✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

携程-2025.11.06

题目一：小兰的花园灌溉系统

1️⃣：按顺序处理每个花圃，检查左右相邻位置是否已安装设备

2️⃣：若左右都未安装且不是第一个，需要建设新水源

3️⃣：用布尔数组标记已安装状态，时间复杂度 O(n)

难度：简单

题目二：小基的密码本重建

1️⃣：遍历字符追踪记录数组

2️⃣：遇到 0 时分配新字符，从 a 开始递增

3️⃣：遇到非 0 值时复制对应位置的字符

难度：简单

题目三：小毛的抽奖券配对

1️⃣：将抽奖券编号按模 分类，分析余数类的配对关系

2️⃣：利用鸽笼原理计算互补余数对能选的最大券数

3️⃣：特殊处理余数为 和 （偶数时）的情况

难度：中等

题目四：小柯的社交网络分析

1️⃣：通过两次 BFS 找到树的直径端点

2️⃣：计算每个节点的离心率（到树上最远点的距离）

3️⃣：统计离心率后缀和，判断每个 对应的连通块数量

难度：中等偏难

1. 小兰的花园灌溉系统

问题描述

小兰在她的花园里有一排编号为 到 的 个花圃，初始时所有花圃都还未安装灌溉设备。她手头有一份施工清单，按时间顺序列出了需要安装灌溉设备的花圃编号序列 ，这些编号两两不同。

灌溉设备的安装遵循"水源连接"规则：

• 如果当前还没有安装任何灌溉设备，可以免费为第一个花圃 安装设备并建立水源；

• 如果已经有花圃安装了灌溉设备，在为花圃 安装设备时：

  • 若花圃 与至少一个已安装设备的花圃相邻（即存在已安装的花圃 使得 ），则可以直接从相邻花圃引水，无需额外成本；

  • 否则，必须消耗 次"独立水源建设"才能为该花圃安装设备。

小兰想知道，按照施工清单的顺序完成所有花圃的灌溉设备安装，最少需要建设多少个独立水源。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，表示测试数据的组数。

对于每组测试数据：

• 第一行输入一个整数 ，表示花圃的数量；

• 第二行输入 个两两不同的整数 ，表示施工清单中的花圃编号序列。

输出格式

对于每组测试数据，输出一行一个整数，表示最少需要建设的独立水源数量。

样例输入

2

5
3 1 5 2 4

3
2 1 3

样例输出

2

0

数据范围

• 

• 

• ，且 两两不同

• 单个测试文件中所有 的和不超过

样例	解释说明
样例1	安装顺序为 。首先为花圃 建立水源（免费）；花圃 与 不相邻，需要建设第 个独立水源；花圃 与 不相邻、与 也不相邻，需要建设第 个独立水源；花圃 与花圃 和 相邻，可以引水；花圃 与花圃 和 相邻，可以引水。共需 个独立水源。
样例2	安装顺序为 。首先为花圃 建立水源（免费）；花圃 与 相邻，可以引水；花圃 与 相邻，可以引水。无需建设独立水源，答案为 。

题解

这道题的核心在于理解"相邻"的概念。当我们为某个花圃安装灌溉设备时，只要它的左边或右边有一个花圃已经安装了设备，就可以从那里引水，不需要建设新的独立水源。

具体来说，按照施工清单的顺序逐个处理每个花圃：

• 对于第一个花圃，直接建立初始水源（这个不计入答案，因为题目问的是需要建设多少个"独立水源"）；
• 对于后续的每个花圃 ，检查位置 和 是否已经安装了设备；
• 如果两个相邻位置都没有安装设备，说明无法引水，需要建设一个新的独立水源，答案加 ；
• 如果至少有一个相邻位置已经安装了设备，可以引水，不需要建设新水源。

实现时，可以用一个布尔数组记录每个花圃是否已经安装了设备。为了避免边界判断，可以将数组开大一些，在两端留出缓冲位置。

时间复杂度为 ，因为每个花圃只需要处理一次，每次处理只需要常数时间的检查和更新操作。

空间复杂度为 ，需要一个大小为 的数组来记录每个花圃的安装状态。

这个复杂度对于题目给定的数据范围（）是完全可以接受的。

参考代码

• Python

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

# 读取测试数据组数
t = int(input())
for _ in range(t):
    # 读取花圃数量
    n = int(input())
    # 读取施工清单
    seq = list(map(int, input().split()))
    
    # vis数组记录每个位置是否已安装设备，两端留出缓冲
    vis = [False] * (n + 3)
    
    # 统计需要建设的独立水源数
    cnt = 0
    # 已安装设备的花圃数量
    done = 0
    
    # 按顺序处理每个花圃
    for pos in seq:
        # 如果不是第一个，且左右都没有安装设备
        if done > 0 and not vis[pos - 1] and not vis[pos + 1]:
            cnt += 1
        # 标记当前花圃已安装
        vis[pos] = True
        done += 1
    
    print(cnt)

