复试OJ二刷复盘（第16篇）——机试备考走到这一步，拼的已经不是会不会写代码了。一刷求过，二刷求懂。我指的“懂”，不是背下来题解，而是拿到一道题能在十分钟内判断它考什么、复杂度要求多少、输入输出有哪些坑，以及能不能在完全不看资料的情况下把代码白纸写出来。这篇复盘笔记记录的是我在备考某高校复试机试过程中的真实状态，适合正在准备复试机试的同学、跨考计算机基础薄弱的人，也适合所有想在短时间里把算法题从“见过”变成“能写”的人。

我是从三个月前开始刷题的，最开始按标签做，链表、二叉树、图论、DP过了一遍，说实话那时候就是对着题解抄，抄完AC就关，第二天忘得干干净净。从第10篇复盘笔记开始，我强制自己不碰题解，每道题从读题、想思路、推复杂度、写码到调试，全程自己来。那是我提升最快的一个阶段。到了这第16篇，我发现自己的关注点已经从“代码怎么写”转移到了“评测系统到底怎么想、判题规则到底卡什么”这些更底层的问题上。

这篇文章我会把最近二刷中重新做透的几类题型、踩过的坑、以及复盘方法论完整梳理一遍，重点讲清楚三件事：复试OJ和普通刷题网站的差异到底在哪、三个高频考点的易错细节、以及遇到WA/TLE时一套可复现的排查流程。

1. 二刷到底在刷什么：复盘笔记的底层逻辑

1.1 一刷和二刷的本质区别

先说个反直觉的结论：一刷的AC数量是虚假的成就感，二刷的“慢”才是真实的提升。

一刷的时候，我的典型节奏是：打开题目，读题五分钟，没思路就翻题解，看到解法觉得“原来是这样”，然后照着敲一遍，提交AC，心里觉得自己会了。这种状态下，即使刷了两百道题，遇到稍微变形的新题，还是容易卡住。原因很简单——题解是别人思维的结果，不是你的思维过程。你没有经历过从题目条件到算法选择的推导链条，自然就没法迁移。

二刷的节奏完全不同。我给自己定的规则是：同一道题，即使三个月前AC过，也必须当成新题来做。先看题目，自己设计算法，估算时间复杂度，然后写代码，提交。只有提交失败或者完全卡住半小时以上，才允许翻看之前的笔记，但翻完之后要合上笔记重新写一遍。这样一轮下来，一道题平均要花一到两小时，但我能明显感觉到，代码是长在自己脑子里的。

1.2 复盘笔记编号到16，到底积累了些什么

我的复盘笔记不是简单的题解粘贴，而是有固定结构的记录，每一条包括五块内容：题目描述的关键条件、我自己写的第一版代码、错在哪——精确到哪一行哪一步、正确思路和复杂度推导、能迁移到哪些同类题。

举个例子。第14篇笔记里我记录了二叉树层序遍历的变形题——要求从下往上、从左到右输出。第一版我直接反着输出最后的结果数组，没发现层内顺序也被反转了。这个错误本身很简单，但我在笔记里记下了一个重要结论：层序遍历类题目，方向问题要在每一层处理，别在最后统一反转。到了第16篇的时候，这样的“结论性笔记”已经有二十多条，遇到类似的题，我脑子里会直接跳出对应的笔记条目。

所以说，复盘的真正价值不是记录“我做对了什么”，而是积累“我在哪里容易想错”。这个积累越厚，临场做题的稳定性就越高。

1.3 这套方法适合谁、不适合谁

适合的人是：有一定基础但正确率不稳的刷题者；离复试还剩两个月左右需要集中突破的考生；跨专业、需要快速建立算法感觉的人。

不适合的人是：刚开始学数据结构、连栈和队列都分不清的纯新手。新手阶段应该先找体系化课程把基础补上，直接上来二刷只会打击信心。另外，如果目标院校的机试难度常年停留在“冒泡排序、简单模拟”这个层级，也不需要按这个强度去刷，选做基础题就够了。

我的结论是：二刷不是给所有人准备的，它只适合那些已经“见过题”但“没吃透题”的人。恰好，复试机试考生绝大多数都属于这一类。

2. 复试OJ与刷题网站的隐藏差距：评测规则和本地环境的错位

