✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线140+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：小基的餐厅评分系统

1️⃣：维护累计目标评分和累计实际评分的前缀和

2️⃣：根据累计表现决定补偿倍数，分情况讨论计算总代价

难度：中等

这道题目的关键在于理解累计表现对补偿机制的影响。通过维护两个前缀和，可以在 O(n) 时间内判断每一天的补偿情况。核心思想是根据当前累计表现的好坏来决定补偿倍数，体现了贪心和模拟的结合。

题目二：小柯的古董收藏拍卖

1️⃣：分析每个古董的Grundy数，奇数为0，偶数为其2的幂次

2️⃣：使用Sprague-Grundy定理，计算所有Grundy数的异或和

3️⃣：异或和非0则先手必胜，否则后手必胜

难度：中等偏难

这道题目是经典的博弈论问题，需要深入理解Sprague-Grundy定理。关键观察是每个数字的Grundy数只与其包含的因子2的个数有关，通过位运算可以高效计算。体现了博弈论、数论和位运算的综合应用。

题目三：小兰的魔法咒语转换

1️⃣：将问题转化为图论中的最短路径问题

2️⃣：使用完全背包的思想进行动态规划

3️⃣：多轮迭代直到状态收敛，处理多组查询

难度：中等

这道题目巧妙地将字符串循环移位问题转化为图论的最短路径问题。通过类似完全背包的动态规划方法，可以高效地计算出所有可达状态的最少操作次数。关键技巧是状态压缩和迭代优化，实现了 O(n×k) 的时间复杂度。

01. 小基的餐厅评分系统

问题描述

小基 经营着一家高端餐厅，她建立了一个严格的品质评分系统。餐厅运营了 天，第 天的目标评分是 分，实际获得的评分是 分。

为了维护餐厅的声誉，小基 制定了如下的补偿机制：

• 如果第 天实际评分低于目标评分（即 ），需要进行补偿。

• 补偿的代价取决于截至第 天的累计表现：

  • 若截至第 天的累计实际评分 不少于累计目标评分 ，说明总体表现良好，只需支付 个信誉点作为补偿。

  • 若截至第 天的累计实际评分 少于累计目标评分 ，说明总体表现不佳，需要支付 个信誉点作为补偿。

请计算 小基 总共需要支付多少个信誉点。

输入格式

第一行包含一个正整数 （），表示餐厅运营的天数。

第二行包含 个正整数 （），表示每天的目标评分。

第三行包含 个正整数 （），表示每天的实际评分。

输出格式

输出一个整数，表示总共需要支付的信誉点数量。

样例输入

3
2 1 3
1 2 2

5
3 3 3 3 3
2 4 1 5 2

样例输出

4

8

样例	解释说明
样例1	第1天：，累计实际1 < 累计目标2，补偿 ；第2天：，无需补偿；第3天：，累计实际5 < 累计目标6，补偿 。总计
样例2	逐天分析累计评分和补偿计算，包含多种累计表现情况，最终总补偿为8

数据范围

题解

这道题考查的是前缀和的应用和分情况讨论。

首先理解题目的核心：每一天如果实际评分低于目标评分，就需要支付补偿，补偿的多少取决于到当前为止的累计表现。

具体来说，维护两个前缀和：

• sum_a：累计目标评分
• sum_b：累计实际评分

对于每一天：

1. 更新 sum_a += a[i] 和 sum_b += b[i]
2. 如果 b[i] < a[i]，计算差值 diff = a[i] - b[i]
3. 根据累计表现决定补偿：
   • 如果 sum_b >= sum_a，说明累计表现良好，补偿 diff
   • 否则累计表现不佳，补偿 2 * diff

这个方法的时间复杂度是 ，空间复杂度是 ，对于给定的数据范围完全可以接受。

关键观察：我们不需要存储所有的前缀和，只需要在遍历过程中维护当前的累计值即可。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 维护累计评分和总补偿
sum_target, sum_actual, total_cost = 0, 0, 0

