✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：图书管理员的排班问题

1️⃣：根据月份判断是否为忙碌期，决定当月工作效率

2️⃣：按月循环模拟整理过程，直到所有图书整理完毕

3️⃣：利用周期性特点，通过简单循环实现时间复杂度优化

难度：中等

这道题目的核心是理解周期性模拟。由于一年只有12个月且忙碌期不跨年，可以通过月份循环来模拟整个过程。关键在于正确判断忙碌期，并处理跨年的月份更新。

题目二：城市网络的安全标识

1️⃣：将问题转化为树的二分染色问题

2️⃣：使用BFS或DFS求出每个节点的层次奇偶性

3️⃣：计算两种染色方案的修改代价，选择较小值

难度：中等

这道题目结合了图论中的树结构和二分染色概念。通过理解树可以进行二分染色的性质，将问题转化为在两种合法方案中选择修改次数较少的一种。

题目三：游戏道具的收集策略

1️⃣：使用质因数分解避免LCM计算时的数值溢出

2️⃣：维护目标LCM和当前前缀LCM的质因数指数表

3️⃣：通过扩展前缀并实时更新满足条件的质因数个数

难度：中等偏难

这道题目需要深入理解最小公倍数的本质和质因数分解。通过将LCM问题转化为质因数指数问题，可以避免直接计算大数LCM造成的溢出，并实现高效的前缀扩展算法。

01. 图书管理员的排班问题

问题描述

小兰是一位图书馆管理员，负责管理图书馆的日常运营。图书馆有一个特殊的规定：每个月需要完成一定数量的图书整理工作。

具体规则如下：

1. 在年初时，图书馆积累了 本需要整理的图书。
2. 平常每个月可以整理 本图书。
3. 每年从第 个月开始，会有连续 个月的忙碌期。
4. 在忙碌期内，每个月可以整理 本图书。

当剩余需要整理的图书数量不大于零时，视为所有图书已整理完毕。现在请你帮助小兰计算：整理完所有图书需要多少个月。

输入格式

第一行包含四个正整数 ，分别表示：

• （）：初始需要整理的图书数量
• （）：平常每月可以整理的图书数量
• （）：忙碌期开始的月份
• （）：忙碌期持续的月份数

保证忙碌期不会跨年。

输出格式

输出一个整数，表示整理完所有图书所需的月数。

样例输入

10 1 1 3

50 10 4 4

样例输出

7

4

数据范围

题解

这道题本质上是一个模拟问题。由于一年只有12个月，而忙碌期始终在同一年内，所以我们可以按月份循环模拟整个过程。

关键思路：

1. 维护当前月份，从1月开始
2. 根据当前月份是否在忙碌期内，决定本月可以整理多少本图书
3. 更新剩余图书数量，月份计数器递增
4. 当到达13月时重置为1月（新的一年）
5. 重复以上过程直到图书全部整理完毕

判断忙碌期的方法：如果当前月份在区间 内，则为忙碌期。

算法复杂度分析：

• 时间复杂度：，最坏情况下循环次数不超过 次
• 空间复杂度：，只需常数级别的额外空间

参考代码

• Python

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

def solve():
    # 读取输入数据
    n, m, p, q = map(int, input().split())
    
    # 初始化变量
    month = 1      # 当前月份，从1月开始
    total = 0      # 总月数计数器
    remain = n     # 剩余需要整理的图书数量
    
    # 判断是否在忙碌期的辅助函数
    def is_busy_period(cur_month):
        return p <= cur_month <= p + q - 1
    
    # 模拟整理过程
    while remain > 0:
        # 根据当前月份决定本月可整理的图书数量
        if is_busy_period(month):
            work = 2 * m  # 忙碌期，双倍效率
        else:
            work = m      # 平常期，正常效率
        
        # 更新剩余图书数量
        remain -= work
        total += 1
        
        # 月份递增，处理跨年情况
        month += 1
        if month > 12:
            month = 1
    
    print(total)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入数据
    long long n, m;
    int p, q;
    cin >> n >> m >> p >> q;
    
    // 初始化变量
    int month = 1;          // 当前月份
    long long total = 0;    // 总月数计数器
    long long remain = n;   // 剩余图书数量
    
    // 判断忙碌期的lambda函数
    auto busy = [&](int cur) {
        return cur >= p && cur <= p + q - 1;
    };
    
    // 模拟整理过程
    while (remain > 0) {
        // 计算本月可整理的图书数量
        long long work = busy(month) ? 2 * m : m;
        
        // 更新状态
        remain -= work;
        total++;
        
        // 月份递增，处理跨年
        month++;
        if (month > 12) month = 1;
    }
    
    cout << total << '\n';
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 读取输入数据
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        
        // 初始化变量
        int month = 1;          // 当前月份
        long total = 0;         // 总月数计数器
        long remain = n;        // 剩余图书数量
        
        // 模拟整理过程
        while (remain > 0) {
            // 判断当前月份是否为忙碌期
            boolean isBusy = (month >= p && month <= p + q - 1);
            
            // 计算本月可整理的图书数量
            long work = isBusy ? 2 * m : m;
            
            // 更新状态
            remain -= work;
            total++;
            
            // 月份递增，处理跨年
            month++;
            if (month > 12) {
                month = 1;
            }
        }
        
        System.out.println(total);
    }
}