这件事是我第8篇复盘时才彻底想明白的。之前我在主流刷题网站上做题，本地跑通、提交AC，一切都顺。直到我拿到目标院校的模拟OJ账号，第一次提交就WA，而代码在本地跑得好好的。排查了一小时，最终发现不是算法问题，而是评测环境差异导致的。从那次之后，我养成了一个习惯：在开始复习前，先搞清楚目标OJ的一切细节。

2.1 编译器和标准版本的差异

很多复试OJ是多年没升级的老系统。老版本编译器意味着什么？意味着你可能用不了C++11之后的新特性，甚至部分STL接口的行为都和现代版本有细微差别。我遇到过最典型的两个情况：

第一个，unordered_map在极老的编译环境下不可用或效率异常低。第二个，auto、范围for循环、std::stoi这类语法在某些老标准下直接编译失败。解决办法很简单：平时练习时只用最保守的C++98/03语法，头文件逐个显式include，严禁万能头文件。

#include <cstdio> #include <cstring> #include <string> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { int n; while (scanf("%d", &n) != EOF) { // 主逻辑 } return 0; }

这段代码是我所有模板的基础版。没有C++11语法，没有万能头文件，在任何老版本编译器下都能过。

2.2 多组输入和输出格式的坑

复试OJ的输入特别喜欢考“多组数据直到文件结束”这种形式。很多新手只处理单组数据，提交后直接WA甚至RE。这里有一个很重要的事实：OJ评测不是人看输出，是脚本比对输出。多一个空格、少一个换行、行尾多一个空白字符，都算错。

我的经验是，必须在做第一道题之前就把输入模板练熟：

int a, b; while (scanf("%d%d", &a, &b) != EOF) { printf("%d\n", a + b); }

如果有字符串含空格的读取，用gets或cin.getline；如果输入可能包含空行，需要考虑跳过空行。输出方面，如果题目要求“行尾没有多余空格”，我的处理方法是先存进vector，最后一并输出，控制分隔符。

2.3 时间限制的真实压力

复试OJ的时间限制通常是1秒或2秒，这和主流刷题网站的宽松限制有区别。1秒是什么概念？大概等于10^8次简单运算。也就是说，如果数据量是10^5级别，O(n²)算法大概率超时，必须用O(n log n)或O(n)；如果是10^8级别，连O(n log n)都必须谨慎。

我在笔记里专门做了个估算表，每次写完算法先对照一遍。

有些题目数据量没给全，这时候就要靠经验判断。比如看到“n的范围不超过1000”又要求最短路径，那大概率Floyd能过；如果看到“n不超过100000”还要求所有点对最短路径，那肯定不能Floyd了。

2.4 本地能跑不等于能AC：几个经典的环境错位

本地环境跑得好好的，一提交就出问题，根本原因一般出在三类地方。

第一，变量未初始化。本地内存被系统清零的概率大，而OJ上同一块堆内存可能残留上次运行的数据。我第二次刷动态规划的经典题时，就吃过这个亏——dp[0][0]忘了赋值0，本地碰巧跑出正确答案，提交后输出全错。

第二，数组越界不报错。本地运行数组越界不一定崩溃，OJ上可能RE，更恶心的情况是恰好覆盖了另一个变量的地址，导致“看起来是错的输出但程序没崩”。解决方式是：开数组时统一多加5个元素，例如int a[100005]而不是int a[100000]。

第三，long long的缺失。题目给的数据范围只要达到10^9，乘法运算就必须用long long。我见过太多人因为int溢出，白送二十分。判断方法很简单：估算最坏情况下中间结果的最大值，如果超过2^31-1，就改用long long。如果还不够，就用long long配合取模运算。

搞懂这些差异之后，我调整了练习方式，平时写代码一律开命令行窗口用g++编译运行，不开IDE的调试环境。这个方法虽然原始，但能最大限度模拟OJ真实环境，很多问题在练习阶段就提前暴露了。

3. 第16篇笔记里的三个算法重灾区：二叉树重建、最短路、并查集

进入正题。这篇复盘里，我重点重新做透了三类算法题。它们刷题网站里是高频题，复试OJ里更是常客。每类我都重写了不止三遍，每一遍都在某一个细节上翻过车，下面把这些细节全部拆开讲。

