这个系列写到第九篇的时候我越来越确认一件事复试OJ这种考试拉开差距的往往不是谁见多识广而是谁能在同样基础的题目上少犯低级错误。东华复试的机试范围翻来覆去就是字符串处理、二叉树、动态规划、搜索和图论这几块题目难度不算刁钻但判题很严格错一个空格、多一次递归、少一个边界判断都会让你跟满分擦肩而过。所以我坚持把做过的题拿出来二刷并且每一篇都把当时的错误思路、正确解法、踩坑过程记录下来。这篇就是东华复试OJ二刷复盘9重点讲四个考点的典型题目拆解以及二刷过程中真实遇到的段错误、超时、输出格式和边界漏判问题。1. 为什么二刷比刷新题更适合复试冲刺1.1 首刷和二刷的注意力完全不一样首刷的时候人的注意力基本都花在“这题怎么做”上面。读题、猜算法、写代码、遇到样例过不了再调这一套流程走完题目虽然AC了但很多细节是稀里糊涂过去的。比如你可能是用递归过了二叉树但递归的层数限制在哪、会不会爆栈你根本没想过再比如字符串去重那类题你用set一把梭过了但题目如果要求“保持首次出现顺序”你的代码其实是错的。二刷就不一样了。题目已经知道怎么做注意力自然就会转移到“这个解法为什么对”、“还有没有更稳的写法”、“哪些边界最容易丢分”上。这个转变特别关键因为复试机试考的不是“你做没做过这道题”而是“你在限时、紧张、键盘不够顺手的情况下能不能稳定地把题写对”。1.2 什么样的题值得放进二刷清单不是所有AC过的题都需要二刷。我筛题单的时候只保留三类错过的题第一次提交不是AC经历过WA、TLE或者CE的说明某个环节的理解有问题必须重刷。过得勉强的题AC了但是用了很久或者代码写得又臭又长说明没有找到最优解这类题放在机试里很容易因为时间不够被卡住。思路模糊的题看题解才写出来的或者写完第二天就忘了自己写了什么的这类题不算真会放进二刷清单从头理一遍。第一遍刷题时我恨不得每天开三十道新题觉得刷得多就有安全感。现在回头看真正有用的反而是把做过的题再挖一遍。这个系列写到第九篇我二刷的题总量已经超过一百道但每天实际过的新题不超过五道其余时间全在重写、对比、记错因。2. 复盘9的题单筛选逻辑按考点、难度、复现价值三条线2.1 按考点分组把散题变成体系东华复试的OJ题库不算特别大但题型风格稳定基本集中在五个方向字符串、二叉树、动态规划、搜索和图、简单模拟。我二刷不是按题号顺序刷的而是按考点分组刷。这轮复盘9我先把之前做过标记的字符串题和二叉树题全部捞出来又把动态规划和搜索里“写过但没吃透”的挑了几道组成了这一轮的题单。分组刷的好处是你能在短期内集中看到同一考点的多种变体。比如字符串去重就有“按字典序输出”、“按首次出现顺序输出”、“同时统计频次”三种变体它们的解法核心都是桶计数但输出条件完全不同。如果不分组今天刷一道字符串、明天刷一道树你很难发现这层规律。2.2 按难度和复现价值排优先级我把复习的题分成三档保底题、中等题、拔高题。保底题是那种只要思路正确、代码别写崩就一定能AC的题占复试的大头中等题需要一点算法优化比如LIS的二分写法拔高题是压轴级别的综合题我在二刷阶段只保证思路通不会在这种题上死磕。复试机试的策略一定是先拿稳保底分再冲拔高题。所以这轮复盘9的刷题顺序是先快速重写四道保底题把每次都能一次AC的状态稳住然后再去碰中等题和拔高题。这里要提醒一句保底题最容易让人大意很多人的WA恰恰是栽在“这题我熟”的错觉上。3. 四个考点的典型题目拆解从错误思路到AC全过程3.1 字符串处理去重题里的“原序”陷阱这道题我印象特别深教训也很简单没看清题目要求上来就用set去重排序。题目原型很简单输入一行由小写字母组成的字符串去掉重复字符然后按原首次出现顺序输出剩余字符。我首刷的时候直接把set一用认为去重排序肯定没毛病结果样例只过了一半。二刷我才认真看题发现输出顺序要求是“按首次出现顺序”而不是字典序。这题的正解其实特别朴素用一个bool数组记录每个字符是否已经出现过再开一个vectorchar按原顺序收集答案最后遍历输出即可。复杂度O(n)空间O(1)。#include iostream #include string #include vector using namespace std; int main() { string s; while (getline(cin, s)) { bool seen[26] {false}; vectorchar order; for (char c : s) { if (c a c z !seen[c - a]) { seen[c - a] true; order.push_back(c); } } for (char c : order) cout c; cout \n; } return 0; }这个题暴露的问题不是不会用set而是读题太急。复试机试的判题只看输出你算法再高级输出不一样就是零分。所以二刷之后我给自己定了个规矩不管题目多简单都要把输出格式和要求完整读两遍再动键盘。3.2 二叉树遍历层序遍历的两种写法与风险点二叉树层序遍历几乎每个复试题库里都有但同学之间写法差异很大。我首刷用的是递归DFS按深度塞进vectorvectorint小数据AC了。后来二刷我专门测了一棵深度很大的左偏树递归直接爆栈这在OJ上一反馈就是SIGSEGV。二刷我改成了标准的BFS写法用队列逐层处理。关键点在于用q.size()锁定当前层的节点数然后一层一层往外弹。这样不需要额外记录每个节点的深度也不会出现层和层之间数据错乱的问题。#include iostream #include vector #include queue using namespace std; struct TreeNode { char val; TreeNode *left, *right; TreeNode(char v) : val(v), left(nullptr), right(nullptr) {} }; TreeNode* build() { char c; cin c; if (c #) return nullptr; TreeNode* node new TreeNode(c); node-left build(); node-right build(); return node; } int main() { TreeNode* root build(); if (!root) return 0; vectorvectorchar levels; queueTreeNode* q; q.push(root); while (!q.empty()) { int sz q.size(); vectorchar level; while (sz--) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } levels.push_back(level); } for (auto l : levels) { for (size_t i 0; i l.size(); i) { if (i) cout ; cout l[i]; } cout \n; } return 0; }这里有个小坑值得单独说一下层序遍历的题目经常要求“每行节点间用空格分隔行尾不能有多余空格”。第一遍AC的人里面至少有一半没注意行尾空格的问题只是OJ恰好没卡这个格式而已。严谨的写法就是用上面代码里的if (i) cout ;先空格后字符这样行尾就不会多出空格了。3.3 动态规划LIS的二分优化为什么要用upper_boundLIS这种经典题几乎每个复试考生都刷过但很多人只会写O(n²)的朴素DP。首刷时我也只写朴素版当时题库里的数据量小侥幸过了。二刷我再回头看这类题发现很多人栽在同一个地方看到n的范围是100000就慌了却不知道LIS可以用贪心加二分优化成O(n log n)。逻辑是这样的维护一个tails数组tails[i]表示长度为i1的递增子序列末尾元素的最小值。遍历原数组时用二分找到第一个大于等于当前元素的位置能替换就替换不能替换就追加。关键细节来了如果题目求的是“不下降子序列”即允许相等替换位置应该用upper_bound找第一个大于当前元素的位置而不是lower_bound找第一个大于等于的位置。差之毫厘谬以千里。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint tails; for (int x : a) { auto it upper_bound(tails.begin(), tails.end(), x); if (it tails.end()) tails.push_back(x); else *it x; } cout tails.size() endl; return 0; }为什么这个优化能保证正确性因为对于相同长度的递增子序列保留更小的末尾元素永远比保留更大的末尾元素有优势。这个贪心思想在很多“最长XX”题目里都能复用。二刷到这里时我把“lower_bound vs upper_bound”的差异抄到了错题本上因为这道题以后很可能会以“非严格递增”的变体再考一次。3.4 搜索与图迷宫最短路DFS和BFS的复杂度鸿沟迷宫最短路我首刷用的是DFS加回溯把所有路径走一遍取最短。写起来确实直观递归里记录当前步数到终点就更新答案。数据库规模小的时候一切岁月静好直到我二刷时随手生成了一张20×20的地图发现DFS跑了好几秒都没出结果这才意识到问题的本质DFS找最短路需要枚举完整条路径空间最坏情况下是指数级的而BFS有“第一次到达终点时就是最短路径”这个性质复杂度是O(n×m)完全不在一个量级。#include iostream #include vector #include queue #include string using namespace std; int n, m; vectorstring grid; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int bfs(int sx, int sy, int ex, int ey) { vectorvectorint dist(n, vectorint(m, -1)); queuepairint, int q; q.push(make_pair(sx, sy)); dist[sx][sy] 0; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); if (x ex y ey) return dist[x][y]; for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 nx n ny 0 ny m grid[nx][ny] ! # dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; q.push(make_pair(nx, ny)); } } } return -1; }这个题给我最大的启发不是“用BFS”而是“看到题目先算复杂度”。在OJ上题目给出的数据范围就是算法选型的最大提示。如果n和m只有10DFS也许能过只要放到100DFS就必死无疑。二刷的意义就在于把你曾经的“侥幸AC”变成“确定能AC”。4. 四个真实踩坑记录段错误、超时、输出格式、边界漏判的排查链路4.1 段错误从崩溃信息到固定的数组越界二刷二叉树层序遍历时我故意先用递归去写结果在深度很大的链式树上直接段错误。当时我第一反应是“指针搞坏了”实际上根本没那么复杂。排查链路是这样的先本地编译运行加上-g -fsanitizeaddress参数程序直接报出stack-overflow还自动给了一个超长的调用栈。顺着调用栈一看全是build()函数一层层往下压栈压到系统栈上限就崩了。这时候才意识到递归建树本身没问题但这个题的输入序列在最坏情况下会退化成深度为n的链递归深度直接等于n而系统栈默认只有8MB左右。处理方法有两个方向一是把二叉树的建树改成迭代式用栈模拟递归二是手动加大递归栈限制。在OJ上没法调系统栈所以最稳的选择就是尽量别写深度不确定的递归。层序遍历本身我用队列实现了完全绕开了递归深度的问题。所以段错误这块的最终结论是写递归前先问自己一句这棵树的深度会不会等于节点总数如果可能立刻改用迭代。4.2 超时从“本地秒出”到“OJ超时”的差距从哪来迷宫最短路那题我DFS版本在10×10的格子上跑得飞快放到15×15就开始有明显延迟放到20×20几乎等于死循环。我一开始甚至怀疑是不是死循环了后来用clock()在本地测了真实耗时才发现这不是死循环是复杂度爆炸。我把计时结果列了个小表10×10大约几十毫秒12×12接近两百毫秒14×14直接超过一秒15×15要好几秒。这个增长趋势就是典型的指数级增长。而同等规模的BFS版本15×15基本在一毫秒以内20×20也不会超过五毫秒。两者相差几百倍。这个问题教给我一个习惯看到20×20、n100000这种范围先算一遍最坏复杂度下的运算量再决定要不要动手写代码。1秒内能执行的操作大约在1e8这个量级O(n²)在n100000下意味着1e10次操作超时是必然的根本不用等到提交了再后悔。4.3 输出格式错行尾多了一个空格OJ直接判WA层序遍历二刷时我曾经习惯性写成cout l[i] ;每行末尾多一个空格。本地跑起来人眼根本看不出区别因为肉眼会自动忽略行尾空白。提交到OJ以后直接WA我当时的第一反应是“算法写错了”。后来我学乖了把期望输出和自己程序的输出分别重定向到两个文件里用diff逐字符对比才发现自己程序输出的每一行都比期望输出多一个空格。这里有一个特别实用的排查方法在本地写一个简单脚本把输出文件里每一行的行尾字符用十六进制看一遍xxd或者cat -A都行行尾出现的^$和真实空格一眼就能看出来。修复方式就是我上面代码里写的那样用if (i) cout ;保证字符之间才有分隔符行尾不输出多余空格。这个细节在东华复试OJ上很可能就是5分和0分的差别因为很多传统OJ是全文比对输出多一个字符都算错。4.4 边界漏判空行输入不是“没数据”而是“一条有效数据”字符串去重那道题我二刷时用while (getline(cin, s))读入然后习惯性地在循环开头写了一句if (s.empty()) continue;。提交WA样例却全过。排查了很久才发现题目描述里有一条容易被忽略的要求输入可能包含空行而空行对应的输出也是一个空行。也就是说空行不是“没有数据”而是一组有效输入应该输出一个换行符。我那个continue直接把空行跳过了导致输出文件整体少了一行后面的结果全部错位。修复很简单删掉continue让代码对空串也执行输出逻辑。但这一类问题暴露的是做题习惯——只考虑了“正常数据”没考虑“边界是被明确测试的”。现在我做字符串题一定会准备几组特殊的自测数据空字符串、全重复字符、无重复字符、超长单字符、包含空格和空行的混合输入。把边界想象成判题系统故意埋的雷二刷的价值就在这里把雷提前踩一遍。5. 复试机试的输入输出与数据范围细节隐性扣分项盘点5.1 多组数据与EOF判定怎么写才稳东华复试OJ很多题目都是“输入包含多组测试数据处理到文件末尾为止”。这句话看起来轻飘飘实际上决定了整个代码的外层结构。最常见写法是while (cin n)循环体里处理单组数据如果是字符串带空格的就用while (getline(cin, s))。这里有几个坑要特别提防。第一读数字再读带空格的字符串时数字行末尾的换行符会残留在输入流里导致getline接到的第一个字符串是空串。解决办法是在两者之间调用一次getline或者让读取方式保持一致。第二每组数据内部用到的容器要在组内重新初始化我见过有人把vector声明在循环外面第一组数据的残留内容污染了后半部分的答案。第三如果题目要求输出“每组数据占一行”别漏了换行但也别多余地输出Case #x:这种前缀除非题目明确要求了。5.2 数据范围决定算法1e3、1e5、1e9三种量级怎么应对做题这么多年我最大的进步就是养成了看数据范围选算法的习惯。数据范围不是摆设它直接告诉你能不能用暴力、需不需要优化、甚至需要优化到什么程度。n在1000以内O(n²)完全可行别过度设计。n在100000左右O(n²)会超时基本要写O(n log n)的算法比如排序配合二分、线段树、树状数组。n在1e9以上这类题通常不是让你枚举而是用数学公式、矩阵快速幂、数论分块这类结论性方法。LIS那道题就是这个逻辑的最佳体现。如果题目只给n≤1000我完全可以用朴素DP两重循环写得痛快AC也没问题但题库把n扩到100000本质上就是在提醒你必须用贪心加二分的O(n log n)解法。复试不考偏题怪题但一定会用数据范围卡掉那些只会写朴素版的人。5.3 编译环境与C标准别让新特性变成CE东华复试OJ用的编译器版本我不确定所以二刷时我刻意练习了一套最保守的写法不用C17的结构化绑定不用auto推导复杂模板类型不用bits/stdc.h这个万能头文件。不是说这些特性不好而是在比赛环境里一个CE直接就是零分完全没有辩解余地。比如我写迷宫BFS时明明auto [x, y] q.front();写起来很爽但为了保险还是用了int x q.front().first; int y q.front().second;。pairint, int的.first和.second在任何C版本都能编译。同样输出用endl还是\n我也统一成了\n因为endl会强制刷新缓冲区在大量输出时可能拖慢速度。如果你不确定平台的编译器版本最稳的做法就是尽可能写C11甚至C98风格的代码。丑一点没关系能过编译、能AC才是硬道理。6. 复盘9之后的计划从刷题量转向限时训练6.1 把目标从“刷了多少题”改成“1小时内AC几题”写了九篇二刷复盘之后我最明显的变化是刷题目标变了。以前我每天盯着“今天刷了15道新题”这种数字觉得量变一定能产生质变。可实际情况是大量题目只是浅尝辄止看完题解写一遍就算过第二天回忆起来只剩下“哦这题我做过”。现在我把每周的计划改成了三次限时模拟每次从题库随机抽3道中等难度题目限时1小时要求全部写出可提交的代码。模拟结束只统计一个指标AC了几道。错题不马上改而是先把错误原因记下来隔天再重写一遍确保不是靠短时记忆背出来的代码。这套流程坚持三周以后我在真实限时环境下的心态稳了很多不再害怕“打开OJ一片空白”。6.2 错题本不抄题解只写“当初为什么错”和“下次怎么避免”二刷复盘做到后面我也整理出一套错题本模板每一道错题只写四行题目类型、我的错误、错误原因分类、正确思路一句话。不抄完整题解因为题解抄了不看等于白抄真正有用的是那条自己总结的“下次怎么避免”。举个例子迷宫BFS这题我的错因分类是“算法选型错误”对应的总结是“网格最短路默认BFSDFS只在路径数量少且明确要求全部路径时才考虑”。字符串去重那题的错因分类是“读题不仔细”对应总结是“输出顺序必须从题目原文找不能凭经验脑补”。每次开始新一天的刷题前先把错题本翻一遍比直接冲进题库有用得多。7. 最后一篇复盘的体会与下一步安排复盘9做到这里我其实已经把首刷时那种“觉得什么都会”的泡沫挤掉了一大半。现在再看东华复试OJ的题目我不会再因为AC了就急着往下一题跑反而会停下来问自己三个问题这个解法的时间复杂度是多少边界条件测全了吗如果我隔三天再写一次还能一次AC吗如果三个问题的答案都是肯定的这道题才算真正过手。下一步的计划是继续整理二叉树和图相关的进阶题把树上搜索、并查集这些出现频率不那么高但复试可能压轴的考点也纳入二刷范围。同时在时间分配上给限时模拟更多的权重毕竟复试考场上的对手不是题目是你自己的手速和心态。如果你也在准备复试机试我的建议其实很简单别急着开新题把做过的题拿出来认认真真二刷一遍。一天两道四十分钟坚持一个月你会明显感受到“一次AC率”的上升。这个系列到第九篇没有结束但也说明一个道理——聪明人用笨功夫刷题这件事重复本身就是捷径。