for i in range(n):
    # 更新累计评分
    sum_target += a[i]
    sum_actual += b[i]
    
    # 如果当天实际评分低于目标，需要补偿
    if b[i] < a[i]:
        gap = a[i] - b[i]
        # 根据累计表现决定补偿倍数
        mult = 1 if sum_actual >= sum_target else 2
        total_cost += gap * mult

print(total_cost)

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<long long> target(n), actual(n);
    for (int i = 0; i < n; i++) {
        cin >> target[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> actual[i];
    }
    
    // 累计评分和总补偿
    long long sum_t = 0, sum_a = 0, ans = 0;
    
    for (int i = 0; i < n; i++) {
        sum_t += target[i];
        sum_a += actual[i];
        
        // 检查是否需要补偿
        if (actual[i] < target[i]) {
            long long diff = target[i] - actual[i];
            // 根据累计表现计算补偿
            if (sum_a >= sum_t) {
                ans += diff;
            } else {
                ans += diff * 2;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        String[] targetStr = br.readLine().split(" ");
        String[] actualStr = br.readLine().split(" ");
        
        long[] target = new long[n];
        long[] actual = new long[n];
        
        for (int i = 0; i < n; i++) {
            target[i] = Long.parseLong(targetStr[i]);
            actual[i] = Long.parseLong(actualStr[i]);
        }
        
        // 累计评分和总补偿计算
        long sumTarget = 0, sumActual = 0, totalCost = 0;
        
        for (int i = 0; i < n; i++) {
            sumTarget += target[i];
            sumActual += actual[i];
            
            // 当天表现不达标时的补偿计算
            if (actual[i] < target[i]) {
                long shortage = target[i] - actual[i];
                // 基于累计表现的补偿策略
                int penalty = (sumActual >= sumTarget) ? 1 : 2;
                totalCost += shortage * penalty;
            }
        }
        
        System.out.println(totalCost);
    }
}

02. 小柯的古董收藏拍卖

问题描述

小柯是一位古董收藏家，她和 小毛 在玩一个特殊的拍卖游戏。拍卖会上有 件古董，第 件古董的估价为 万元。两人轮流进行竞拍，小柯先开始。

每轮竞拍的规则如下：

1. 首先选择一件估价大于 1 万元的古董（即选择下标 使得 ）。

2. 然后选择一个正整数 ，满足：

   • 
   • 

   也就是说， 必须是 的真因数。

3. 将该古董的估价降低 万元（即该古董新估价变为 ）。

如果某位竞拍者在自己的回合无法进行任何操作，则该竞拍者失败，另一位获胜。

假设双方都采用最优策略，请判断谁将获得最终胜利。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 （），表示测试数据组数。

每组测试数据格式如下：

第一行包含一个正整数 （），表示古董数量。

第二行包含 个正整数 （），表示各件古董的估价。

保证所有测试数据中 的总和不超过 。

输出格式

对每组测试数据输出一行结果：

如果小柯最终获胜，输出 Baobao；

否则输出 Zeeman。

样例输入

5
2
4 4
1
2
2
114514 1919810
5
16 48 22 12 24
2
4 2

样例输出

Zeeman
Baobao
Zeeman
Zeeman
Baobao

数据范围

• 

• 

• 

• 所有测试数据中 的总和不超过

题解

这是一道经典的博弈论问题，需要用到Sprague-Grundy定理。

首先分析单个古董的情况。对于估价为 的古董，能够到达的状态是所有 的值，其中 是 的真因数。

关键观察：

1. 如果 是奇数，那么它的所有因数都是奇数，减去后得到的都是偶数。而偶数状态可以继续操作，奇数状态（除了1）无法操作。因此奇数的Grundy数为0。

2. 如果 是偶数，设 ，其中 是奇数，。分析发现， 的Grundy数等于 ，即 中因子2的个数。

具体计算方法：

• 对于奇数，Grundy数为0
• 对于偶数，Grundy数为其二进制表示中末尾0的个数（即2的最大幂次）

整个游戏的Grundy数就是所有古