东华复试OJ二刷复盘：从WA到AC的边界与复杂度思考

说来也怪越到复试前一个月我越觉得前期刷题时欠下的“账”都要还。所谓“东华复试OJ二刷”其实不是我突发奇想而是把第一轮留下的一堆WA题重新过一遍。刷到第16次复盘时我对这套题库的结构突然有了很不一样的感觉它压根不是在考你会不会背模板而是在逼你理解复杂度、边界和代码习惯。如果你也正在准备研究生复试或者只想在某套OJ上高效二刷一个题库这次复盘应该能帮你省下不少时间。这篇不是把所有题的AC代码贴一遍而是记录我在二刷阶段对题型分布、状态定义、输入输出边界、还有复试考核逻辑的重新理解。适合几类人看正在准备复试机试的考生、第一次刷OJ但一直被WA折磨的新手、以及已经进入二刷却总觉得“刷过等于没刷过”的同学。废话不多说直接进入正题。1. 东华复试OJ到底在考什么二刷时我重新画了一遍考点地图第一遍刷的时候我判断错了一件事总以为考的是“会不会做”。第二遍才意识到它真正考的是“能不能在限制条件下设计出更稳的解法”。东华复试OJ的题量不大但覆盖面很分裂。它既不是那种几百道让你练手感的LeetCode式题库也不是纯ACM风格的硬核比赛题。它更像是把复试笔试、机试、还有面试手撕代码的考点打包在一起用OJ的形式逼你动手。1.1 题型分布与难度曲线的再次确认第一遍我更多是“遇题刷题”看到什么做什么。第二遍我统计了自己已提交的题目分布大概是这样题型大类出现频率难度中位数二刷时我的重点动态规划最高中等偏上状态定义是否冗余能否压缩维度图论与搜索较高中等DFS/BFS的剪枝条件图的存储方式字符串处理中等中等常见算法的模板是否记得准确数学与数论较低中等边界数据取模运算溢出风险模拟与细节较高较易多组输入的读取模式输出格式这个分布说明一件事题库很重视基础但又不放水。动态规划占比高是因为复试面试时老师最容易现场考察而且DP题的解法往往能反映一个人的“建模思维”图论和搜索题目多是因为它们最容易从“会写”变成“会讲”面试官可以顺着你的思路追问下去。1.2 “AC”不再是唯一目标吃透复杂度而不是凑过样例一刷时有个坏习惯样例过了就提交WA了就换个写法继续蒙。二刷时我强制自己把所有题目按“时间复杂度”重新做笔记因为复试OJ里有很多题数据范围会卡你两层循环。比如一道题n给到10的5次方你写O(n²)再正确也过不了不是算法错是复杂度错。我给自己定的标准是每道题不光要AC还要能在注释里写清楚为什么选择这个复杂度。如果一道题可以用前缀和、双指针、二分三种方法做我会把三种都写一遍再用一个表格对比每种解法的空间和时间。这个过程很像复试面试时被追问“还有没有更好的做法”提前把这层想透上机时才不会慌。2. 二刷的核心策略与时间管理我为什么把顺序彻底打乱很多人二刷还沿着第一次的顺序从头往后刷这是最大的误区。第一遍刷完后你的记忆还在时按原顺序重刷会形成“模拟AC”的错觉——看到熟悉题号就知道大概解法但换个问法还是不会。所以我在二刷开始时就把顺序彻底打乱了。2.1 按知识块而不是按题号刷我把题库里的题重新归堆分成“DP专题”“图论专题”“字符串专题”“模拟细节专题”四组每组集中刷三到四天。这样做的理由很简单同一知识点的题放在一起你能明显看出题目之间微小的“变形点”。比如第一轮里我跳过了一道“环形数组最大子段和”的题当时觉得冷门。后来在DP专题里把它和普通最大子段和并排看才发现所谓环形只是让你处理“数组首尾相接”这个条件而已本质还是DP。如果不分组这种变形很难发现。2.2 一次只设一个“攻坚点”二刷时我给自己定的规则是每天只能有一个攻坚点。要么今天只死磕状态压缩要么今天只练拓扑排序的边界情况。白天三到四道题围绕这个点展开晚上复盘时只总结这一个点。这样做的好处是反馈特别清晰。你当天就知道自己有没有把这类题吃透而不是一口气做八道题最后每道题都只留下了模糊的印象。第16次复盘那天我的攻坚点就是“图论中带限制条件的拓扑排序”所以这一轮我对这类题的敏感度提高了不少。2.3 第16次复盘的特殊定位复盘次数到16意味着我已经完成了一轮完整的“刷题→总结→再刷题”循环。我习惯每四次复盘做一次小阶段总结16正好是第四个节点。到了这个节点我明显感觉到自己的关注点变化了第一轮关注“这题怎么做”第二轮前几期关注“为什么我当时WA”到第16期已经开始关注“这个套路在面试时该怎么讲”。这种变化不是自然发生的是复盘格式逼出来的。每次复盘我都会固定写三段一是题目与解法回顾二是当时的错误现场三是如果面试被问到该怎么展开。第16期做完回头看第一期的笔记最大的感受是刷题复盘的意义不是留痕而是逼你不断拉高看问题的视角。3. 清单式复盘这轮印象最深的8道题二刷不是每个题都值得单独写几百字。我把这一轮里印象最深的八道题整理成了清单既有重新酿成WA的题也有第一轮AC但这次发现自己根本没吃透的题。重点说几个典型。3.1 动态规划类状态定义里藏着最常见的一个坑有一道题是“从一个数组中选出若干数使它们的和最接近目标值”。第一轮我写的状态是“dp[i]表示前i个数能凑出的所有和”用布尔数组硬推结果空间勉强能过但时间卡得很死。这次我换了个思路把问题看成“正反两个方向的搜索剪枝”用双向BFS配合哈希表去查可能达到的和AC之后才明白原题的考点根本不是DP模板。真正要记的坑是不少DP题看起来是“选或不选”的背包问题但如果目标值范围远大于数组长度暴力的布尔DP会导致时间和空间同时爆炸。这时候要回头重新审视状态定义可能该压缩的是“和”这一维也可能该把问题改造成“差值最小化”的DP。3.2 图论类拓扑排序的“合法结果”不止一种这轮做了一道很折磨人的题给定一堆课程之间的先修关系要求输出任意一个合法的学习顺序。第一轮我用Kahn算法写每次从队列里取出节点时没管入度减完之后是否可能产生多个候选。虽然也AC了但这轮我把题目改成了“要求字典序最小的合法顺序”发现只靠普通队列不行必须换成优先队列。这个改版让我理解了一件事拓扑排序的模板很简单但它的变体非常多。复试OJ特别喜欢在这种“模板之上加条件”的地方设坑因为很多人只背了裸模板不知道优先队列可以控制输出的顺序。3.3 字符串类最小表示法的双指针理解有一道字符串题题目描述是把一个字符串任意循环移位后求能使字典序最小的那个起始位置。第一轮我看到“循环移位”就直接枚举每个起点比较一次n值小的时候还能过但题库里有一个测试点把n调到了10的6次方超时。这次我重新复习了最小表示法核心是双指针不断跳过不可能成为答案的起点。理解它最好的方法是用“两个指针赛跑”的视角而不是死记代码。写代码时我也顺手把while循环里的越界判断单独抽出来做了一组测试因为这个模板一旦写错大概率会陷入死循环或者数组越界。3.4 数据结构类堆与排序的边界选择有一道“取前K个最大元素”的题第一轮我直接std::sort然后取后K个过了。这轮我特意尝试了堆的写法因为如果数据范围进一步变大排序法的O(n log n)就不是最优了。用堆维护大小为K的最小堆时间复杂度变成O(n log K)内存也稳定。这题本身不难但复试OJ里经常把“前K个”和“K个动态插入”结合起来考如果只会排序法就会卡在“动态插入”那个环节。第二轮的教训是像堆、哈希表这种基础结构一定要练习“为什么这时候比排序更合适”而不是只在模板题里见它们。4. 从WA到AC追踪记录三次卡壳背后的共同点这轮复盘最值钱的不是哪道难题终于AC而是我在连续三次WA的过程里找到了一个共同规律很多错误不是由于“算法不会”而是由于“对输入和边界的处理太随意”。4.1 第一次卡壳整数溢出不是只有负数才会触发一道求“连续子数组最大乘积”的题我第一遍写的DP逻辑没问题但测试点里有一个全是1到30之间的数字的数组中间某一步乘积达到10的10次方以上C的int一下子就爆了。但诡异的是运行结果不是负数而是一个看起来还算正常的数字因为溢出之后它又恰好落回了int范围最后比较大小就完全错了。这类错误最坑人因为它不会让程序崩溃也不会让你一眼看出问题。我当时用下列代码排查long long curMax 1, curMin 1; for (int num : nums) { if (num 0) swap(curMax, curMin); curMax max(curMax * num, (long long)num); curMin min(curMin * num, (long long)num); ans max(ans, curMax); }改成长整型之后同一组数据的结果立刻变了。这个坑提醒我凡是题目里出现乘积、加法累计、幂运算的题先看一眼数据范围再决定用int还是long long。4.2 第二次卡壳把“多组输入”误判成了“单组循环”东华复试OJ里有相当一部分题是“多组测试数据”但不一定都写成“T组”的形式。有一道模拟题我先入为主以为只有一组输入结果程序只处理了第一组后面全部没读进去。OJ的多组输入常见写法是读到文件尾为止。我之前写的是int n; cin n; while (n--) { // 处理单个用例 }但这题的格式是每次给两个数字一直给到EOF没有T。正确的处理方式应该是int a, b; while (cin a b) { // 处理 }两种写法看似差不多实际天差地别。现在每次开始读题我会先标记“测试数据结构”是自己构造n、还是while(cin)、还是循环读字符串防止想当然。4.3 第三次卡壳格式化读入与EOF判断的细节还有一次WA是错在scanf的格式串上。我当时用“%d\n”去读输入本来只是想兼容换行符结果OJ的测试数据里某一行末尾没有换行或者连续两个数字之间是多个空格这个格式串就会让读取停住。后来我彻底改了习惯能用cin/cout解决的就用流读入除非数据量特别大才用scanf而且绝不把换行符写进格式串。复试OJ对格式很敏感但这不是让你去炫技而是强调“按题目要求的格式读取不多吃一个字符”。这类经验只有反复WA几次才能真正长记性。5. OJ复盘的常见问题与避坑清单二刷到现在我把所有遇到过的典型问题整理成了一张速查表。每次再WA我都会先对着表自查一遍效率比以前高了很多。5.1 常见错误速查表错误现象常见原因排查方向我个人的解决办法答案偏大/偏小整数溢出看数据范围和变量类型涉及乘法先换long long样例能过但AC不了多组输入理解错读题时确认输入结构用while(cin)统一处理运行超时复杂度不够优看n的范围估算换前缀和/二分/堆等结构数组越界边界判断写错检查循环上下界条件里先判越界再访问输出格式错多打空格/少打换行看输出说明统一用辅助函数控制空格死循环指针更新不及时双指针/while中的变量变化每轮末尾打日志验证这张表看起来简单但真到紧张的时候很救命。复试机试时间有限不可能每道题都从头Debug有个清单能让你先把最高频的错误排除掉。5.2 我的“颜色标记法”错误日志我在笔记软件里建了一个专门的复盘文档给错误类型分类边界类用红色标记复杂度类用橙色标记读入格式类用黄色标记思路错误用蓝色标记。每次二刷遇到一道新题WA我都会先去这个日志里看一眼是否属于已有类型。颜色标记法的另外一个妙用是能找出自己的“体质问题”。统计完第16次复盘时我发现自己红色的边界类最多这意味着我每次卡住的根源其实是注意力分配而不是算法储备。知道了这一点后面做题时我会专门留出两分钟检查边界条件WA率明显下降。这个习惯不算什么高深技巧但对复试用处极大。6. 复试视角下刷OJ本身就是在模拟面试二刷进行到中段我发现一个容易被忽略的事实复试OJ和真正复试面试之间的差距并没有想象中那么大。机试要的是AC面试要的是“讲清楚为什么AC”两者之间只差一个表达能力。6.1 从做题到讲题每道题都当成口头汇报第16次复盘之后我开始每做完一道题就模拟“口述题解”用三分钟把思路讲给自己听。这个过程会暴露很多问题比如我说不清楚为什么一维DP不用二维比如我遇到“如果元素有负数该怎么处理”会卡壳这其实说明我并没有把解法真正理解。后来我干脆把每道题的复盘笔记都写成“分步骤回答”的结构第一步讲算法选择第二步讲复杂度第三步讲边界条件第四步讲有没有更优做法。这个结构恰好跟面试时手撕代码之后被追问的节奏一致。6.2 面试官真正关心的不只是AC代码这道题过了但你可以不可以换一种数据结构可不可以从递归改成迭代如果数据范围再大一个量级这个算法还能不能跑东华复试OJ里的很多题AC只是起点真正的分水岭是你能在题目基础上回答出这些“如果”。我在二刷时会把每道题的最后一步固定写成“如果能重来”板块记录如果数据范围扩大到10的7次方我会如何调整。这一步对面试特别有用因为面试官最常问的就是“你有没有想过更优的解法”提前做了这个思考现场就不会冷场。6.3 二刷过程中的心态及时止损二刷不是越刷越爽的中间必然会遇到那种“第一遍明明AC了第二遍却怎么都写不对”的题。我第一次遇到时特别挫败后来才明白这恰恰说明第一遍是背模板背出来的第二遍才是真正在重建自己的理解。现在我做二刷复盘时会刻意把错的题用单独的清单管理不追求当天必须解决。如果一道题卡了四十分钟以上我会先放下等第二天再重新看。这么做不是逃避而是给大脑留出无意识加工的时间。很多题第二天再看往往五分钟内就能找到错误点。最后再分享一个小习惯如果你也在二刷某套题库我特别建议你给每个复盘周期都定一个“主题H3”。比如这次是第16次复盘我的主题就是“边界条件的系统性排查”。这样每次复盘都不会漫无目的回头看时也会有清晰的成长轨迹。经验这个东西不是靠AC数量堆出来的而是靠你从每道WA里提取出可以复用的判断规则。二刷最大的价值恰恰在于把这些规则沉淀下来。