复试OJ二刷复盘：吃透高频算法题与评测系统差异

复试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是多年没升级的老系统。老版本编译器意味着什么意味着你可能用不了C11之后的新特性甚至部分STL接口的行为都和现代版本有细微差别。我遇到过最典型的两个情况第一个unordered_map在极老的编译环境下不可用或效率异常低。第二个auto、范围for循环、std::stoi这类语法在某些老标准下直接编译失败。解决办法很简单平时练习时只用最保守的C98/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; }这段代码是我所有模板的基础版。没有C11语法没有万能头文件在任何老版本编译器下都能过。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 ≤ 100O(n³)三重循环暴力n ≤ 1000O(n²)朴素DP、双循环n ≤ 10^5O(n log n)排序、堆、分治n ≤ 10^7O(n)线性扫描、哈希n ≤ 10^9O(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; // 小顶堆 } }; vectorEdge graph[10005]; int dist[10005]; void dijkstra(int s, int n) { for (int i 1; i n; i) dist[i] INF; priority_queueNode 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万个数据全部正确。提交到OJWA。那一刻我的第一反应是“OJ坏了”第二反应才是“input格式是不是有问题”。冷静下来我按下面这套流程排查。4.2 第一步检查输入输出格式我重新读了一遍题目发现题目要求“每一组的输出占一行行尾无多余空格”而我在循环里输出的是“数字空格”。最后一多了个空格。有些OJ不判行尾多余空格但这个OJ判。修改后提交依然WA。4.3 第二步检查多组数据的状态重置这时候我怀疑是全局变量没清空。我的堆排序是函数内定义数组理论上没有跨组残留。但我注意到题目除了多组数据外还允许n在不同组之间变化。如果上一组数据用了全局数组下一组不重新读覆盖就会残留旧值。我虽然没有这个问题但排查到这一步时还是决定把数组定义改成了局部变量确认每组都在函数内重新初始化。4.4 第三步构造边界数据和极端条件格式没问题、状态没问题那问题大概率出在数据边界。我开始造各种极端数据只有1个数、所有数相等、已经有序的数组、倒序数组、n等于最大值100000。这一轮测试里我发现当n等于1时我的堆排序的“从最后一个非叶子节点开始调整”的写法会访问到越界下标。本地之所以没暴露是因为测试数据里没有n1的情况。这正是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篇复盘笔记以来觉得最值得保留的习惯。