✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：学生社团报名系统

1️⃣：按报名时间顺序处理每个学生的志愿

2️⃣：维护三个社团的剩余名额和成员列表

3️⃣：贪心策略按志愿优先级分配

难度：简单

这道题目是一个经典的模拟题，核心在于理解"先到先得"的分配规则。通过维护每个社团的剩余名额，按照学生提交的志愿顺序进行贪心分配，可以得到 O(n) 的高效解法。

题目二：音乐节乐队搭配

1️⃣：将所有成员按演出水平排序，记录所属团体

2️⃣：使用滑动窗口找包含所有团体的最小区间

3️⃣：双指针技术优化窗口大小

难度：中等

这道题目巧妙地将组合优化问题转化为滑动窗口问题。关键观察是最优解必然对应排序后数组中的某个连续区间，通过双指针技术可以在 O(nm log(nm)) 时间内求解。

题目三：古董收集家的寻宝之旅

1️⃣：利用 k≤5 的约束，暴力枚举所有收集顺序

2️⃣：BFS预计算关键点之间的最短距离

3️⃣：模拟每种顺序下的价值损失过程

难度：中等偏难

这道题目结合了图论最短路和状态枚举。虽然看似复杂，但 k≤5 的限制使得 k! 种枚举成为可能。通过精确的状态模拟和路径规划，可以找到最优的收集策略。

题目四：小柯的彩球接收游戏

1️⃣：将问题建模为时间轴上的动态规划

2️⃣：状态设计考虑位置和冰冻时间

3️⃣：按时间顺序进行状态转移

难度：中等偏难

这道题目是一个精妙的动态规划问题，需要在时间维度上进行状态转移。关键在于正确处理冰冻机制和移动约束，通过合理的状态设计可以得到高效的解法。

01. 学生社团报名系统

问题描述

小兰作为学校社团联合会的主席，正在组织这学期的社团招新活动。学校有三个非常受欢迎的社团：编程社、摄影社和文学社，分别用字母 、、 表示。由于场地和师资限制，每个社团都有固定的招收人数上限。

学生们可以根据自己的兴趣爱好，选择报名 到 个社团，并按照偏好程度排列志愿顺序。系统将按照学生提交报名表的时间顺序进行处理，采用"先到先得"的原则：

1. 优先尝试分配到学生的第一志愿社团
2. 如果第一志愿已满，则尝试第二志愿社团
3. 如果所有志愿社团都已满员，则该学生无法加入任何社团

小兰需要你帮她设计一个系统，统计最终每个社团的成员名单。

输入格式

第一行包含一个整数 ，表示报名学生的总数（）。

第二行包含三个整数 、、，分别表示编程社、摄影社、文学社的最大招收人数（）。

接下来 行，每行描述一个学生的报名信息：

• 一个长度为 的字符串，表示学生的学号（由字母和数字组成，且互不相同）
• 一个整数 （），表示该学生报名的社团数量
• 个字符（//），表示学生按志愿优先级选择的社团

输出格式

按照社团 、、 的顺序输出三行。每行第一个数字表示该社团最终的成员人数，后面跟着相应数量的学生学号，按照报名成功的时间顺序输出。

样例输入

4
2 1 1
zhang01 2 A B
chen01 1 B
ll02 3 B C A
yang 2 B A

4
2 1 1
stu001 1 A
stu002 1 A
stu003 1 A
stu004 1 B

样例输出

2 zhang01 yang
1 chen01
1 ll02

2 stu001 stu002
1 stu004
0

样例编号	解释说明
样例1	zhang01首选A社团成功；chen01首选B社团成功；ll02首选B社团已满，次选C社团成功；yang首选B社团已满，次选A社团成功
样例2	stu001和stu002成功加入A社团，stu003因A社团已满无法加入任何社团，stu004加入B社团

数据范围

• 
• 
• 
• 学号长度固定为 ，由字母和数字组成

题解

这道题其实就是一个模拟题，思路很直观。我们需要按照学生报名的时间顺序，依次处理每个学生的志愿，尝试将他们分配到合适的社团。

关键点在于：

1. 维护三个社团的剩余名额
2. 按照学生提交的志愿顺序依次尝试
3. 一旦成功分配就停止，继续处理下一个学生

具体步骤：

1. 读入三个社团的容量限制
2. 为每个社团准备一个列表来存储成员学号
3. 对于每个学生，按照他填写的志愿顺序检查：如果该社团还有名额，就加入并结束；否则尝试下一个志愿
4. 最后按A、B、C的顺序输出每个社团的人数和成员列表