• Cpp

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        
        // ok数组标记每个花圃是否已安装设备
        vector<bool> ok(n + 3, false);
        
        int ans = 0;  // 需要建设的独立水源数
        int num = 0;  // 已安装设备的花圃数
        
        // 按顺序读取并处理每个花圃
        for(int i = 0; i < n; i++){
            int x;
            cin >> x;
            
            // 不是第一个，且左右相邻都未安装
            if(num > 0 && !ok[x - 1] && !ok[x + 1]){
                ans++;
            }
            
            // 标记当前花圃已安装
            ok[x] = true;
            num++;
        }
        
        cout << ans << "\n";
    }
    
    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 T = Integer.parseInt(br.readLine());
        
        while(T-- > 0){
            // 读取花圃数量
            int n = Integer.parseInt(br.readLine());
            
            // 读取施工清单
            String[] parts = br.readLine().split(" ");
            
            // isSet数组标记每个花圃是否已安装设备
            boolean[] isSet = new boolean[n + 3];
            
            int res = 0;   // 需要建设的独立水源数
            int total = 0; // 已安装设备的花圃数
            
            // 按顺序处理每个花圃
            for(int i = 0; i < n; i++){
                int pos = Integer.parseInt(parts[i]);
                
                // 不是第一个，且左右相邻都未安装
                if(total > 0 && !isSet[pos - 1] && !isSet[pos + 1]){
                    res++;
                }
                
                // 标记当前花圃已安装
                isSet[pos] = true;
                total++;
            }
            
            System.out.println(res);
        }
    }
}

2. 小基的密码本重建

问题描述

小基有一个特殊的密码本，密码本中有一个长度为 的密码串 ，由小写字母组成。不幸的是，密码串本身丢失了，但小基找到了一份关于这个密码串的"字符追踪记录"。

这份记录是一个长度为 的数组 ，其中对于每个位置 （）：

• 如果 ，表示密码串中第 个字符在位置 中从未出现过，即这是该字符第一次出现；

• 如果 ，表示密码串中第 个字符与位置 的字符相同，并且在区间 内没有出现过这个字符，也就是说 是该字符上一次出现的位置。

现在，请你根据这份"字符追踪记录"帮助小基重建原来的密码串。题目保证输入数据一定合法，即至少存在一个满足条件的密码串，并且所需的不同字符数不超过 个。

输入格式

第一行输入一个整数 ，表示密码串的长度。

第二行输入 个整数 ，表示字符追踪记录数组。

输出格式

输出一行，一个长度为 的字符串 ，由小写字母组成。

如果存在多个满足条件的答案，输出其中任意一个即可。

样例输入

10

0 0 1 2 0 5 3 7 0 9

样例输出

ababccaadd

数据范围

• 

• 

• 题目保证输入合法，存在至少一个满足条件的小写字母串（不同字符数不超过 ）

样例	解释说明
样例1	位置 ：，第一次出现，设为 a；位置 ：，第一次出现，设为 b；位置 ：，与位置 相同，为 a；位置 ：，与位置 相同，为 b；位置 ：，第一次出现，设为 c；位置 ：，与位置 相同，为 c；位置 ：，与位置 相同，为 a；位置 ：，与位置 相同，为 a；位置 ：，第一次出现，设为 d；位置 ：，与位置 相同，为 d。因此密码串为 ababccaadd。

题解

这道题的关键在于理解"字符追踪记录"的含义。对于每个位置，要么是某个字符第一次出现（），要么是继承之前某个位置的字符（）。

既然题目保证输入合法，那么直接按照记录重建密码串即可：

1. 从左到右遍历数组 ；
2. 遇到 时，说明位置 需要一个新的字符，从 a 开始依次分配新字母；
3. 遇到 时，说明位置 的字符与位置 的字符相同，直接复制即可。

由于题目保证了数据的合法性，不需要额外的检查。实现时只需要维护一个当前可用的字母（初始为 a），每次遇到新字符就分配这个字母并递增到下一个。

时间复杂度为 ，只需要一次遍历即可完成重建。

空间复杂度为 ，需要存储重建的密码串。

对于给定的数据范围（），这个算法非常高效。

参考代码

• Python

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

# 读取密码串长度
n = int(input())
# 读取字符追踪记录（注意：题目是1-indexed，但Python从0开始）
rec = [0] + list(map(int, input().split()))

# 初始化密码串，使用列表便于修改
pwd = [''] * (n + 1)

# 当前可用的新字符
ch = 'a'

# 遍历每个位置重建密码串
for i in range(1, n + 1):
    if rec[i] == 0:
        # 第一次出现，分配新字符
        pwd[i] = ch
        ch = chr(ord(ch) + 1)
    else:
        # 继承之前位置的字符
        pwd[i] = pwd[rec[i]]

# 输出重建的密码串（跳过索引0）
print(''.join(pwd[1:]))

• Cpp

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // pre数组存储字符追踪记录
    vector<int> pre(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> pre[i];
    }
    
    // str存储重建的密码串
    string str(n + 1, ' ');
    
    // nxt表示下一个可用的新字符
    char nxt = 'a';
    
    // 遍历每个位置重建密码串
    for(int i = 1; i <= n; i++){
        if(pre[i] == 0){
            // 第一次出现，分配新字符
            str[i] = nxt;
            nxt++;
        } else {
            // 继承之前位置的字符
            str[i] = str[pre[i]];
        }
    }
    
    // 输出从位置1到n的密码串
    cout << str.substr(1) << "\n";
    
    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[] items = br.readLine().split(" ");
        int[] track = new int[n + 1];
        for(int i = 1; i <= n; i++){
            track[i] = Integer.parseInt(items[i - 1]);
        }
        
        // result数组存储重建的密码串
        char[] result = new char[n + 1];
        
        // curChar表示当前可用的新字符
        char curChar = 'a';
        
        // 遍历每个位置重建密码串
        for(int i = 1; i <= n; i++){
            if(trac