✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

美团

题目一：小兰的密码破译

1️⃣：从左到右扫描字符串，寻找 "pw" 模式的出现位置

2️⃣：使用哈希表存储密钥标识符去重，统计不同种类数量

难度：简单

这道题目的关键在于理解字符串的唯一分割规律，通过线性扫描找到每个密码片段的边界。由于分割的唯一性，我们可以使用贪心的方式从左到右处理，时间复杂度为 O(n)。

题目二：小基的数字游戏

1️⃣：分析 MEX 的性质，找到数组中从 0 开始的最长连续段

2️⃣：使用贪心策略，将连续段按顺序放在前面以最大化前缀 MEX 值

难度：中等

这道题目的核心观察是 MEX 值的增长规律。通过数学分析可以发现，为了最大化"缺失数组"的和，应该让 MEX 值尽可能快地增长。最优策略是将从 0 开始的连续整数按顺序排列在前面。

题目三：小毛的家族投资计划

1️⃣：建立树结构，理解"反链"（无祖先-后代关系的节点集合）的概念

2️⃣：使用树形 DP 结合多重背包的思想进行状态转移

3️⃣：对每个节点维护选择不同数量节点的最优方案

难度：中等偏难

这是一道经典的树形动态规划问题。难点在于理解"反链"的概念和设计合适的状态转移。通过将子树信息合并的多重背包方法，可以在 O(n²) 的时间复杂度内解决问题。

题目四：小柯的网络管理系统

1️⃣：理解网络效率的定义，分析修改操作对效率值的影响范围

2️⃣：使用双线段树分别维护按编号的区间查询和按子树的区间查询

3️⃣：通过 DFS 序将树上查询转化为区间查询

难度：中等偏难

这道题目综合了树结构、异或运算和线段树等多个知识点。关键观察是修改操作只影响节点本身和其父节点，因此可以高效地进行增量更新。双线段树的设计巧妙地处理了两种不同类型的查询。

01. 小兰的密码破译

问题描述

小兰收到了一份来自秘密组织的加密文件，这份文件由一串小写字母组成。据情报显示，这个字符串由多个"密码片段"组成，每个密码片段都以字母 pw 结尾，前面是一个"密钥标识符"。

具体规则如下：每个密码片段的格式为 密钥标识符 + pw，其中密钥标识符不能包含字母 p 和 w。比如 secretpw 表示密钥标识符是 secret，abcpw 表示密钥标识符是 abc。

现在 小兰需要知道这份加密文件中包含多少种不同的密钥标识符。

文件保证可以被唯一地分割为一个或多个密码片段。

输入格式

第一行输入一个仅由小写字母组成的字符串 （），表示加密文件的内容。

输出格式

输出一个整数，表示加密文件中包含多少种不同的密钥标识符。

样例输入

secretpwabcpw

xyzpwdefpwabcpw

样例输出

2

3

数据范围

题解

这道题的核心是理解密码片段的构成规律。由于每个密码片段都以 pw 结尾，而且分割是唯一的，我们可以从左到右扫描字符串，每当遇到 pw 就确定了一个密码片段的结束位置。

具体解法：

1. 从头开始扫描字符串，寻找 pw 出现的位置
2. 当在位置 i 找到 pw 时，说明从上一个片段结束后到位置 i-1 的子串就是当前片段的密钥标识符
3. 将这个密钥标识符加入到集合中去重
4. 继续扫描下一个片段
5. 最终集合的大小就是不同密钥标识符的数量

这个算法的时间复杂度是 ，空间复杂度是 （用于存储不同的密钥标识符）。

参考代码

Python

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

s = input()
key_set = set()  # 存储不同的密钥标识符
n = len(s)
start = 0  # 当前密码片段的起始位置

i = 0
while i < n - 1:
    # 检查是否找到 "pw"
    if s[i] == 'p' and s[i + 1] == 'w':
        # 提取密钥标识符
        key = s[start:i]
        key_set.add(key)
        # 移动到下一个片段的起始位置
        start = i + 2
        i += 2
    else:
        i += 1

