1. 复盘框架每天3题到底该留下什么东华复试OJ刷到第130题之后速度和题量已经不太重要了真正拉开差距的其实是复盘质量。我给自己定的规矩是哪怕当天只做3题也一定要留出大约四十分钟把这3题重新过一遍把“题目场景、考点、第一反应的偏差、最终解法、可变式方向”写进笔记。这次复盘130、131、132三题分别覆盖字符串处理、数学推导模拟、动态规划入门正好是复试机试里最常出现的三类题型。很多人在这个阶段容易陷入“刷题量上去了但遇到稍微变形的新题还是没思路”的困境。原因不是刷得少而是复盘太浅。复盘不是把AC代码贴一遍就结束我要回答自己三个问题这题到底在考什么我第一眼看到题目时最自然的思路是什么这个思路和AC思路之间的差距在哪这三个问题想清楚比再刷十道题都有用。我也把这三题的考点列成了表格方便一个月后回看。题号题目场景核心考点复盘重点130两个字符串能否通过循环移位匹配字符串处理、边界判断拼接技巧、子串起点范围控制131围成一圈报数求最后存活编号模拟、数学递推公式推导与编号映射关系132有限容量下选择物品求最大价值动态规划、01背包状态定义、滚动数组倒序遍历原因1.1 复盘时我会刻意忽略“AC”本身当时做这三题的时候130题我一眼就想到拼接字符串的思路但第一次提交还是错了一个测试点问题出在子串起点的上限上。131题我一开始用的是链表模拟跑起来没问题但n到十万级就会超时后来才改成递推公式。132题我已经写过很多次01背包然而还是把滚动数组的遍历顺序写反导致结果偏大。复盘的价值不在于记录“我通过了”而在于记录“我第一次在哪一步想岔了”。这些想岔的地方往往是题目真正想考察的边界条件。比如130题里很多人都会想到A A拼起来找子串但如果B比A长或者B恰好跨过拼接点就要小心处理。这类边界不是靠背模板能解决的只能在复盘里反复标注。所以我现在的笔记结构是固定五段题目改写、考点标签、卡壳点、AC代码、扩展变式。做题时我只写前两段复盘时补后三段。这个习惯从100题坚持到现在已经积累了三十多页笔记考前基本只看这些。1.2 这类OJ题和实际工程的差异东华复试OJ的题目风格比较偏基础不会故意给你设工程陷阱重点考查的仍然是“能否把问题抽象成明确的数据结构和算法”。这和我在网上看到的华为OJ风格有些不同华为OJ往往把题目包装成实际业务场景输入输出也更复杂。但核心框架是通用的不管是东华OJ还是其他OJ本质都是给你输入、要你输出判题系统后台跑测试用例来比对结果。如果之后想更深一层完全可以自己用Java写一个在线判题系统的项目来练手核心模块包括题目管理、代码提交、编译运行、沙箱隔离和结果判定。做一遍就知道OJ后台远没有想象中那么神秘。不过复试阶段的重点是算法本身这个项目可以留到复试之后再折腾。2. 第130题复盘循环移位匹配坑不在匹配而在起点2.1 题目场景还原题目大致是这样的输入两个字符串A和B判断B是否是A经过若干次循环左移后得到的字符串的下一个子串翻译成人话就是A可以像转轮盘一样循环移动只要B能在这个轮盘上被完整匹配上就输出yes。这个场景很常见比如判断密码锁上的一段数字是否能组成目标数字或者判断循环队列中是否存在某段特征序列。第一次看到这类题本能反应肯定是枚举所有循环移位的结果每次移位后完全匹配一次。这样做没问题但会让复杂度变成O(n^2)乘上匹配成本万一字符串长度到几千甚至上万效率就吃不消。我当时的第一版思路就是枚举写了大概五分钟后意识到可以更简单与其真的把字符串左移不如构造一个A A的串然后在这个新串里找B。为什么可行因为循环左移k位的结果本质就是A中从下标k开始的连续len(A)个字符而A A恰好把每一种起点都覆盖了。这一步其实是把“移动”变成了“滑动窗口”属于典型的空间换时间思路。2.2 完整解法与代码用C实现最直观的做法是暴力匹配子串代码非常短#include iostream #include string using namespace std; bool isLoopMatch(const string A, const string B) { int n A.length(); int m B.length(); if (m n) return false; string S A A; for (int i 0; i n; i) { int j 0; while (j m S[i j] B[j]) j; if (j m) return true; } return false; } int main() { string A, B; while (cin A B) { cout (isLoopMatch(A, B) ? yes : no) endl; } return 0; }关键点在于for (int i 0; i n; i)。为什么不是i S.length()因为B的长度已经保证小于等于A的长度所以只要循环移位起点在A的范围内从起点出发的n个字符就足够覆盖整个A。而如果起点i到了n以上比如i n对应的其实又是从A[0]开始的序列已经在上次循环里匹配过了没必要重复。如果B比A长还让起点走满S.length() - m 1就会多出无意义的匹配偶尔还会触发越界风险。如果想更稳直接调用STL的find也行代码更短bool isLoopMatch(const string A, const string B) { if (B.length() A.length()) return false; return (A A).find(B) ! string::npos; }find内部通常用BM或KMP类算法匹配效率高。但复试时我还是建议自己手动实现一遍暴力匹配因为很多OJ上的题是为了考手动匹配能力万一find在某些环境下的实现不符合预期手动版本更可控。2.3 字符串匹配的边界与易错点这道题我踩了一个让我印象深刻的坑如果B比A长直接A A再find(B)其实是可能返回错误的因为B可能在拼接后的串里横跨多个循环周期。比如A ab, B aba拼接后A A abab你会发现B aba确实出现在拼接串里但A无论怎么循环移位都不可能产生“aba”这个子串因为B的长度已经超过A本身。所以一定不能漏掉if (m n) return false;。这个判断不是优化是正确性的一部分。另一个容易错的地方是输入里可能包含空格如果用cin A空格会被截断。复试OJ一般不会在字符串题里塞空格但对这种细节保持敏感是好的如果题目明确说字符串可以含空格就得改用getline读取。复盘里面我会额外记一句字符串类的题解题前先问三件事——长度上限是多少、字符集是什么、是否区分大小写。这三件事几乎决定了解法选型。长度小可以直接暴力长度大就要考虑KMP或哈希字符集小可以用桶记录字符集大就得用哈希表或排序。3. 第131题复盘约瑟夫环不止能模拟还能用一条公式收工3.1 模拟思路与递推思路的对比131题是经典的约瑟夫环n个人围成一圈从1号开始报数每报到m的人出圈接着从下一个人重新报数问最后剩下的人的编号。复试题目往往要求先理解规则直接用链表或数组模拟也能过小数据但一旦n是十万级每轮删除都要移动元素复杂度直接爆炸。我在第一次做这题时用的是数组标记法维护一个当前游标和剩余人数每次循环数m个人找到要删除的下标然后标记。这个思路的复杂度是O(n * m)如果m很大比如100万而n只有1000整体运算量就会非常离谱。所以模拟只能应对“教学示例”级别的数据真正比赛里必须上数学结论。递推的思路是假设n个人围成一圈时最后留下的人编号为f(n)那么第一次删除的人编号是(m - 1) % n。删除这个人之后剩下n-1个人重新编号新的0号位置对应原来删除位置的下一个位置。把n-1问题的解f(n-1)映射回n问题的编号就能得到f(n) (f(n-1) m) % n。这个式子写成代码只要一行循环。3.2 完整实现与复杂度分析#include cstdio int josephus(int n, int m) { int ans 0; // n 1 时最后留下的人编号为 0 for (int i 2; i n; i) { ans (ans m) % i; } return ans 1; // 转回 1 起始编号 } int main() { int n, m; while (scanf(%d%d, n, m) 2) { printf(%d\n, josephus(n, m)); } return 0; }这一段代码的时间复杂度是O(n)空间复杂度是O(1)无论n多大都能在极短时间内跑完。很多第一次见的同学不太理解为什么i从2开始也不理解mod i里的i为什么不是n。其实i表示当前问题的规模递推是从规模1推导到规模n的所以每一步都只对当前规模取模。规模为1时显然答案是0这个0是相对0起始编号的最后输出时需要转换成题目要求的1起始编号所以ans 1。这里我要特别讲清楚“相对编号”这个概念。约瑟夫环递推里的编号一直是相对当前环的首位而言的而不是原始绝对位置。每删掉一个人环的整体编号都会重排导致直接记忆原始编号是非常容易出错的。这也是为什么很多人推导时容易把ans理解成原始编号从而算出错误结果。3.3 变式题和额外收获复盘时我额外思考了几个变式如果要求按出圈顺序输出编号那O(n)的递推公式就不够用了需要结合树状数组或线段树进行区间删除模拟复杂度可以做到O(n log n)如果m非常大比如超过int范围就要用到“大步跳跃”优化直接跳过一整轮报数。这些变式不需要复试阶段全部掌握但至少要知道它们存在万一考题换个说法不至于完全懵。约瑟夫环这种题的启发是凡是“规则循环、状态不断收缩”的问题都可以先思考有没有递推关系。这类题最忌讳一上来就照着原过程机械模拟因为出题人往往会把数据范围设成模拟会超时的大小逼你找规律。我的经验是遇到n超过10万并且规则里存在“循环删除”关键词的题目优先想数学解法模拟只用来写对拍程序验证小数据。4. 第132题复盘01背包的滚动数组为什么必须倒着遍历4.1 从二维DP到一维滚动数组132题是标准的01背包有n件物品每件物品有自己的重量w和价值v背包容量为V问能装下的最大价值是多少。这是动态规划的基础题型几乎所有复试机试都绕不开它。第一遍学的时候一般会写二维dp[i][j]其中i表示前i件物品j表示当前容量转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。二维版本非常直观但它有一个明显的问题空间复杂度是O(n * V)。如果V是1万n是1000数组就是1000万int类型占40MB有些OJ的内存限制在32MB甚至16MB直接超限。所以实战里一定会用滚动数组优化只用一维dp[j]表示容量为j时的最大价值。一维版本的转移方程变成dp[j] max(dp[j], dp[j - w] v)。问题是为什么这里必须让外层循环物品、内层循环容量时把容量从大到小遍历我是用“物品只能选一次”这个逻辑来理解的正序更新时dp[j - w]可能已经在当前物品这轮被更新过相当于同一件物品被选了两次倒序更新时dp[j - w]还是上一轮物品处理完后的旧值这样dp[j]只能从不包含当前物品的状态转移过来恰好保证每件物品至多选一次。4.2 手写代码与边界控制#include iostream #include algorithm using namespace std; const int MAXV 100000; int dp[MAXV 1]; int main() { int n, V; cin n V; for (int i 1; i n; i) { int w, v; cin w v; for (int j V; j w; j--) { dp[j] max(dp[j], dp[j - w] v); } } cout dp[V] endl; return 0; }有几个细节值得单独拿出来说。第一j的循环下限是w不是0因为容量小于物品重量时dp[j - w]的下标为负数会导致越界访问虽然有时候不一定会崩但结果是错的。第二dp数组一定要初始化为0这对应“背包为空时什么也没装价值为0”的初始状态。第三如果题目要求“恰好装满背包”那初始化和最后答案的判断条件就要变dp[0]设为0其它下标设为负无穷最后检查dp[V]是否大于0。这个区别在复试中经常当成进阶问法。我还会顺手把w和v输入顺序读错之类的低级错误记录在复盘里因为这种错误在考场上白白浪费调试时间。建议写背包模板时统一用weight[ i ]和value[ i ]这种语义清晰的变量名别用w、v两个单字母硬记尤其是看到代码里到处都是v和w时很容易混淆到底谁是重量谁是价值。4.3 如何从01背包发散到其他背包复盘的最后我总会想一下扩展方向。01背包有两个经典变式完全背包把容量正序遍历即可因为物品可以无限次选多重背包则可以把物品数量按二进制拆分成多个01背包物品或者使用单调队列优化。复试阶段完全背包出现的频率不低多重背包如果出现在正式考试里数据范围一般也不会卡得太狠。把这些背包问题放在一起看其实核心还是“状态转移的时候当前状态能不能由同一轮物品更新”这个区别。只要把正序和倒序的原理想透考场上即使忘了模板也能根据“同一物品选几次”反推出来。我见过不少同学死记模板结果题目问的是完全背包却把容量倒序写了整道题直接零分。记原理永远比记模板可靠。5. 三题打卡过程中遇到的典型问题与排查技巧5.1 编译运行环境对写法的限制东华复试OJ使用的C版本一般比较稳定但不一定支持最新标准。我的习惯是在代码里尽量避开C11之后的特性和auto不要依赖unordered_map之外的复杂容器因为不同版本上的头文件差异可能导致本地能跑、OJ上编译失败。更常见的坑是输入输出。有些题目是多组测试数据直到EOF结束必须写成while (cin A B)或while (scanf(...) 2)这种形式。如果写成只读一组数据再return本地测试看起来没问题OJ上就只能过第一组样例后面全判错。这类问题几乎每次训练都会有人遇到复盘里必须标红。还有输出格式的坑题目要求每个结果之间用换行隔开如果多输出一个空格或漏掉换行在OJ的“严格比对”模式下直接报错。OJ后台普遍就是把你提交的程序编译运行再喂入标准输入把你程序的标准输出和预期输出做逐字节对比有些简单题目还会用ESP等特判但复试OJ大都是严格比对所以千万不能小看多余空格。5.2 现场调试时的几条经验我在刷这三题时也遇到了一些比较烦的bug。比如130题第一次忘记处理m n导致找出了“错误的匹配”131题刚开始用数组模拟数据一大就超时浪费了不少时间。这里整理了一个小小的速查表分享给同样在准备复试OJ的同学。症状可能原因排查方法本地运行正常OJ全错多组数据只处理了一组改成循环读入到EOF输出格式不对末尾多空格、缺换行把输出用repr查看逐字符对比大数组直接崩溃或者MLE栈上开了很大的数组把大数组改为全局变量或使用静态数组递归程序栈溢出递归深度过大改成迭代或用显式栈答案偏大背包容量循环正序写检查内层循环方向是否倒序答案偏小初始化边界错误检查dp初始值和“恰好装满”条件运行超时模拟复杂度太高寻找递推公式或改用更优数据结构有一条调试技巧对我帮助最大先写一个暴力解再写一个高效解用小数据对拍。比如131题可以写一个普通链表模拟版本和一个O(n)递推公式版本随机生成n小于20的数据反复比较结果确认两边完全一致后再提交递推版本。对拍能快速验证自己的思路是否出错比盯着代码干想高效太多。5.3 复试备考中刷题节奏的调整从130题开始我已经不再盲目追求“每天5题”了。这个阶段更合理的节奏就是标题里说的“每日3题”每天三个新题每个题复盘三十分钟再留五分钟想扩展变式。这样一天的投入接近两小时既不会因为强度太大导致疲惫又能保证长期稳定推进。如果下午状态不好我会挑一题代码模板类题型热身比如背包问题状态稳定的时段再刷一题需要推导的类型比如约瑟夫环这类。状态没有硬性的好坏之分但我发现把同类题放在同一天做记忆效果特别好。130、131、132这组题正好都是“一个核心思路可以扩展到多个变式”的题型组合起来复盘很舒服。6. 关于复盘笔记和代码模板的一点心得最后分享一个我一直在用的复盘格式每道题都分成四行记录。第一行是题目的一句话场景第二行是考点标签第三行是第一次提交的错误原因第四行是最终解法里最值得记住的关键点。代码不用整段复制只抄状态转移方程和边界判断即可。比如130题我记录的是“循环移位子串匹配拼接起点范围B长于A直接false”。131题记录的是“约瑟夫环递推ans(ansm)%i复杂度O(n)”。132题记录的是“01背包滚动数组容量倒序dp[j]max(dp[j], dp[j-w]v)”。这些几十个字的内容比一整页完整代码更容易考前快速过。这个习惯对我帮助很大因为复试复习期会积累大量题目如果全部靠重新刷一遍来回忆时间根本不够。而复盘笔记能让我像翻目录一样直接定位到某一题的核心思路和曾经的坑。130到132这三题做完之后我对字符串匹配、数学递推和动态规划模板的理解明显比单纯刷题时要深。个人建议所有准备OJ复试的人都试试这种“每天三题加上结构化复盘”的方式坚持二十天你会明显感受到自己做题时的第一反应快了很多。