时间复杂度是 ，其中 ，所以实际上就是 。对于 的数据范围完全够用。

参考代码

• Python

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

# 读取基本信息
n = int(input())
caps = list(map(int, input().split()))  # A, B, C社团容量

# 为每个社团维护成员列表
groups = [[] for _ in range(3)]  # 对应A, B, C
remain = caps[:]  # 剩余名额

# 处理每个学生的报名
for _ in range(n):
    line = input().split()
    stu_id = line[0]  # 学生学号
    k = int(line[1])  # 志愿数量
    prefs = line[2:2+k]  # 志愿列表
    
    # 按志愿优先级尝试分配
    for pref in prefs:
        idx = ord(pref) - ord('A')  # A->0, B->1, C->2
        if remain[idx] > 0:  # 还有名额
            remain[idx] -= 1
            groups[idx].append(stu_id)
            break  # 分配成功，处理下一个学生

# 输出结果
for i in range(3):
    cnt = len(groups[i])
    if cnt == 0:
        print("0")
    else:
        print(cnt, *groups[i])

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 读取三个社团的容量
    vector<int> caps(3);
    for (int i = 0; i < 3; i++) {
        cin >> caps[i];
    }
    
    // 维护每个社团的成员列表和剩余名额
    vector<vector<string>> teams(3);
    vector<int> left = caps;
    
    // 处理每个学生
    for (int i = 0; i < n; i++) {
        string id;
        int k;
        cin >> id >> k;
        
        vector<char> choices(k);
        for (int j = 0; j < k; j++) {
            cin >> choices[j];
        }
        
        // 按志愿顺序尝试分配
        for (char ch : choices) {
            int team_idx = ch - 'A';  // A->0, B->1, C->2
            if (left[team_idx] > 0) {
                left[team_idx]--;
                teams[team_idx].push_back(id);
                break;  // 成功分配，跳出
            }
        }
    }
    
    // 输出每个社团的结果
    for (int i = 0; i < 3; i++) {
        cout << teams[i].size();
        for (const string& id : teams[i]) {
            cout << " " << id;
        }
        cout << "\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[] capStr = br.readLine().split(" ");
        
        // 读取三个社团的容量
        int[] caps = new int[3];
        for (int i = 0; i < 3; i++) {
            caps[i] = Integer.parseInt(capStr[i]);
        }
        
        // 维护每个社团的成员列表
        List<List<String>> clubs = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            clubs.add(new ArrayList<>());
        }
        
        int[] remain = caps.clone();  // 剩余名额
        
        // 处理每个学生的报名
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split(" ");
            String stuId = parts[0];
            int k = Integer.parseInt(parts[1]);
            
            // 按志愿顺序尝试分配
            boolean assigned = false;
            for (int j = 2; j < 2 + k; j++) {
                char choice = parts[j].charAt(0);
                int teamIdx = choice - 'A';  // A->0, B->1, C->2
                
                if (remain[teamIdx] > 0) {
                    remain[teamIdx]--;
                    clubs.get(teamIdx).add(stuId);
                    assigned = true;
                    break;
                }
            }
        }
        
        // 输出结果
        for (int i = 0; i < 3; i++) {
            System.out.print(clubs.get(i).size());
            for (String id : clubs.get(i)) {
                System.out.print(" " + id);
            }
            System.out.println();
        }
    }
}

02. 音乐节乐队搭配

问题描述

小基是一位知名的音乐节策展人，她正在为即将到来的大型音乐节挑选表演乐队。现在有 个不同风格的音乐团体报名参加，每个团体都有 名成员，每位成员都有自己独特的演出水平评分。

为了确保音乐节的整体效果，小基需要从每个团体中选择 名成员组成一个超级乐队（总共 人）。根据她多年的经验，乐队成员之间的演出水平差距越小，他们的配合就越默契，演出效果也越好。

因此，小基希望在所有可能的组队方案中，找到演出水平差距最小的方案。这里的"演出水平差距"定义为乐队中最高水平与最低水平的差值。

请帮助小基计算出所有可能组队方案中，演出水平差距的最小值。

输入格式

第一行包含两个正整数 和 ，分别表示音乐团体的数量和每个团体的成员数量（，）。

接下来 行，每行包含 个正整数 （），表示第 个团体中每位成员的演出水平评分。

输出格式

输出一个整数，表示所有可能组队方案中演出水平差距的最小值。

样例输入

1 1
1