02. 城市网络的安全标识

问题描述

小毛负责一个城市的网络安全系统。该系统由 个节点组成，节点编号为 到 ，节点之间通过 条双向连接构成一个连通的树形网络。

每个节点都有一个安全标识，标识只能是以下三种类型之一：

• s：安全节点
• d：危险节点
• ?：未分类节点

为了确保网络安全，系统要求：

1. 所有节点的标识必须是 s 或 d（不能有 ?）
2. 任意两个直接相连的节点必须有不同的标识

小毛可以对任意节点进行重新标识操作，每次操作可以将一个节点的标识修改为 s 或 d。请帮助小毛找到使整个网络满足安全要求的最少操作次数。

输入格式

第一行包含一个正整数 （），表示网络节点数。

第二行包含一个长度为 的字符串 ，仅包含字符 s、d 和 ?，其中第 个字符表示节点 的初始安全标识。

接下来 行，每行包含两个正整数 和 （，），表示节点 与节点 之间存在一条双向连接。

输出格式

输出一个整数，表示使网络满足安全要求的最少操作次数。

样例输入

5
?s?dd
1 2
2 3
2 4
4 5

4
ssss
1 2
2 3
3 4

样例输出

3

2

数据范围

• 
• 字符串 仅包含字符 s、d 和 ?
• 保证输入构成一棵树

题解

这道题的核心是理解树的性质：树是一个连通的无环图，可以进行二分染色。换句话说，我们可以将树的所有节点分为两个集合，使得同一集合内的节点互不相邻。

解题思路：

1. 对树进行深度优先搜索或广度优先搜索，给每个节点标记奇偶层
2. 有两种合法的标识方案：
   • 方案A：偶数层标识为s，奇数层标识为d
   • 方案B：偶数层标识为d，奇数层标识为s
3. 对于每种方案，计算需要修改的节点数
4. 选择修改次数较少的方案

计算修改次数的方法：

• 如果节点当前标识与目标标识相同，修改次数为0
• 如果节点当前标识为?或与目标标识不同，修改次数为1

算法复杂度：

• 时间复杂度：，需要遍历所有节点一次
• 空间复杂度：，存储图的邻接表

参考代码

• Python

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

def solve():
    # 读取输入
    n = int(input())
    labels = input().strip()
    
    # 构建邻接表
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        u -= 1  # 转换为0-indexed
        v -= 1
        graph[u].append(v)
        graph[v].append(u)
    
    # BFS求每个节点的层次（奇偶性）
    layer = [-1] * n
    queue = deque([0])
    layer[0] = 0
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if layer[neighbor] == -1:
                layer[neighbor] = layer[node] ^ 1  # 交替层次
                queue.append(neighbor)
    
    # 计算两种方案的修改次数
    cost_a = 0  # 偶数层s，奇数层d
    cost_b = 0  # 偶数层d，奇数层s
    
    for i in range(n):
        target_a = 's' if layer[i] == 0 else 'd'
        target_b = 'd' if layer[i] == 0 else 's'
        
        # 如果当前标识与目标不同，需要修改
        if labels[i] != target_a:
            cost_a += 1
        if labels[i] != target_b:
            cost_b += 1
    
    print(min(cost_a, cost_b))

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    cin >> n;
    string labels;
    cin >> labels;
    
    // 构建邻接表
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // 转换为0-indexed
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // BFS求层次
    vector<int> layer(n, -1);
    queue<int> q;
    q.push(0);
    layer[0] = 0;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int neighbor : graph[node]) {
            if (layer[neighbor] == -1) {
                layer[neighbor] = layer[node] ^ 1;
                q.push(neighbor);
            }
        }
    }
    
    // 计算两种方案的代价
    int cost_a = 0, cost_b = 0;
    for (int i = 0; i < n; ++i) {
        char target_a = (layer[i] == 0) ? 's' : 'd';
        char target_b = (layer[i] == 0) ? 'd' : 's';
        
        if (labels[i] != target_a) cost_a++;
        if (labels[i] != target_b) cost_b++;
    }
    
    cout << min(cost_a, cost_b) << '\n';
    return 0;
}

• Java

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

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 labels = br.readLine();
        
        // 构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < n - 1; i++) {
            String