3.1 根据遍历序列重建二叉树：索引边界是最大杀手

题目：给定一棵二叉树的前序遍历序列和中序遍历序列，要求输出它的后序遍历序列。第一反应是用递归重建二叉树再后序遍历，思路很清晰，但实现时索引计算极其容易出问题。

核心原理：前序遍历的第一个元素是根节点，在中序遍历里找到这个根节点，它左边的元素属于左子树，右边的属于右子树，然后递归处理左右区域。

#include <cstdio> int pre[1005], in[1005]; int indexOfIn[1005]; void build(int preL, int preR, int inL, int inR) { if (preL > preR) return; int root = pre[preL]; int pos = indexOfIn[root]; int leftLen = pos - inL; build(preL + 1, preL + leftLen, inL, pos - 1); build(preL + leftLen + 1, preR, pos + 1, inR); printf("%d ", root); // 后序遍历 } int main() { int n; while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; i++) scanf("%d", &pre[i]); for (int i = 1; i <= n; i++) { scanf("%d", &in[i]); indexOfIn[in[i]] = i; } build(1, n, 1, n); printf("\n"); } return 0; }

我每次都错在leftLen的取值上。注意，leftLen是左子树的节点个数，不是左子树的区间终点。正确的递归参数是：build(preL + 1, preL + leftLen, inL, pos - 1)。这里preL + 1是左子树前序起点，preL + leftLen是左子树前序终点；中序部分是inL到pos-1。右边同理，preL + leftLen + 1是右子树前序起点。

写对的诀窍是：先把中序区间写对，再用节点数推前序区间。不要直接凭感觉写下标，一定要用变量把左右子树的节点个数算出来，宁可多写一行也绝不硬算。

3.2 单源最短路径：从邻接矩阵到堆优化，以及路径输出

很多复试OJ的最短路题不要求输出路径，只看最短距离，但偶尔会加一个“输出路径中字典序最小的”这种条件。我二刷最短路时，把朴素Dijkstra和堆优化Dijkstra都重写了两遍，重点解决了两个问题。

第一个问题是INF怎么取。常见写法是#define INF 0x3f3f3f3f。为什么不是INT_MAX？因为INT_MAX加上一个正数会溢出变成负数，导致松弛操作失效。0x3f3f3f3f约等于10^9，比所有合理的最远距离都大，而且两个INF相加也不会溢出int范围，这是习惯写法，不要轻易改。

第二个问题是撤销“松弛”操作的理解。Dijkstra的核心思想是“确认一个点的距离，然后更新它周围所有点”。二刷时我要求自己能把这句话翻译成代码，而不是背模板。

堆优化版本的核心代码：

#include <cstdio> #include <vector> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; struct Edge { int to, w; }; struct Node { int id, dist; bool operator<(const Node &other) const { return dist > other.dist; // 小顶堆 } }; vector<Edge> graph[10005]; int dist[10005]; void dijkstra(int s, int n) { for (int i = 1; i <= n; i++) dist[i] = INF; priority_queue<Node> pq; dist[s] = 0; pq.push({s, 0}); while (!pq.empty()) { Node cur = pq.top(); pq.pop(); int u = cur.id; if (cur.dist > dist[u]) continue; // 过期节点 for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i].to; int w = graph[u][i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({v, dist[v]}); } } } }

最后再提一句路径输出。如果需要输出路径而非只是距离，要在松弛成功时记录pre[v] = u，最后从终点不断往前回溯到起点。注意如果题目要求字典序最小的路径，单纯记录前驱是不够的——当两条路径距离相等时，要优先选择字典序更小的那个，处理方式是：松弛条件改成dist[u] + w < dist[v] || (dist[u] + w == dist[v] && 路径字典序更小)。这个变体在复试里出现频率不低，别忽略。

3.3 并查集与Kruskal最小生成树：判环逻辑最容易写错

第三类我重新做透的是并查集。这类题的奇怪之处在于：原理极其简单，但考场上写出来的代码可以错得五花八门。

并查集的核心就两个操作：查（find）和并（union）。但必须注意，路径压缩和按秩合并都要写，否则最坏情况下并查集会退化成一个链表。