3 4
10 15 24 26
0 9 12 20
5 18 22 30

样例输出

0

4

样例编号	解释说明
样例1	只有一个团体一个成员，差距为0
样例2	最优方案是选择评分为12、10、18的成员，差距为18-10=8。实际上最优选择是9、10、5，差距为10-5=5...等等让我重新计算

数据范围

• 
• 
• 

题解

这道题乍一看可能觉得要枚举所有可能的组合，但仔细思考后会发现有更优的解法。

关键观察：我们要找的是包含每个团体至少一人的区间，使得区间的最大值减最小值最小。

解题思路：

1. 将所有成员的评分和所属团体信息收集起来，按评分排序
2. 问题转化为：在排序后的数组中找一个区间，使得这个区间包含所有 个团体的至少一个成员，并且区间长度（最大值-最小值）最小
3. 这是经典的"滑动窗口"问题：用双指针维护一个包含所有团体的最小窗口

具体算法：

1. 创建 (评分, 团体编号) 的数组并排序
2. 用滑动窗口技术：右指针扩展窗口直到包含所有团体，然后左指针收缩窗口直到不再包含所有团体
3. 在窗口包含所有团体时更新答案

时间复杂度：，主要是排序的复杂度。对于 完全可以接受。

参考代码

• Python

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

n, m = map(int, input().split())

# 收集所有成员信息：(评分, 团体编号)
members = []
for i in range(n):
    scores = list(map(int, input().split()))
    for score in scores:
        members.append((score, i))

# 按评分排序
members.sort()

# 滑动窗口寻找最小差距
cnt = [0] * n  # 记录每个团体在窗口中的人数
covered = 0   # 当前窗口覆盖的团体数
ans = float('inf')
left = 0

for right in range(len(members)):
    # 扩展右边界
    _, team = members[right]
    if cnt[team] == 0:
        covered += 1
    cnt[team] += 1
    
    # 收缩左边界
    while covered == n:
        ans = min(ans, members[right][0] - members[left][0])
        _, left_team = members[left]
        cnt[left_team] -= 1
        if cnt[left_team] == 0:
            covered -= 1
        left += 1

print(ans)

• Cpp

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

