2025年中科大计算机复试机试过去一周了陆续有学弟学妹把题目拼凑出来找我复盘。帮他们逐题讲思路、调代码的过程中我越发觉得这套回忆版真题对下一届备考的人参考价值很大。这篇就按今年机试的主要题型把从读题到写出AC代码的完整推导过程整理出来每道题都给出可直接上手的C实现。文章适合两类人一类是准备中科大或其他985高校计算机复试的考生想搞清楚机试到底考什么、怎么练另一类是初试刚结束、正在纠结要不要花时间突击机试的同学——复试机试往往就是最后拉开排名的地方。1. 复试机试全貌考察重点与实战环境1.1 今年机试的题型分布与考察逻辑中科大计算机学院的复试机试往年一般是4到6道题时间两到三个小时用在线评测系统当场判分。今年考生反馈的题目覆盖了四类核心算法字符串与模拟、图论中的DAG最长路、动态规划里的分组背包以及二分答案。这个分布并不意外它基本反映了复试机试的考察逻辑不是让你默写哪个高深算法板子而是看你能不能把常见算法灵活用到具体场景里。一个很明显的变化是今年第一题就不是纯裸题而是字符串压缩展开题目长、输入格式绕很多人光读题就花了十分钟。后面几道题虽然算法本身不冷门但都需要先做一步建模转换。比如任务依赖那道题如果不把项目完成时间映射到DAG最长路直接套最短路径模板就容易走偏。这说明复试机试越来越看重读题-抽象-建模-编码这条完整链条而不是只会刷模板题。另外我注意到今年题目的数据范围都出得有讲究。字符串题长度不超过200朴素解答完全能过但图论的题目点数到了10万逼着你必须用邻接表加拓扑序DP不能用邻接矩阵。这种藏在数据范围里的提示其实是出题人在暗示你使用什么复杂度的算法。读题时把数据范围圈出来是拿到高分的第一步。1.2 考试环境、评分规则与备赛方向中科大复试机试一般是在Linux环境下进行主流语言是C/C评测系统类似OJ代码只对若干组测试数据判分。这意味着两个实战要点第一不要依赖IDE的自动补全考场里你基本就是对着一个编辑器写代码练手的时候就要习惯手写STL头文件和main函数第二判分不是结果对了就满分多个测试点里可能有大样例、边界样例你要保证的是在所有数据下都能跑出正确结果而不是只在示例数据上正确。评分规则上通常按通过的测试点给分部分正确也有分。所以考场策略应该是先做最有把握的题拿到保底分再回头啃难题。从准备方向看我建议把复习优先级排成字符串/模拟 搜索与图论基础 动态规划基础 二分答案与贪心 数学/数论。字符串和模拟永远是机试的基本盘代码量大、边界多练的是手感和细心图论重在建模DFS/BFS、拓扑排序、最短路径必须熟练到条件反射DP掌握背包、最长上升子序列、区间DP、树形DP这类高频模型就够了。2. 高频题型破题思路与算法选型2.1 字符串与模拟题细节决定成败字符串题在机试里出现的频率之高超出很多人想象。它不考复杂算法考的是你对字符读入、字符串拼接、嵌套结构、边界条件这些基本功的掌握程度。今年那道字符串压缩展开题典型特征是有嵌套方括号和多位数字例如3[a2[c]]。这种题一旦处理不好数字的位数、栈的压入弹出顺序很容易写出看着挺对但样例就是过不了的代码。处理这类题我的习惯是先明确几个子问题数字怎么解析、方括号怎么配对、展开的字符串临时存放在哪里、一个层级的括号结束后如何拼回上一层。把这些子问题拆开就会发现栈这个数据结构几乎是天然答案。数字栈用来存重复次数字符串栈用来存方括号前的已生成内容然后一边遍历一边维护当前层的字符串。细节上特别注意数字可能是两位数甚至三位数必须用num num * 10 (c - 0)的方式累积不能用单个字符去处理。模拟题还有一个通用技巧先把样例数据在纸上走一遍把每一步的中间状态写出来再对照代码打调试输出。很多同学一上来就写代码结果调了半小时查不出错就是因为脑子里的执行路径本来就是乱的。纸上推演成本很低在机试中却能省下大量无效调试时间强烈推荐养成这个习惯。2.2 图论与搜索先想清楚建模再动手图论题在机试里不是难在算法而是难在建模。今年那道任务依赖题表面上问一个项目所有任务完成需要的最短时间听起来像关键路径或最短路径实际上抽象成图以后就是DAG上的最长路。每个任务是一个点任务之间的先后依赖是有向边任务完成时间是点权那么整个项目的最早完成时间就是所有路径里累计时间最长的那条。为什么会是最长路而不是最短路因为一个任务必须等它所有的前驱任务都完成才能开始所以完成时间取决于最慢的前驱链而不是最快的。这个取最大的直觉是我在复盘时反复强调的点。具体算法上DAG上求最长路不需要写通用的SPFA直接用拓扑排序配合DP就行按拓扑序依次处理每个点用当前点的dp值去松弛它的后继节点。因为拓扑序保证了处理每个点时它所有的前驱都已经更新完了。选数据结构时如果点数到了10万邻接矩阵就别想了必须用动态数组vectorint g[N]建邻接表。有些同学清晰记得Prim、Dijkstra的板子但遇到这类题反而卡住核心原因是没建立先看数据范围、再选数据结构、最后套算法的思维。图论题的代码基本都短难得永远是动手前的那几分钟建模。2.3 动态规划状态定义是灵魂动态规划是复试机试的压轴常客也是很多同学最头疼的部分。今年考到的分组背包本质是背包九讲里的基础模型但换了一个团队项目选型的场景很多人就认不出来了。这再次说明背模板虽然重要更重要的是理解状态和转移的含义。以分组背包为例题目通常是这样每个组件属于一个分组每组最多选一个组件背包容量有限问能获得的最大价值。状态定义和普通01背包完全一致dp[j]表示当前考虑了前若干组之后容量为 j 时能获得的最大价值。转移的区别在于普通01背包是每个物品选或不选分组背包是每组内选择一个物品或者一个都不选。实现上的关键坑是循环顺序。很多人把容量循环和组内物品循环写反导致同一组内选了两个物品。正确写法一定是外层枚举组中间层倒序枚举容量内层枚举该组内的物品。容量倒序的目的是保证每个容量只被当前组更新一次不会从本组已经更新过的状态再次转移过去。这个为什么倒序的问题我在辅导时每次都会追问能讲清楚的同学遇到再变种的背包题也不会慌。3. 真题手把手复盘从读题到AC完整走一遍3.1 字符串解压栈模拟解决嵌套展开题目描述回忆版给出一个字符串由小写字母、数字和方括号组成规则和常见压缩算法一致例如3[a2[c]]展开得到accaccacc。保证括号嵌套合法数字只表示重复次数且没有前导零。输出展开后的完整字符串。解题思路从左到右扫描字符串用两个栈维护状态。数字栈cnt存遇到[时的重复次数字符串栈pre存该层括号之前已经拼好的字符串。维护一个当前层字符串cur和一个当前数字累加器num。遇到数字就累加遇到[就把当前数字和当前字符串压栈并清空遇到]就弹出数字和之前的字符串把当前层字符串重复若干次后拼接到之前的字符串后面普通字母直接追加到cur。AC代码#include bits/stdc.h using namespace std; int main() { string s; cin s; stackint cnt; // 重复次数 stackstring pre; // 之前已生成的字符串 string cur; // 当前层字符串 int num 0; // 当前数字 for (char c : s) { if (isdigit(c)) { num num * 10 (c - 0); } else if (c [) { cnt.push(num); pre.push(cur); num 0; cur.clear(); } else if (c ]) { int k cnt.top(); cnt.pop(); string prev pre.top(); pre.pop(); string tmp; for (int i 0; i k; i) tmp cur; cur prev tmp; } else { cur c; } } cout cur endl; return 0; }复盘要点这个题最大的坑是num的清零时机。每处理完一个[都要重置为0否则后面的数字会不断累加。另一个坑是[之后可能有多个字母再嵌套下一层[此时cur里已经有一段字符串压栈时要保证它完整保留出栈后拼回。代码里prev pre.top()还要注意别把顺序写反应该是之前的字符串 当前层重复后的内容。当时有考生卡在最后输出的字符串顺序上其实就是这个小细节。3.2 软件构建耗时拓扑排序与DAG最长路题目描述回忆版一个软件项目由 N 个任务组成每个任务编号从 0 到 N-1完成第 i 个任务需要cost[i]天。任务之间存在依赖关系输入 M 对关系(u, v)表示任务 u 必须在任务 v 开始之前完成。数据保证依赖关系不会成环。求整个项目最早可以在第几天完成。解题思路把任务看成点依赖关系看成有向边 u - v这就构成一个DAG。每个任务的最早完成时间dp[i]应该取所有前驱任务完成的最晚时间加上自己的耗时。因为任务 v 要等所有前驱都做完才能开工所以最慢的那个前驱决定了 v 最早什么时候能完成。拓扑排序天然的保证当一个任务出队时它的所有前驱都已经处理完毕此时再向后继节点更新一定是对的。AC代码#include bits/stdc.h using namespace std; int main() { int N, M; cin N M; vectorint cost(N); for (int i 0; i N; i) cin cost[i]; vectorvectorint g(N); vectorint indeg(N, 0); for (int i 0; i M; i) { int u, v; cin u v; g[u].push_back(v); indeg[v]; } vectorint dp(N, 0); queueint q; for (int i 0; i N; i) { dp[i] cost[i]; if (indeg[i] 0) q.push(i); } int ans 0; while (!q.empty()) { int u q.front(); q.pop(); ans max(ans, dp[u]); for (int v : g[u]) { dp[v] max(dp[v], dp[u] cost[v]); if (--indeg[v] 0) { q.push(v); } } } cout ans endl; return 0; }复盘要点我把这道题讲给学弟听时他第一反应是最短路径。我让他手动算一个简单例子任务A耗时3任务B耗时5C依赖A和B则C最早完成时间是 max(3,5)C的耗时从起点到终点的最短路径在这里毫无意义最长路径才符合约束。这个转换想通了代码反而就是模板。另外dp[i]初始化为cost[i]很关键这让没有前驱的任务直接有了基础值而不是从0开始导致答案偏小。3.3 团队项目选型分组背包的转移顺序题目描述回忆版你需要为项目选一批组件共有 N 个候选组件每个组件有一个所属组号、占用资源w[i]、产生价值val[i]。同一个组内最多只能选择其中一个组件总共可用的资源容量为 V。问在不超过容量的前提下能获得的最大总价值是多少。解题思路这是典型的分组背包。把组件按组号分组每组作为一个整体来处理。dp[j]表示当前容量为 j 时的最大价值。枚举组时组内最多选一个所以转移是这一组不选或者选这一组中的某一个。为了保证每组最多选一个容量 j 的倒序循环必须放在组内物品循环的外层否则同组物品之间会互相影响导致最终选了多个。AC代码#include bits/stdc.h using namespace std; int main() { int N, V; cin N V; mapint, vectorpairint, int groups; // group - {w, val} for (int i 0; i N; i) { int g, w, val; cin g w val; groups[g].push_back({w, val}); } vectorint dp(V 1, 0); for (auto p : groups) { // 容量倒序保证每个容量只被本组更新一次 for (int j V; j 0; --j) { for (auto item : p.second) { int w item.first; int val item.second; if (j w) { dp[j] max(dp[j], dp[j - w] val); } } } } cout dp[V] endl; return 0; }复盘要点这个代码量很小但循环顺序写错就会变成另一种错误模型。如果先枚举组内物品、再倒序容量组内第一个物品更新后的dp可能会被第二个物品当作上一次已经确定的旧状态来用等于允许一组选两个。这也是为什么很多人背了板子上考场依然错他们不理解倒序的真正作用是每轮转移只使用上一轮的状态。用mapint, vectorpairint,int分组是考场中最省心的做法不用管组号是否连续排序问题也省了。3.4 最小化最大值二分答案的检查函数设计题目描述回忆版给定长度为 N 的非负整数数组 A要把它依次划分成 K 个连续子段。定义一种划分方案的开销为这 K 个子段各自元素和的最大值。求所有划分方案中开销最小是多少。解题思路这道题属于典型的最小化最大值问题看到这种描述应该条件反射想到二分答案。二分一个答案 x检查能否把数组分成至多 K 段使得每一段的元素和都不超过 x。检查时用贪心从左往右累加当前段和超过 x 就立刻开新段最后统计段数是否小于等于 K。这个检查函数是贪心正确的因为让每段尽量长、段数尽量少最有利于满足不超过K段的条件所以存在可行方案当且仅当贪心得到的段数不超过K。二分下界是数组元素最大值上界是数组总和。AC代码#include bits/stdc.h using namespace std; int main() { int N, K; cin N K; vectorint a(N); long long low 0, high 0; for (int i 0; i N; i) { cin a[i]; low max(low, (long long)a[i]); high a[i]; } auto check [](long long x) { int cnt 1; long long cur 0; for (int i 0; i N; i) { if (cur a[i] x) { cnt; cur a[i]; } else { cur a[i]; } } return cnt K; }; while (low high) { long long mid (low high) / 2; if (check(mid)) high mid; else low mid 1; } cout low endl; return 0; }复盘要点这道题真正容易错的地方不是二分而是检查函数里的边界。如果遇到一个元素本身大于 x那么无论怎么分都不可能成功但我们的下界已经保证 x 不小于最大元素所以这种情况不会出现。另一个容易错的是cnt的初始值应该从1而不是0开始因为数组至少会被分成一段。我把这题放在最后是因为它体现了一种从答案反过来验证的思考方式这种能力在复试机试里越来越重要。4. 考场实战的调试技巧与避坑手册4.1 从TLE到AC的优化习惯很多同学在牛客、力扣上刷题时习惯了平台给你的便利但复试机试现场是没有那么多友好提示的。第一输入输出量大的时候cin加sync_with_stdio(false)通常够用但如果还超时就把输入换成scanf甚至自己写快读。字符串题里频繁用string拼接也要注意大量循环内做cur cur c会产生很多临时对象可以用cur c来避免额外拷贝。第二写完第一版后不要急着交花一分钟看数据范围算复杂度。N1000 双重循环可以N100000 就必须优化到 O(N log N) 或 O(N)。今年那题 DAG 最长路如果有人用了邻接矩阵或者 Floyd光初始化矩阵就已经爆内存了。这种优化不是技巧问题而是习惯问题考场时间越紧张越容易乱。第三对拍是最有效的调试手段。机试前自己准备一个小脚本或者在本地写两份代码一份暴力一份优化跑随机小数据比较结果。我辅导学生时经常说面向样例编程只能保证不零分面向对拍才能保证AC。这个习惯没法在复试现场临时养成一定要在平时练题时就用起来。4.2 高频Bug与排查思路考场里最常见的错误我把它们整理成一张速查表错误类型典型表现排查思路数组越界本地跑正常OJ运行错误(RE)检查所有数组下标是否可能取到负数或 N初始化遗漏多组数据时第二组答案出错重点检查循环内的sum、cnt、cur是否重置类型溢出大数相加变成负数涉及和的变量统一用long long循环顺序写反背包类题目结果偏大检查容量循环是否倒序、是否在组内物品外层EOF读入处理输入不止一组程序只跑了第一组用while (cin n)包裹主逻辑这里我想单独展开说下数组越界。复试机试的评测数据里边界样例几乎一定会出现。比如 N1 的数组、最多层嵌套的括号、K1 的划分。很多代码在主样例上没问题一到这种边界就崩。我的建议是写完核心逻辑后先想三个边界最小规模、最大规模、所有元素相同的特殊情况然后手动在脑子里跑一遍或者直接用这几组数据测试代码。这个习惯能帮你躲掉机试里至少一半的坑。调试输出也是一个双刃剑。考场里可以用printf或cout打印中间量但交卷前一定要记得删掉调试语句否则大量多出来的输出会导致格式错误直接零分。我见过不止一个考生因为忘了删调试输出在一道会做的题上丢了全部分数这真的是最冤的失败方式。5. 写在最后机试准备的几点体会每年复试季总有人问我机试到底该投入多少时间。我自己的体会是机试是一个性价比很高的复试环节。初试分数高不代表机试一定强很多考生初试后完全放飞结果机试现场连链式前向星都写不顺最后被反超。反过来只要花三到四周每天坚持刷两三道高频题把代码模板内化成肌肉记忆机试成绩就能有一个很明显的提升。如果只让我留一条建议那就是别背代码背思考方式。3[a2[c]]考的从来不是栈的API而是遇到嵌套结构就用栈的意识任务依赖考的不是拓扑排序板子而是把依赖关系想成有向图、把最慢前驱传下去的建模能力。把每道题都当成建模练习来做复试机试就不再是玄学而是可以稳稳拿下的分数。希望这篇复盘能帮到你明年考场见。 
长河君 · 2026/9/30 5:00:11 · 阅读 1.2k 2025中科大复试机试复盘：四大算法题型与AC代码全解析
2025年中科大计算机复试机试过去一周了陆续有学弟学妹把题目拼凑出来找我复盘。帮他们逐题讲思路、调代码的过程中我越发觉得这套回忆版真题对下一届备考的人参考价值很大。这篇就按今年机试的主要题型把从读题到写出AC代码的完整推导过程整理出来每道题都给出可直接上手的C实现。文章适合两类人一类是准备中科大或其他985高校计算机复试的考生想搞清楚机试到底考什么、怎么练另一类是初试刚结束、正在纠结要不要花时间突击机试的同学——复试机试往往就是最后拉开排名的地方。1. 复试机试全貌考察重点与实战环境1.1 今年机试的题型分布与考察逻辑中科大计算机学院的复试机试往年一般是4到6道题时间两到三个小时用在线评测系统当场判分。今年考生反馈的题目覆盖了四类核心算法字符串与模拟、图论中的DAG最长路、动态规划里的分组背包以及二分答案。这个分布并不意外它基本反映了复试机试的考察逻辑不是让你默写哪个高深算法板子而是看你能不能把常见算法灵活用到具体场景里。一个很明显的变化是今年第一题就不是纯裸题而是字符串压缩展开题目长、输入格式绕很多人光读题就花了十分钟。后面几道题虽然算法本身不冷门但都需要先做一步建模转换。比如任务依赖那道题如果不把项目完成时间映射到DAG最长路直接套最短路径模板就容易走偏。这说明复试机试越来越看重读题-抽象-建模-编码这条完整链条而不是只会刷模板题。另外我注意到今年题目的数据范围都出得有讲究。字符串题长度不超过200朴素解答完全能过但图论的题目点数到了10万逼着你必须用邻接表加拓扑序DP不能用邻接矩阵。这种藏在数据范围里的提示其实是出题人在暗示你使用什么复杂度的算法。读题时把数据范围圈出来是拿到高分的第一步。1.2 考试环境、评分规则与备赛方向中科大复试机试一般是在Linux环境下进行主流语言是C/C评测系统类似OJ代码只对若干组测试数据判分。这意味着两个实战要点第一不要依赖IDE的自动补全考场里你基本就是对着一个编辑器写代码练手的时候就要习惯手写STL头文件和main函数第二判分不是结果对了就满分多个测试点里可能有大样例、边界样例你要保证的是在所有数据下都能跑出正确结果而不是只在示例数据上正确。评分规则上通常按通过的测试点给分部分正确也有分。所以考场策略应该是先做最有把握的题拿到保底分再回头啃难题。从准备方向看我建议把复习优先级排成字符串/模拟 搜索与图论基础 动态规划基础 二分答案与贪心 数学/数论。字符串和模拟永远是机试的基本盘代码量大、边界多练的是手感和细心图论重在建模DFS/BFS、拓扑排序、最短路径必须熟练到条件反射DP掌握背包、最长上升子序列、区间DP、树形DP这类高频模型就够了。2. 高频题型破题思路与算法选型2.1 字符串与模拟题细节决定成败字符串题在机试里出现的频率之高超出很多人想象。它不考复杂算法考的是你对字符读入、字符串拼接、嵌套结构、边界条件这些基本功的掌握程度。今年那道字符串压缩展开题典型特征是有嵌套方括号和多位数字例如3[a2[c]]。这种题一旦处理不好数字的位数、栈的压入弹出顺序很容易写出看着挺对但样例就是过不了的代码。处理这类题我的习惯是先明确几个子问题数字怎么解析、方括号怎么配对、展开的字符串临时存放在哪里、一个层级的括号结束后如何拼回上一层。把这些子问题拆开就会发现栈这个数据结构几乎是天然答案。数字栈用来存重复次数字符串栈用来存方括号前的已生成内容然后一边遍历一边维护当前层的字符串。细节上特别注意数字可能是两位数甚至三位数必须用num num * 10 (c - 0)的方式累积不能用单个字符去处理。模拟题还有一个通用技巧先把样例数据在纸上走一遍把每一步的中间状态写出来再对照代码打调试输出。很多同学一上来就写代码结果调了半小时查不出错就是因为脑子里的执行路径本来就是乱的。纸上推演成本很低在机试中却能省下大量无效调试时间强烈推荐养成这个习惯。2.2 图论与搜索先想清楚建模再动手图论题在机试里不是难在算法而是难在建模。今年那道任务依赖题表面上问一个项目所有任务完成需要的最短时间听起来像关键路径或最短路径实际上抽象成图以后就是DAG上的最长路。每个任务是一个点任务之间的先后依赖是有向边任务完成时间是点权那么整个项目的最早完成时间就是所有路径里累计时间最长的那条。为什么会是最长路而不是最短路因为一个任务必须等它所有的前驱任务都完成才能开始所以完成时间取决于最慢的前驱链而不是最快的。这个取最大的直觉是我在复盘时反复强调的点。具体算法上DAG上求最长路不需要写通用的SPFA直接用拓扑排序配合DP就行按拓扑序依次处理每个点用当前点的dp值去松弛它的后继节点。因为拓扑序保证了处理每个点时它所有的前驱都已经更新完了。选数据结构时如果点数到了10万邻接矩阵就别想了必须用动态数组vectorint g[N]建邻接表。有些同学清晰记得Prim、Dijkstra的板子但遇到这类题反而卡住核心原因是没建立先看数据范围、再选数据结构、最后套算法的思维。图论题的代码基本都短难得永远是动手前的那几分钟建模。2.3 动态规划状态定义是灵魂动态规划是复试机试的压轴常客也是很多同学最头疼的部分。今年考到的分组背包本质是背包九讲里的基础模型但换了一个团队项目选型的场景很多人就认不出来了。这再次说明背模板虽然重要更重要的是理解状态和转移的含义。以分组背包为例题目通常是这样每个组件属于一个分组每组最多选一个组件背包容量有限问能获得的最大价值。状态定义和普通01背包完全一致dp[j]表示当前考虑了前若干组之后容量为 j 时能获得的最大价值。转移的区别在于普通01背包是每个物品选或不选分组背包是每组内选择一个物品或者一个都不选。实现上的关键坑是循环顺序。很多人把容量循环和组内物品循环写反导致同一组内选了两个物品。正确写法一定是外层枚举组中间层倒序枚举容量内层枚举该组内的物品。容量倒序的目的是保证每个容量只被当前组更新一次不会从本组已经更新过的状态再次转移过去。这个为什么倒序的问题我在辅导时每次都会追问能讲清楚的同学遇到再变种的背包题也不会慌。3. 真题手把手复盘从读题到AC完整走一遍3.1 字符串解压栈模拟解决嵌套展开题目描述回忆版给出一个字符串由小写字母、数字和方括号组成规则和常见压缩算法一致例如3[a2[c]]展开得到accaccacc。保证括号嵌套合法数字只表示重复次数且没有前导零。输出展开后的完整字符串。解题思路从左到右扫描字符串用两个栈维护状态。数字栈cnt存遇到[时的重复次数字符串栈pre存该层括号之前已经拼好的字符串。维护一个当前层字符串cur和一个当前数字累加器num。遇到数字就累加遇到[就把当前数字和当前字符串压栈并清空遇到]就弹出数字和之前的字符串把当前层字符串重复若干次后拼接到之前的字符串后面普通字母直接追加到cur。AC代码#include bits/stdc.h using namespace std; int main() { string s; cin s; stackint cnt; // 重复次数 stackstring pre; // 之前已生成的字符串 string cur; // 当前层字符串 int num 0; // 当前数字 for (char c : s) { if (isdigit(c)) { num num * 10 (c - 0); } else if (c [) { cnt.push(num); pre.push(cur); num 0; cur.clear(); } else if (c ]) { int k cnt.top(); cnt.pop(); string prev pre.top(); pre.pop(); string tmp; for (int i 0; i k; i) tmp cur; cur prev tmp; } else { cur c; } } cout cur endl; return 0; }复盘要点这个题最大的坑是num的清零时机。每处理完一个[都要重置为0否则后面的数字会不断累加。另一个坑是[之后可能有多个字母再嵌套下一层[此时cur里已经有一段字符串压栈时要保证它完整保留出栈后拼回。代码里prev pre.top()还要注意别把顺序写反应该是之前的字符串 当前层重复后的内容。当时有考生卡在最后输出的字符串顺序上其实就是这个小细节。3.2 软件构建耗时拓扑排序与DAG最长路题目描述回忆版一个软件项目由 N 个任务组成每个任务编号从 0 到 N-1完成第 i 个任务需要cost[i]天。任务之间存在依赖关系输入 M 对关系(u, v)表示任务 u 必须在任务 v 开始之前完成。数据保证依赖关系不会成环。求整个项目最早可以在第几天完成。解题思路把任务看成点依赖关系看成有向边 u - v这就构成一个DAG。每个任务的最早完成时间dp[i]应该取所有前驱任务完成的最晚时间加上自己的耗时。因为任务 v 要等所有前驱都做完才能开工所以最慢的那个前驱决定了 v 最早什么时候能完成。拓扑排序天然的保证当一个任务出队时它的所有前驱都已经处理完毕此时再向后继节点更新一定是对的。AC代码#include bits/stdc.h using namespace std; int main() { int N, M; cin N M; vectorint cost(N); for (int i 0; i N; i) cin cost[i]; vectorvectorint g(N); vectorint indeg(N, 0); for (int i 0; i M; i) { int u, v; cin u v; g[u].push_back(v); indeg[v]; } vectorint dp(N, 0); queueint q; for (int i 0; i N; i) { dp[i] cost[i]; if (indeg[i] 0) q.push(i); } int ans 0; while (!q.empty()) { int u q.front(); q.pop(); ans max(ans, dp[u]); for (int v : g[u]) { dp[v] max(dp[v], dp[u] cost[v]); if (--indeg[v] 0) { q.push(v); } } } cout ans endl; return 0; }复盘要点我把这道题讲给学弟听时他第一反应是最短路径。我让他手动算一个简单例子任务A耗时3任务B耗时5C依赖A和B则C最早完成时间是 max(3,5)C的耗时从起点到终点的最短路径在这里毫无意义最长路径才符合约束。这个转换想通了代码反而就是模板。另外dp[i]初始化为cost[i]很关键这让没有前驱的任务直接有了基础值而不是从0开始导致答案偏小。3.3 团队项目选型分组背包的转移顺序题目描述回忆版你需要为项目选一批组件共有 N 个候选组件每个组件有一个所属组号、占用资源w[i]、产生价值val[i]。同一个组内最多只能选择其中一个组件总共可用的资源容量为 V。问在不超过容量的前提下能获得的最大总价值是多少。解题思路这是典型的分组背包。把组件按组号分组每组作为一个整体来处理。dp[j]表示当前容量为 j 时的最大价值。枚举组时组内最多选一个所以转移是这一组不选或者选这一组中的某一个。为了保证每组最多选一个容量 j 的倒序循环必须放在组内物品循环的外层否则同组物品之间会互相影响导致最终选了多个。AC代码#include bits/stdc.h using namespace std; int main() { int N, V; cin N V; mapint, vectorpairint, int groups; // group - {w, val} for (int i 0; i N; i) { int g, w, val; cin g w val; groups[g].push_back({w, val}); } vectorint dp(V 1, 0); for (auto p : groups) { // 容量倒序保证每个容量只被本组更新一次 for (int j V; j 0; --j) { for (auto item : p.second) { int w item.first; int val item.second; if (j w) { dp[j] max(dp[j], dp[j - w] val); } } } } cout dp[V] endl; return 0; }复盘要点这个代码量很小但循环顺序写错就会变成另一种错误模型。如果先枚举组内物品、再倒序容量组内第一个物品更新后的dp可能会被第二个物品当作上一次已经确定的旧状态来用等于允许一组选两个。这也是为什么很多人背了板子上考场依然错他们不理解倒序的真正作用是每轮转移只使用上一轮的状态。用mapint, vectorpairint,int分组是考场中最省心的做法不用管组号是否连续排序问题也省了。3.4 最小化最大值二分答案的检查函数设计题目描述回忆版给定长度为 N 的非负整数数组 A要把它依次划分成 K 个连续子段。定义一种划分方案的开销为这 K 个子段各自元素和的最大值。求所有划分方案中开销最小是多少。解题思路这道题属于典型的最小化最大值问题看到这种描述应该条件反射想到二分答案。二分一个答案 x检查能否把数组分成至多 K 段使得每一段的元素和都不超过 x。检查时用贪心从左往右累加当前段和超过 x 就立刻开新段最后统计段数是否小于等于 K。这个检查函数是贪心正确的因为让每段尽量长、段数尽量少最有利于满足不超过K段的条件所以存在可行方案当且仅当贪心得到的段数不超过K。二分下界是数组元素最大值上界是数组总和。AC代码#include bits/stdc.h using namespace std; int main() { int N, K; cin N K; vectorint a(N); long long low 0, high 0; for (int i 0; i N; i) { cin a[i]; low max(low, (long long)a[i]); high a[i]; } auto check [](long long x) { int cnt 1; long long cur 0; for (int i 0; i N; i) { if (cur a[i] x) { cnt; cur a[i]; } else { cur a[i]; } } return cnt K; }; while (low high) { long long mid (low high) / 2; if (check(mid)) high mid; else low mid 1; } cout low endl; return 0; }复盘要点这道题真正容易错的地方不是二分而是检查函数里的边界。如果遇到一个元素本身大于 x那么无论怎么分都不可能成功但我们的下界已经保证 x 不小于最大元素所以这种情况不会出现。另一个容易错的是cnt的初始值应该从1而不是0开始因为数组至少会被分成一段。我把这题放在最后是因为它体现了一种从答案反过来验证的思考方式这种能力在复试机试里越来越重要。4. 考场实战的调试技巧与避坑手册4.1 从TLE到AC的优化习惯很多同学在牛客、力扣上刷题时习惯了平台给你的便利但复试机试现场是没有那么多友好提示的。第一输入输出量大的时候cin加sync_with_stdio(false)通常够用但如果还超时就把输入换成scanf甚至自己写快读。字符串题里频繁用string拼接也要注意大量循环内做cur cur c会产生很多临时对象可以用cur c来避免额外拷贝。第二写完第一版后不要急着交花一分钟看数据范围算复杂度。N1000 双重循环可以N100000 就必须优化到 O(N log N) 或 O(N)。今年那题 DAG 最长路如果有人用了邻接矩阵或者 Floyd光初始化矩阵就已经爆内存了。这种优化不是技巧问题而是习惯问题考场时间越紧张越容易乱。第三对拍是最有效的调试手段。机试前自己准备一个小脚本或者在本地写两份代码一份暴力一份优化跑随机小数据比较结果。我辅导学生时经常说面向样例编程只能保证不零分面向对拍才能保证AC。这个习惯没法在复试现场临时养成一定要在平时练题时就用起来。4.2 高频Bug与排查思路考场里最常见的错误我把它们整理成一张速查表错误类型典型表现排查思路数组越界本地跑正常OJ运行错误(RE)检查所有数组下标是否可能取到负数或 N初始化遗漏多组数据时第二组答案出错重点检查循环内的sum、cnt、cur是否重置类型溢出大数相加变成负数涉及和的变量统一用long long循环顺序写反背包类题目结果偏大检查容量循环是否倒序、是否在组内物品外层EOF读入处理输入不止一组程序只跑了第一组用while (cin n)包裹主逻辑这里我想单独展开说下数组越界。复试机试的评测数据里边界样例几乎一定会出现。比如 N1 的数组、最多层嵌套的括号、K1 的划分。很多代码在主样例上没问题一到这种边界就崩。我的建议是写完核心逻辑后先想三个边界最小规模、最大规模、所有元素相同的特殊情况然后手动在脑子里跑一遍或者直接用这几组数据测试代码。这个习惯能帮你躲掉机试里至少一半的坑。调试输出也是一个双刃剑。考场里可以用printf或cout打印中间量但交卷前一定要记得删掉调试语句否则大量多出来的输出会导致格式错误直接零分。我见过不止一个考生因为忘了删调试输出在一道会做的题上丢了全部分数这真的是最冤的失败方式。5. 写在最后机试准备的几点体会每年复试季总有人问我机试到底该投入多少时间。我自己的体会是机试是一个性价比很高的复试环节。初试分数高不代表机试一定强很多考生初试后完全放飞结果机试现场连链式前向星都写不顺最后被反超。反过来只要花三到四周每天坚持刷两三道高频题把代码模板内化成肌肉记忆机试成绩就能有一个很明显的提升。如果只让我留一条建议那就是别背代码背思考方式。3[a2[c]]考的从来不是栈的API而是遇到嵌套结构就用栈的意识任务依赖考的不是拓扑排序板子而是把依赖关系想成有向图、把最慢前驱传下去的建模能力。把每道题都当成建模练习来做复试机试就不再是玄学而是可以稳稳拿下的分数。希望这篇复盘能帮到你明年考场见。