int parent[10005]; int rankSize[10005]; int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } void unite(int x, int y) { int fx = find(x); int fy = find(y); if (fx == fy) return; if (rankSize[fx] < rankSize[fy]) { parent[fx] = fy; } else { parent[fy] = fx; if (rankSize[fx] == rankSize[fy]) rankSize[fx]++; } }

我二刷遇到的经典题是Kruskal求最小生成树。思路是：把所有边按权值从小到大排序，遍历每一条边，如果边的两个端点不在同一个集合里就加入这条边，并合并两个集合；如果已经在同一个集合里就跳过，因为加入它会形成环。这个“跳过”的判断，就是用并查集判断两个点是否连通，写起来容易漏。

完整的Kruskal框架：

struct Edge { int u, v, w; bool operator<(const Edge &other) const { return w < other.w; } }; Edge edges[100005]; int kruskal(int n, int m) { sort(edges, edges + m); int ans = 0, cnt = 0; for (int i = 1; i <= n; i++) { parent[i] = i; rankSize[i] = 0; } for (int i = 0; i < m; i++) { int fu = find(edges[i].u); int fv = find(edges[i].v); if (fu != fv) { unite(edges[i].u, edges[i].v); ans += edges[i].w; cnt++; if (cnt == n - 1) break; } } if (cnt < n - 1) return -1; // 不连通 return ans; }

这里的坑在于：cnt必须等于n - 1才说明图连通且生成了树。我在第一次写的时候忘了这个判断，导致不连通图也输出了错误答案。

4. 一次WA之后：完整的排查链路与心态调整

二刷复盘最有价值的部分不是“我做对了”，而是“我提交了一次WA之后是怎么一步步找到问题的”。这一章用一个真实案例走一遍完整排查过程。

4.1 现象描述：本地全过，提交WA

题目是堆排序的模板题，输入n个数，要求从小到大输出。我的代码在本地测试了多组数据，包括随机生成的100万个数据，全部正确。提交到OJ，WA。那一刻我的第一反应是“OJ坏了”，第二反应才是“input格式是不是有问题”。

冷静下来，我按下面这套流程排查。

4.2 第一步：检查输入输出格式

我重新读了一遍题目，发现题目要求“每一组的输出占一行，行尾无多余空格”，而我在循环里输出的是“数字+空格”。最后一多了个空格。有些OJ不判行尾多余空格，但这个OJ判。修改后提交，依然WA。

4.3 第二步：检查多组数据的状态重置

这时候我怀疑是全局变量没清空。我的堆排序是函数内定义数组，理论上没有跨组残留。但我注意到题目除了多组数据外，还允许n在不同组之间变化。如果上一组数据用了全局数组，下一组不重新读覆盖，就会残留旧值。我虽然没有这个问题，但排查到这一步时还是决定把数组定义改成了局部变量，确认每组都在函数内重新初始化。

4.4 第三步：构造边界数据和极端条件

格式没问题、状态没问题，那问题大概率出在数据边界。我开始造各种极端数据：只有1个数、所有数相等、已经有序的数组、倒序数组、n等于最大值100000。这一轮测试里，我发现当n等于1时，我的堆排序的“从最后一个非叶子节点开始调整”的写法，会访问到越界下标。本地之所以没暴露，是因为测试数据里没有n=1的情况。

这正是OJ评测的特点：评测数据覆盖所有边界条件，本地测试往往只覆盖“常规情况”。修复之后提交，AC。整个过程耗时一个半小时，但我把这套排查流程记进了笔记，后面遇到WA基本都是半小时内解决。

4.5 TLE的排查思维方式

排查完WA再说说TLE。遇到超时，我的排查步骤是固定的：先把算法复杂度写出来，对照数据规模估算最坏运行时间；如果确认复杂度超标，优先考虑优化数据结构而不是优化常数。

举个例子，有一道题要求频繁查询区间最小值。我用的是扫描法，单次查询O(n)，总复杂度O(nq)，数据量大直接超时。改用线段树或ST表后，查询变成O(log n)或O(1)，才顺利通过。排查TLE的另一个检查点是：是不是在循环里反复做了无意义的操作，比如strlen写在循环条件里、每次循环都重新申请大数组。这些都能在提交前靠肉眼找出来。

4.6 心态调整：40分钟没有AC是常态

复试着机试的时候，很多人死在心态上。我第11篇复盘时给自己定了一个数据：一道中等难度题，从读题到AC，平均需要45到60分钟。也就是说，考试时如果一道题15分钟没思路，别慌，这不是你菜，是正常节奏。

我给自己定的策略是：前15分钟看完所有题目，按难度排序；从最简单的开始做，保证拿到基础分；遇到卡壳超过20分钟的题，先跳过，回头再看。机试不是竞赛，不要求“全部AC”，保住能拿的分比死磕难题重要得多。这个策略让我从“最后半小时慌得写不动代码”变成“按时交卷还有时间检查”。

5. 适合短时间冲刺的复试OJ刷题节奏

复盘写了16篇之后，我总结出一套可复用的刷题节奏。它不一定适合所有人，但如果你和我一样，需要在两三个月内从“半吊子水平”冲到“机试不慌”，可以参考这个方案。

5.1 按模块筛选题目，不要海量刷题

我把复试机试常考的算法分成五块：线性表与模拟、树与二叉树、图论、动态规划、字符串处理。每个模块只刷10到15道“母题”，即最经典的、能代表该类算法思想的题目。母题的标准是：网上讲解多、题目变形多、代码量适中。做完母题后，找两三道变形题练迁移能力。盲目刷200道杂题，不如吃透50道母题。

5.2 整理一份手写模板

数据结构操作类题目，代码结构相对固定。建议把二叉树的几种遍历、建树、并查集、Dijkstra、KMP、高精度加法这些模板统一整理成一份文档，每天花20分钟手抄一遍。很多人觉得抄模板没用，但到了考场上，你会发现肌肉记忆比临场思考可靠得多。我抄到第16篇的时候，二叉树的非递归遍历已经能在一分钟内无错写出。

5.3 完成白纸编程训练

复试机试通常允许使用编辑器和编译器，但不排除某些高校的机试环境极其简朴，只给一个在线编辑框。我自己的训练方法是：每周找两天的晚上，不开IDE，直接在命令行用文本编辑器写代码，写完用g++编译，报错就看行号改，完全模拟无智能提示的环境。第一晚极度痛苦，第五晚开始适应，第十晚已经没有什么不适感了——这个适应过程必须在考前完成，不能指望考场上突然觉醒。

5.4 用三个时间点来安排复盘周期

我的具体安排是：新题做完当天记录错因；3天后不借助题解重做一遍；7天后随机抽做。第16篇复盘笔记的文章，就是在一次7天后的随机抽做过程中产生的——我抽到了之前错过的重建二叉树题，重新梳理了一遍完整思路，顺手把最短路和并查集又各写了一轮。事实证明，这种间隔重复比集中刷题牢固得多。

笔记里我会给每道错题标三个状态：还没懂、看过题解能写、独立能写。只有最后一个状态才算合格。

5.5 最后冲刺阶段的模拟训练

考前两周，我开始做整卷模拟。找一套目标院校的往年题或者同等难度的模拟卷，定时90分钟，全程不开笔记、不翻题解，完完全全模拟考场。模拟完不看分数，只看两样东西：哪些题卡住了、卡住的原因是什么。是思路卡住，还是代码写得慢？是复杂度估算错了，还是输入输出处理不规范？每一次模拟，都对应着一篇复盘笔记的素材。

这个阶段最容易暴露的，不是算法不会，而是时间分配失当。我第二次模拟时，在最后一道DP题上花了40分钟，结果前面一道简单模拟题没来得及写，白白丢了基本分。从那次之后，我调成了“简单题优先、卡题超过20分钟立即放弃”的策略。

最后分享一个我认为最实用的小技巧：给每次WA都写一句“错因归纳”。比如我笔记里出现的条目：“多组输入忘清空”“行尾多空格”“INF设得太小”“数组开小了5个”“双指针循环边界写反”。这些条目每一条都对应一次真实提交失败，集中起来复盘比翻十篇题解都管用。下一次遇到类似问题，脑子里会瞬间跳出对应条目，节省大量排查时间。这是我写满16篇复盘笔记以来，觉得最值得保留的习惯。