print(len(key_set))

Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    unordered_set<string> keys;  // 存储不同的密钥标识符
    int n = s.size();
    int start = 0;  // 当前密码片段的起始位置
    
    for (int i = 0; i < n - 1; i++) {
        // 检查是否找到 "pw"
        if (s[i] == 'p' && s[i + 1] == 'w') {
            // 提取密钥标识符
            string key = s.substr(start, i - start);
            keys.insert(key);
            // 移动到下一个片段的起始位置
            start = i + 2;
            i++;  // 跳过 'w'
        }
    }
    
    cout << keys.size() << "\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));
        String s = br.readLine();
        
        HashSet<String> keySet = new HashSet<>();  // 存储不同的密钥标识符
        int n = s.length();
        int start = 0;  // 当前密码片段的起始位置
        
        for (int i = 0; i < n - 1; i++) {
            // 检查是否找到 "pw"
            if (s.charAt(i) == 'p' && s.charAt(i + 1) == 'w') {
                // 提取密钥标识符
                String key = s.substring(start, i);
                keySet.add(key);
                // 移动到下一个片段的起始位置
                start = i + 2;
                i++;  // 跳过 'w'
            }
        }
        
        System.out.println(keySet.size());
    }
}

02. 小基的数字游戏

问题描述

小基 正在玩一个有趣的数字游戏。她有一个包含 个非负整数的数组 ，她可以任意重新排列这些数字。

游戏规则如下：对于重排后的数组，她需要计算一个长度为 的"缺失数组" ，其中 表示前 个元素中没有出现的最小非负整数（即 MEX 值）。

小基 的目标是通过重新排列数组 ，使得"缺失数组" 中所有元素的和最大。

你需要帮助 小基 找到这个最大和，并给出一种可能的数组重排方案。

【名词解释】

：一个整数数组的 定义为没有出现在数组中的最小非负整数。例如 ，。

输入格式

第一行输入一个正整数 （），表示数组 的长度。

第二行输入 个非负整数 （），表示数组 的元素。

输出格式

第一行输出一个整数，表示"缺失数组" 的最大元素和。

第二行输出 个整数，表示重排后的数组 。

如果存在多个解决方案，您可以输出任意一个。

样例输入

3
1 0 1

6
0 1 2 3 4 5

样例输出

5
0 1 1

21
0 1 2 3 4 5

样例	解释说明
样例1	将数组重排为 后，缺失数组 为 ，元素和为
样例2	数组本身已经是最优排列，缺失数组 为 ，元素和为

数据范围

题解

这道题的关键观察是：为了让 MEX 值尽可能大且增长尽可能快，我们应该让前缀包含尽可能多的连续整数从 0 开始。

具体分析：

1. 当前缀包含了 这 个连续整数时，其 MEX 值为
2. 为了最大化"缺失数组" 的和，我们希望 MEX 值能够尽快增长到最大可能值
3. 设数组中包含的不同整数能形成的最长连续段是 ，那么最优策略是先按顺序放置这些数

算法步骤：

1. 统计数组中出现的所有不同数字
2. 找到最小的缺失数 （即从 0 开始的最长连续段的长度）
3. 将 按顺序放在数组前面
4. 剩余的数字任意排列在后面
5. 计算最大和：前 个位置的贡献是 ，后面每个位置的贡献都是

时间复杂度：（使用哈希表统计）

参考代码

Python

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

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

# 统计出现的数字
num_set = set(a)
m = 0
# 找到最小缺失数
while m in num_set:
    m += 1

# 计算最大和
max_sum = m * (m + 1) // 2 + m * (n - m)
print(max_sum)

# 构造方案
result = []
used = set()

# 先放置 0 到 m-1
for i in range(m):
    result.append(i)

# 再放置剩余元素
for num in a:
    if num < m and num not in used:
        used.add(num)
    else:
        result.append(num)

