复试机试的打卡复盘写到第6篇了。先交代下背景我是从确定进入东华复试之后开始准备机试的当时给自己定了个规矩——每天在东华复试OJ上做3道题做完当天记录结果第二天复盘错因每隔三天写一次阶段复盘。这次要复盘的是第16~18天题目范围已经从最开始的语法热身、简单模拟推进到动态规划、树与图、字符串处理这些复试高频考点了。如果你也在准备复试机试或者刚开始用OJ刷题但不知道怎么复盘这篇应该能给你一点参考。我会把这三天的做题记录、踩坑过程、改错思路全部摊开来讲包括我自己为什么WA、为什么TLE、最后是怎么改对的。这样比单纯晒AC数量有用得多。1. 第16~18天的选题思路为什么我把三天做成了三个专题很多人在OJ刷题是随机点题今天做一道数组明天做一道贪心后天碰一道图论。我之前也这么干过但后来发现效率太低了。复试机试准备时间就那么几周必须把有限的时间砸在最高频的考点上。我16~18天的安排分别是动态规划、树与图、字符串与模拟。1.1 第16天动态规划专题重点治“状态定义不清楚”第16天选了三道题整数拆分最大乘积、01背包恰好装满的方案数、最长先增后减子序列。这个组合是有意设计的。第一道题考状态转移的基本功第二道题考DP数组初始化的敏感性第三道题是LIS的变体看看横向迁移能力。当天的结果并不好看一题AC一题WA了一次才过还有一题TLE之后改出了正解。TLE那题是“最长先增后减子序列”我一开始用了三层循环的暴力解法数据规模一到500就超时了。后来改成正着做一遍LIS、倒着做一遍LIS再枚举中间最高点时间复杂度降到了O(n²)才勉强压过去。这个专题复习完我最深的感受是动态规划最难的从来不是写出转移方程而是把“dp[i]到底代表什么”这件事想明白同时把初始化和边界处理对。想不清楚状态定义的时候写出来的代码就是一顿乱试AC全靠猜测。1.2 第17天树与图专题模板题反而最容易翻车第17天做的是二叉树层序遍历、验证二叉搜索树、无向图连通分量数量。树和图是复试题里的常客看起来都是模板题但实际上是最容易在“边边角角”出问题的类型。层序遍历我用queue做的按层输出的时候需要先把当前队列长度存下来再一层一层往外弹。这个细节很多第一次写的人会忽略直接整棵树当成一维序列输出了。验证二叉搜索树那天我更是在同一个坑里栽了两次后面专门讲。连通分量那道题我用DFS写测试数据里有一条很长的链状图递归深度一上去就栈溢出改成显式栈之后才过。这三道题里两道AC速度还算快但验证BST那道题的WA让我意识到树相关的题局部正确不等于整体正确这个思维方式必须扭转过来。1.3 第18天字符串与模拟专题拼的全是细节第18天的三道题是大数加法、日期天数差、删除一个字符后能否变成回文串。字符串题和模拟题在复试OJ上的出现频率很高因为它们不怎么考高深的算法但特别考验把文字描述翻译成代码的能力以及处理输入输出的细致程度。当天最大的事故出现在大数加法上。题目描述说“每组数据占一行包含两个以大十进制表示的整数”我用getline去读结果因为上一行用scanf读T之后残留了一个换行符导致第一组数据读进来的是一串空字符串。后来改成cin直接读两个string才稳住了。日期天数差那道题反而比较顺利因为前一天晚上刚好整理过闰年判断标准套路直接套上去用。2. 三道题从WA到AC的完整复盘这波亏不能白吃一个星期的刷题里真正让我记住的往往不是AC得很顺利的题而是那些WA了两三发才过的题。复盘的价值也在这里。下面这三道题是16~18天里我认为最值得拆开揉碎讲的。2.1 整数拆分最大乘积贪心直觉是怎么把我带偏的题目描述很朴素给一个正整数n把它拆成至少两个正整数之和要求这些正整数乘积最大输出最大乘积。我第一反应是贪心尽量拆成3。这个结论本身是从数学上站得住脚的事实是当n≥5时尽量拆3得到的乘积确实最大。我当时满心以为2分钟就能AC结果在n4的时候被卡住了。4怎么拆拆成3和1乘积是3拆成2和2乘积是4。贪心算法一碰到这个案例就原形毕露了。我盯着输出结果想了很久最后放弃结论老老实实写动态规划。状态定义是dp[i]表示整数i拆分后能得到的最大乘积状态转移方程是dp[1] 1; for (int i 2; i n; i) { for (int j 1; j i; j) { dp[i] max(dp[i], max(j * (i - j), j * dp[i - j])); } }这个转移的核心逻辑是在i的拆分中把一部分切成j剩下的部分要么不再拆直接用i-j要么继续拆用dp[i-j]。两种可能都试一遍取最大值。写完之后我又跟贪心结论对比了一下大n的时候动态规划结果和拆3的结论一致但动态规划不需要背任何数学结论通用性更强。这道题给我的教训是复试题里遇到看起来有“巧解”的题目如果你不能在3分钟内严格证明这个巧解就老老实实写自己确定能AC的解法。贪心直觉在笔试里也许能碰对答案在OJ评测里会被一个反例打回原形。2.2 验证二叉搜索树被“局部正确”骗了两次验证二叉搜索树是第17天的重点翻车现场。题目很简单给一棵二叉树的根节点判断它是否是一个有效的二叉搜索树。我当时很快写了一个版本bool isValidBST(TreeNode* root) { if (!root) return true; if (root-left root-left-val root-val) return false; if (root-right root-right-val root-val) return false; return isValidBST(root-left) isValidBST(root-right); }这个代码只看每个节点和它直接左右孩子的大小关系完全没考虑跨层约束。OJ很快就给了我一个WA。测试用例里有一棵树根节点是10左子树根节点是5左子树的右孩子是15右子树是18。按我的代码每个局部都满足左小右大但实际上15比根节点10大这个节点放错位置了整棵树不是BST。正确的思路有两种。一种是给递归函数传递一个取值范围区间每往左走上界变成当前节点值每往右走下界变成当前节点值。另一种更省事的做法是中序遍历因为BST的中序遍历结果一定严格递增。bool dfs(TreeNode* root, long long lower, long long upper) { if (!root) return true; if (root-val lower || root-val upper) return false; return dfs(root-left, lower, root-val) dfs(root-right, root-val, upper); }这里用long long是因为测试用例可能出现INT_MIN和INT_MAX作为节点值初值如果设成int的边界一上来就误判了。这个细节值得记下来。我现在看到树的结构题第一反应不再是“检查每个点”而是主动去想“全局约束会不会被某个深层节点破坏”。2.3 大数加法我最先处理的不是进位而是输入行第18天大数加法这题题目本身并不难难的是读入这关。平台给的输入说明是“文件包含多个测试实例每个实例占一行”我一开始想用getline逐行读结果写得非常痛苦因为前面处理T的时候用的是scanf(%d)它把换行符留在缓冲区里导致第一次getline读到空字符串。后来我想明白一件事对于“每行两个数用空格隔开”这种格式直接用cin处理字符串是最稳妥的根本不需要先读整行再手动split。于是代码简化成while (cin a b) { cout add(a, b) endl; }add函数内部先把两个字符串倒序短的那个补零对齐然后逐位相加处理进位最后把结果再倒回来。核心部分长这样string add(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); if (a.size() b.size()) a.append(b.size() - a.size(), 0); else b.append(a.size() - b.size(), 0); string res; int carry 0; for (int i 0; i a.size(); i) { int sum (a[i] - 0) (b[i] - 0) carry; res.push_back(sum % 10 0); carry sum / 10; } if (carry) res.push_back(carry 0); reverse(res.begin(), res.end()); return res; }这道题最值得说的不是算法而是教训OJ题的输入格式千差万别拿到题先花30秒确认是用EOF循环读、先读T还是读完整行这比急着写算法逻辑重要得多。我那天因为这个细节浪费了将近20分钟补零和对齐反而是后面很快搞定的事。3. 9道题暴露出来的四个高频失分点不是算法问题复盘整个16~18天我把所有WA和TLE的原因统计了一下除了算法本身没想清楚之外有四个非算法层面的问题非常突出。这些问题不解决就算算法思路再清晰提交上去照样会挂。3.1 边界条件永远要第一个写出来整数拆分的n4案例、BST的空树情况、大数加法的两个数长度不一致、日期天数差里的闰年2月……几乎每道题都有它的“特殊值”。以前我写代码是先写主流程最后补边界结果要么漏掉要么补丁打得很难看。现在的做法是拿到题先在草稿纸上写清楚输入的最小值是什么最大值是什么空输入会怎样单节点会怎样两个数相等会怎样。写完这些再动键盘。3.2 输入输出习惯要跟题目走不能跟自己的惯性走东华复试OJ上的题有的读到EOF结束有的第一行给T还有的是每组数据之间有空行。这三种格式对应完全不同的代码写法。我的项目里常年用while(cinn)处理多组输入一旦题目明确说了“第一行为测试次数T”我就会因为惯性写错结构。第18天大数加法不是T格式我却一直按“先读T再循环”去猜浪费的时间比做正题还多。我的反思是每道题提交之前先对着题目原文把输入格式重新默读一遍这比盯着代码看一遍有效得多。3.3 时间复杂度的估算不能靠感觉要养成算规模的习惯第16天那道“最长先增后减子序列”TLE核心原因就是我没看数据规模就上手写暴力。题目如果n给到1e3O(n²)可能过n给到1e5就必须O(nlogn)。复试机试的时间限制一般给得比较松但也不是无限松三层循环套上去到了临界点照样超时。我现在每道题写之前会在草稿纸上算一下n是多少我的算法复杂度是多少估算出大概的运算次数超过1e7就要考虑优化。这个习惯让我在后面刷图论题的时候少踩了很多坑。3.4 隔一天再看的复盘比当天盯着改更有效这也是我打卡系列一直在坚持的事。当天AC的题大脑其实是热的很多错误即使改了第二天也就忘了。所以我的复盘方式比较特殊所有错题当天只记录不重写第二天重新把题做一遍不看任何之前的代码。做出来了再对照前一天的错误记录。这个“冷却期”能把短期记忆的假象过滤掉留下的才是真学会了的知识点。4. 我的三遍复盘法一道题是“AC了”还是“真会了”很多人刷题只追求提交记录里的一片绿色显示Accepted就觉得自己会了。我之前也这样直到我发现同一道题过两周再做还能写错。后来我给自己定了“三遍法”现在刷题吸收率高了很多也推荐给时间还算充裕的备考人。4.1 第一遍AC之后立刻研究最优解AC只代表你的代码通过了测试点不代表你的解法是好的。我的习惯是AC之后立刻去翻题解区和讨论区看看别人用了什么更优雅的思路。比如整数拆分那道题我写了O(n²)的动态规划通过了但有人用拆3的数学结论直接O(1)出答案还有人用记忆化DFS。对比之下O(n²)的DP虽然不是最优但在复试场景下已经够用因为评委看的是正确率和代码可读性不是运行时长的极限优化。这遍研究的核心目的是拓宽思路不需要真的把所有解法都实现但至少要知道每个解法存在、它解决什么问题。4.2 第二遍隔天重写不看答案也不看旧代码这是最关键的一遍。我把题目标记在打卡表上第二天不做新题之前先把前一天错过的题独立重写一遍。如果还能AC说明这个知识点真的进脑子了如果卡住说明当时是瞎猫碰上死耗子或者纯粹靠短期记忆背住了代码。这个时候再去翻前一天的笔记效率比当天改错高很多。4.3 第三遍按“错因标签”归档到冲刺清单每天的三道题不论对错我都会在打卡表里写下几个标签比如“DP初始化”“BST边界”“输入EOF”“递归爆栈”。第16~18天结束后我把这些标签汇总了一遍发现“边界条件”出现了5次“输入输出格式”出现3次“复杂度估算”出现2次。这些标签就是复试前最后一周的冲刺方向比重新把所有题目刷一遍精准得多。5. 接下来第19~21天的调整从刷题转向模拟实战连续刷了18天我对东华复试OJ的风格也有了一些判断整体难度在“基础算法熟练掌握”这个档位很少出特别偏的偏题怪题但会在边界条件、数据规模这些细节上卡人。所以第19~21天我打算做出三个调整。5.1 专题安排从“补短板”变成“稳拿分”接下来三天我不太可能再花一整天只死磕动态规划了。更多的安排是每天两题保持手感一题刷自己相对薄弱的贪心和二分另一题做综合性比较强的模拟题。复试机试不是算法竞赛不需要掌握太多冷门算法但常见题型必须达到“看到就能下手”的熟练度。5.2 每周加一次限时模拟强迫自己适应机试节奏平时刷题没有时间压力一道题磨一两个小时也无所谓但复试机试是有时间限制的。我计划以后每周挑一天拿一套指定题库里的题给自己定1小时的倒计时模拟完整考试流程。这个过程不是为了测能做出多少题而是为了训练紧张状态下的做题策略先扫一遍所有题从最简单的开始不在一道题上纠缠超过20分钟。5.3 细节点位补强手写样例、调试输出和赛后记录最后想说几个小习惯。现在我还坚持在每道题AC之后把题目给出的样例手动在纸上走一遍对照代码逻辑确认每一步的中间结果遇到需要调试的时候用错误答案反推而不是盲目加输出语句。每次复盘结束时我会在打卡表最后补一句“这道题如果两周后再查我能不能一遍写对”。想不清楚答案的题就不算真正结束。这个习惯看着简单但已经帮我避免了不少重复刷题的时间浪费如果你也在准备复试机试建议也试试。