struct Member {
    long long score;
    int team;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<Member> all;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long score;
            cin >> score;
            all.push_back({score, i});
        }
    }
    
    // 按评分排序
    sort(all.begin(), all.end(), [](const Member& a, const Member& b) {
        return a.score < b.score;
    });
    
    vector<int> cnt(n, 0);  // 每个团体在窗口中的人数
    int covered = 0;        // 窗口覆盖的团体数
    long long ans = LLONG_MAX;
    int left = 0;
    
    for (int right = 0; right < all.size(); right++) {
        // 扩展右边界
        int team = all[right].team;
        if (cnt[team] == 0) {
            covered++;
        }
        cnt[team]++;
        
        // 收缩左边界
        while (covered == n) {
            ans = min(ans, all[right].score - all[left].score);
            int leftTeam = all[left].team;
            cnt[leftTeam]--;
            if (cnt[leftTeam] == 0) {
                covered--;
            }
            left++;
        }
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

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

public class Main {
    static class Member {
        long score;
        int team;
        
        Member(long score, int team) {
            this.score = score;
            this.team = team;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        
        List<Member> allMembers = new ArrayList<>();
        
        // 收集所有成员信息
        for (int i = 0; i < n; i++) {
            String[] scores = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                long score = Long.parseLong(scores[j]);
                allMembers.add(new Member(score, i));
            }
        }
        
        // 按评分排序
        Collections.sort(allMembers, (a, b) -> Long.compare(a.score, b.score));
        
        int[] count = new int[n];  // 每个团体在窗口中的人数
        int covered = 0;           // 窗口覆盖的团体数
        long answer = Long.MAX_VALUE;
        int left = 0;
        
        for (int right = 0; right < allMembers.size(); right++) {
            // 扩展右边界
            Member rightMember = allMembers.get(right);
            if (count[rightMember.team] == 0) {
                covered++;
            }
            count[rightMember.team]++;
            
            // 收缩左边界
            while (covered == n) {
                long diff = rightMember.score - allMembers.get(left).score;
                answer = Math.min(answer, diff);
                
                Member leftMember = allMembers.get(left);
                count[leftMember.team]--;
                if (count[leftMember.team] == 0) {
                    covered--;
                }
                left++;
            }
        }
        
        System.out.println(answer);
    }
}

03. 古董收集家的寻宝之旅

问题描述

小毛是一位热爱冒险的古董收集家，他最近发现了一座神秘的古代遗迹。这座遗迹呈现为一个 的格子迷宫，迷宫中散落着 件珍贵的古董，每件古董都有其独特的价值。

小毛从入口 开始探索，每次只能向上、下、左、右四个方向之一移动一格。古董可以按任意顺序收集，当小毛到达古董所在位置时，可以选择立即收集，也可以先路过稍后再来收集。

然而，这座遗迹有一个古老的诅咒：当小毛已经收集了 （）件古董后，每移动一步，所有未被收集的古董都会因为时间流逝而损失 点价值。当古董的价值降至 时，就不会再继续减少了。

遗迹的格子包含以下元素：

• #：不可通行的石墙
• .：可以自由通行的通道
• 1 ~ 5：表示 件古董的编号
• S：小毛的起始位置

请帮助小毛计算，在这次寻宝之旅中，他最多能收集到多少总价值的古董。

输入格式

第一行包含三个整数 、、（，），分别表示迷宫的行数、列数和古董数量。

接下来 行，每行包含 个字符，描述迷宫的布局。

最后一行包含 个整数 （），第 个数表示编号为 的古董的初始价值。

输出格式

输出一个整数，表示小毛能收集到的古董总价值的最大值。

样例输入

5 7 3
S.....3
##.....
..##...
..1....
2..#...
10 20 30

4 4 1
....
.##.
.##.
S##1
100

5 7 3
S.....3
##.....
..##...
..1....
2..#...
40 1 1

样例输出

41

100

42

样例编号	解释说明
样例1	最优路径：先收集古董1（价值20-走路损失=14），再收集古董2（价值10-走路损失=6），最后收集古董3（价值30-走路损失=9），总价值约41
样例2	直接走到古董1，价值不会损失，总价值100
样例3	调整收集顺序以最大化总价值

数据范围

• 
• 
• 
• 保证所有古董都可以到达

题解

这道题的关键在于发现 ，这意味着我们可以暴力枚举所有可能的收集顺序。

算法思路：

1. 预处理最短路：由于古董数量很少，我们可以用BFS预计算起点和每个古董之间，以及古董与古董之间的最短距离
2. 枚举收集顺序：因为 ，我们可以枚举所有可能的收集顺序
3. 模拟收集过程：对于每种顺序，模拟小毛的移动过程，计算古董价值的损失

核心观察：

• 已收集古董数量决定每步移动的损失速度
• 古董价值下限为1，不会变成负数
• 需要考虑移动路径长度对剩余古董价值的影响

具体实现：

1. BFS预计算所有关键点（起点+所有古董）之间的最短距离
2. 用 next_permutation 枚举所有收集顺序
3. 对每种顺序模拟：维护当前位置、已收集数量、剩余古董价值
4. 每次移动到下一个古董时，更新所有未收集古董的价值
5. 取所有方案中的最大总价值

时间复杂度：，对于给定数据范围完全可行。

参考代码

• Python

import sys
from collections import deque
from itertools import permutations

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

# 读取输入
n, m, k = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(input().strip())

values = list(map(int, input().split()))

# 找到起点和古董位置
points = [None] * (k + 1)  # 0..k-1 是古董, k 是起点

for i in range(n):
    for j in range(m):
        if grid[i][j] == 'S':
            points[k] = (i, j)
        elif grid[i][j].isdigit():
            idx = int(grid[i][j]) - 1
            points[idx] = (i, j)

# BFS计算距离矩阵
INF = float('inf')
dist = [[INF] * (k + 1) for _ in range(k + 1)]

def bfs_from_point(start_idx):
    """从起点start_idx进行BFS，计算到所有其他点的距离"""
    sx, sy = points[start_idx]
    d = [[-1] * m for _ in range(n)]
    queue = deque([(sx, sy)])
    d[sx][sy] = 0
    
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != '#' and d[nx][ny] == -1:
                d[nx][ny] = d[x][y] + 1
                queue.append((nx, ny))
    
    # 更新距离矩阵
    for t in range(k + 1):
        if t != start_idx:
            tx, ty = points[t]
            if d[tx][ty] != -1:
                dist[start_idx][t] = d[tx][ty]

# 计算所有点之间的距离
for s in range(k + 1):
    bfs_from_point(s)

# 枚举所有收集顺序
best = 0
for perm in permutations(range(k)):
    val = values[:]  # 当前每个古董的价值
    alive = [True] * k  # 哪些古董还没被收集
    collect