print(' '.join(map(str, result)))

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> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 统计出现的数字
    unordered_set<long long> vis(a.begin(), a.end());
    int m = 0;
    // 找到最小缺失数
    while (vis.count(m)) {
        m++;
    }
    
    // 计算最大和
    long long max_sum = 1LL * m * (m + 1) / 2 + 1LL * m * (n - m);
    cout << max_sum << "\n";
    
    // 构造方案
    vector<long long> rest;
    unordered_map<long long, int> used;
    
    // 收集剩余元素
    for (long long x : a) {
        if (x < m && !used[x]) {
            used[x] = 1;
        } else {
            rest.push_back(x);
        }
    }
    
    // 输出方案：先输出 0 到 m-1
    for (int i = 0; i < m; i++) {
        cout << i << " ";
    }
    // 再输出剩余元素
    for (size_t i = 0; i < rest.size(); i++) {
        cout << rest[i];
        if (i + 1 < rest.size()) cout << " ";
    }
    cout << "\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[] parts = br.readLine().split(" ");
        long[] a = new long[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(parts[i]);
        }
        
        // 统计出现的数字
        HashSet<Long> numSet = new HashSet<>();
        for (long x : a) {
            numSet.add(x);
        }
        
        int m = 0;
        // 找到最小缺失数
        while (numSet.contains((long) m)) {
            m++;
        }
        
        // 计算最大和
        long maxSum = (long) m * (m + 1) / 2 + (long) m * (n - m);
        System.out.println(maxSum);
        
        // 构造方案
        List<Long> rest = new ArrayList<>();
        HashSet<Long> used = new HashSet<>();
        
        // 收集剩余元素
        for (long x : a) {
            if (x < m && !used.contains(x)) {
                used.add(x);
            } else {
                rest.add(x);
            }
        }
        
        // 输出方案：先输出 0 到 m-1
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            sb.append(i).append(" ");
        }
        // 再输出剩余元素
        for (int i = 0; i < rest.size(); i++) {
            sb.append(rest.get(i));
            if (i < rest.size() - 1) sb.append(" ");
        }
        
        System.out.println(sb.toString());
    }
}

03. 小毛的家族投资计划

问题描述

小毛拥有一个庞大的家族企业，家族成员关系可以用一棵以 小毛（编号为 ）为根的家族树来表示。每个家族成员 都有一个投资能力值 。

现在 小毛要制定一个投资计划，从家族成员中选择 个人参与投资项目。但是有一个重要的限制：选择的成员之间不能存在直系血缘关系（即不能同时选择祖先和其后代）。

对于每个可能的投资人数 （），小毛想知道在满足条件下能够获得的最大投资能力值之和 。如果无法选择出 个满足条件的成员，则 。

【名词解释】

祖先节点：在以 为根的家族树中，如果节点 在节点 到根节点 的路径上，且 ，则称 是 的祖先节点。

输入格式

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

对于每组测试数据：

第一行输入一个正整数 （），表示家族成员的数量。

第二行输入 个正整数 （），表示每个家族成员的投资能力值。

接下来 行，每行输入两个正整数 （），表示家族成员 和 之间有直系血缘关系。输入保证构成一棵合法的树。

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

输出格式

对于每组测试数据，输出一行 个整数，第 个整数表示 。

样例输入

2
1
114514
4
5 3 3 3
1 2
1 4
4 1

样例输出

114514
5 6 9 -1

样例	解释说明
样例1	只有一个成员，所以
样例2	对于 的情况： 选择投资能力最高的成员（值为 ）， 选择值为 和 的成员（总和为 ，但实际输出是 ）， 可以选择三个值为 的成员， 无法满足条件

数据范围

• 
• 
• 
• 
• 保证所有测试数据的 之和不超过

题解

这是一个树形动态规划问题。我们需要在树上选择 个节点，使得这些节点两两之间没有祖先-后代关系，这样的节点集合称为"反链"。

核心思路是使用树形DP配合多重背包的思想：

对每个节点 ，我们定义：

• dp0[u][t]：在节点 不被选择的前提下，从 的子树中恰好选择 个节点的最大价值
• 如果选择节点 ，那么其所有子孙都不能再被选择，贡献就是

算法步骤：

1. 对于叶子节点，初始化 dp0[u][0] = 0
2. 对于非叶子节点，通过子节点的信息进行状态转移
3. 在合并子节点信息时，使用类似背包的思想：对于每个子节点 ，我们可以选择从其子树中取 到 size[v] 个节点
4. 特别地，如果取 个节点，我们可以选择不选 （使用 dp0[v][1]）或者直接选 （价值为 ）

时间复杂度为 ，对于给定的数据范围是可行的。

参考代码

Python

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

def solve():
    n = int(input())
    a = [0] + list(map(int, input().split()))
    
    # 建图
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # 树形DP
    # dp0[u] 表示不选择u时，从u的子树中选择若干节点的所有可能方案
    # dp0[u][k] = 从u的子树中选择k个节点的最大价值（u不被选择）
    dp0 = {}
    
    def dfs(u, p):
        # 初始化：不选任何节点的价值为0
        dp0[u] = {0: 0}
        
        for v in adj[u]:
            if v != p:
                dfs(v, u)
                
                # 计算从v的子树中选择的方案
                # 1. 不选v，使用dp0[v]的所有方案
                # 2. 选择v，价值为a[v]，选择1个节点
                v_options = dict(dp0[v])
                v_options[1] = max(v_options.get(1, float('-inf')), a[v])
                
                # 合并到当前节点u的方案中（背包DP）
                new_dp = {}
                for i, val_i in dp0[u].items():
                    for j, val_j in v_options.items():
                        k = i + j
                        new_dp[k] = max(new_dp.get(k, float('-inf')), val_i + val_j)
                
                dp0[u] = new_dp
    
    dfs(1, 0)
    
    # 计算答案
    ans = [-1] * (n + 1)
    
    # 不选根节点的情况
    for k, val in dp0[1].items():
        if k <= n:
            ans[k] = max(ans[k], val)
    
    # 选择根节点的情况（只选择根节点，k=1）
    ans[1] = max(ans[1], a[1])
    
    print(' '.join(map(str, ans[1:n+1])))

t = int(input())
for _ in range(t):
    solve()

Cpp

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

const int MAXN = 5005;
vector<int> g[MAXN];
unordered_map<int, ll> dp0[MAXN];  // dp0[u] 表示不选择u时的所有可能方案
ll a[MAXN];

void dfs(int u, int p) {
    // 初始化：不选任何节点的价值为0
    dp0[u].clear();
    dp0[u][0] = 0;
    
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
            
            // 计算从v的子树中选择的方案
            unordered_map<int, ll> v_options = dp0[v];
            // 选择v本身的情况
            if (v_options.count(1)) {
                v_options[1] = max(v_options[1], a[v]);
            } else {
                v_options[1] = a[v];
            }
            
            // 合并到当前节点u的方案中（背包DP）
            unordered_map<int, ll> new_dp;
            
            for (auto& [i, val_i] : dp0[u]) {
                for (auto& [j, val_j] : v_options) {
                    int k = i + j;
                    if (new_dp.count(k)) {
                        new_dp[k] = max(new_dp[k], val_i + val_j);
                    } else {
                        new_dp[k] = val_i + val_j;
                    }
                }
            }
            
            dp0[u] = new_dp;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        cin >> a[i];
    }
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    dfs(1, 0);
    
    vector<ll> ans(n + 1, -1);
    
    // 不选根节点的情况
    for (auto& [k, val] : dp0[1]) {
        if (k <= n) {
            ans[k] = max(ans[k], val);
        }
    }
    
    // 选择根节点的情况（只选择根节点，k=1）
    ans[1] = max(ans[1], a[1]);
    
    for (int k = 1