第三次写这套题的复盘了。二刷某高校复试OJ的整个过程前后横跨了三周这一轮复盘我本来只想整理个错题清单结果翻回去看第一轮的做题记录很多当时感觉“我明白了”的题现在重新上手还是要卡一下尤其是图论和动态规划思路不到位就是写不出AC代码。复试的机试不像笔试代码提交上去当场判定对了就过错了就是零分没有情面可讲。这篇复盘想写给两类人一类是正在准备计算机类、软件类考研复试机试的同学另一类是刷了不少题但总觉得没沉淀下来的同学。我先说说背景。报考学校自建的OJ系统题量不小复试成绩里机试占比很重题目难度介于传统ACM入门题和课程作业之间考的是熟练度和基础算法的基本功。第一次刷的时候我比较莽按题号顺序从前往后AC一道忘一道。二刷才老老实实按专题、按难度重新过了一遍这一遍的效果比一刷好太多。如果你也正在准备类似的复试机试这篇复盘里的题型分布、重点算法思路、踩坑记录和复盘方法论应该能帮你少走不少弯路。1. 复盘之前先把“二刷”这件事想明白1.1 一刷和二刷的本质区别在哪里很多人刷题只刷一遍觉得见过、AC过就等于掌握了其实这是最大的错觉。一刷的典型状态是“刷题像追剧”看完题解觉得懂了照抄一遍AC了第二天再问自己“为什么这么做”往往说不上来。二刷的核心不是把题再看一遍而是合上题解、不看笔记凭记忆和推导把代码写出来再和第一次的解法对比找出差距。我用一个很通俗的比喻来理解这件事一刷是在认路二刷是在自己开一遍车。认路的时候你坐在副驾驶旁边有人指挥路口怎么走都是别人告诉你的二刷是把导航关掉自己开到终点真开错几次才能记得住。复试考场上没有题解也没有人指挥你能依赖的只有脑子里真正沉淀下来的路径。所以二刷和“再看一遍”完全是两码事。二刷的精髓是主动回忆或者叫“提取练习”。这个过程中每一次卡壳都是在帮你找弱点卡壳的地方越多复盘的价值越大。1.2 我的三轮复盘节奏是怎么定的二刷不是刷一遍就完了至少要拆成几个轮次不然还是囫囵吞枣。我当时把时间排成了三轮每轮目的完全不同第一轮广度覆盖。把OJ题库里所有涉及复试范围的基础题全部过一遍不追求难题目标是熟悉题型标记出自己完全没头绪的题目。第二轮专题攻坚。按照数据结构、搜索、图论、动态规划等专题分组刷解决第一轮遗留的难点并针对每个专题做三类事的对比练习模板题、变形题、综合题。第三轮整体复盘。也就是这篇“复盘3”把第二轮刷过但AC不稳定的题再做一遍模拟现场机试环境限时完成整理错题档案。这个节奏的前提是我有一个Excel表格记录状态。每道题一行列分别是题号、难度、一刷状态、二刷状态、第一思路是否正确、错误类型、是否需要三刷。表格看着朴素实际价值比很多人想象的都大因为机试备考最怕的就是刷了多少题不知道自己会什么表格能让你随时知道自己的真实水平分布在哪。1.3 复盘记录表应该记什么不该记什么复盘记录表不是题解抄写本不需要把完整代码贴进去只需要记录关键信息。我建议每一行至少包含这几个字段题目类型关键词比如“最短路”“区间DP”方便按专题筛选。一刷是否通过通过/看题解通过/未通过。二刷是否独立写出这是最关键的字段独立写出才叫会。卡壳点描述记录当时卡在哪个环节是状态定义想不出来还是边界条件漏了还是建图的思路歪了。一题多解备注如果有更好的解法用一句话记下来不展开写。不记什么不记AC后的全代码不记题解原文。因为这些内容会给你“我已经掌握了”的错觉。记录是为了触发回忆不是为了让记录本身看起来完整。2. 高频考点分布与题型规律2.1 各知识模块出现频率统计结合学校前几年复试命题规律和我自己刷题时的观察我把考点模块按出现频率排了个序模块典型题型出现频率核心能力模拟与字符串处理日期计算、文本处理、进制转换很高细心、边界处理排序与查找结构体排序、二分查找很高对库函数的熟练度搜索BFS最短步数、DFS回溯高状态设计、剪枝树与遍历二叉树重建、遍历序列中高递归思维图论最短路、最小生成树中高模板熟练度、变形能力动态规划线性DP、背包、区间DP中状态定义、转移推导数学素数、最大公约数、大数运算中数论基础贪心区间调度、背包变体中低证明能力这个表不是绝对的但高频模块之间的权重差异很明显。如果复习时间紧张模拟和搜索建议优先保底这两个模块最容易出题也最容易拿分图论和DP决定上限复试想拿高分必须啃下来。2.2 每类题型的核心竞争力是什么模拟题和字符串题表面上简单实则是失分重灾区核心能力是“细心”。题目描述里的每个条件都可能变成测试点比如“按字典序输出”“忽略前导零”“可能存在空行”漏掉一个就得白白丢掉AC。复现这类题的唯一方法是多读题、逐字抠细节。搜索题的核心是状态设计。BFS的“状态”不一定是二维坐标可能是三维、四维的复合状态比如“位置步数奇偶”“位置钥匙状态”。能想到把哪些信息装进状态里比会写队列难得多。DFS回溯的核心则是顺序和剪枝不同顺序的搜索树大小差很多全排列类题目不排序就剪枝效率能差几个数量级。图论题的核心是把模板变成条件反射。最短路的五种写法、并查集的路径压缩、最小生成树的两种算法这些必须做到闭着眼能写。考场上没有时间现场推演模板不熟就是送分题变送命题。变形题的难点在于“识破”一个问题看起来不像最短路但建个图、把代价抽象成边权以后就是裸的最短路。动态规划的核心是状态定义这也是大多数人的死穴。转移方程可以推状态定义想错了方向后面全白搭。我的经验是拿到一个DP题优先想“如果我只知道全局的第i个变量我能描述清楚当前局面吗”能那大概率就是一个一维状态不能就往二维、三维扩展。2.3 冷门但容易翻车的题型复盘的时候我还特意统计了“冷门但一出现就翻车”的题型这类题平时刷得少考场上遇到容易懵。主要集中在这几类大数运算不涉及高精度库函数要求自己写字符串加法乘法很多人到了考场手写高精度直接乱套。二进制与位运算判断二进制中1的个数、子集枚举、状态压缩知识点浅但平时不练会生疏。素数筛与质因数分解埃氏筛、线性筛的边界条件比较多一紧张容易写错。浮点数输出精度如果题目要求保留若干位小数输出格式错等价于零分体验极差。所以二刷的时候我特意给这些“低频但高杀伤”的题目留了时间每类挑三五道练手不求精通但求到时不慌。这也是一种很划算的时间投资。3. 二刷重点题目复盘从思路到代码3.1 最短路变体把“本质”吃透比背模板重要学校OJ上有一道题我很推荐复盘给定N个城市和M条道路每条道路有通行时间和通行费用要求在限定时间内从起点到达终点求最小费用。表面上看它是最短路但每个节点维护的值不再是单一的最短距离而是一个二元组当前时间当前费用。我第一次做这道题的时候直接套了Dijkstra模板结果样例都过不了因为优先级队列里只存了一个距离值松弛的时候发现要么时间超了、要么费用不是最优。后来才想明白这里要分两层看第一层是“时间约束”作为过滤条件第二层是“费用最小”作为优化目标。可以定义一个结构体保存状态struct Node { int city; int time; int cost; bool operator(const Node other) const { return cost other.cost; // 费用小的优先 } };每次从堆顶取一个状态出来先判断当前时间是否超限超了直接丢弃然后检查当前位置与费用组合是不是已经比之前记录的状态差是就跳过。这样做的好处是不用对时间维度单独开一个大数组只要 cost 数组记录的是“在某个时间范围内的最小费用”就能保证正确性。这道题让我意识到模板背得再熟也得先想清楚“图上每个点存的是什么信息”也就是状态空间怎么建模。最短路的本质是状态图上的最优转移点的含义可以由你自由定义定义对了就成功了一半。3.2 回溯搜索暴搜也要有章法复试OJ的DFS题一般不会考太深的剪枝但也不容小觑。有一道排列生成题输入n个数字输出所有不重复的全排列数字中含有重复元素。这个题看似简单实际暗藏两个坑一是“不重复”三个字二是输出顺序要按字典序。我一开始的做法是生成所有排列后用集合去重小数据能过数据一多直接超时时间都浪费在反复生成重复排列上。后来改用经典做法先排序然后DFS时跳过和前一个元素相同的分支。关键代码是这样void dfs(int depth) { if (depth n) { for (int i 0; i n; i) { printf(%d%c, nums[i], i n - 1 ? \n : ); } return; } for (int i depth; i n; i) { // 跳过重复元素 bool dup false; for (int j depth; j i; j) { if (nums[j] nums[i]) { dup true; break; } } if (dup) continue; swap(nums[depth], nums[i]); dfs(depth 1); swap(nums[depth], nums[i]); // 回溯还原 } }这个剪枝方式很多人不理解觉得对同一个位置的枚举交换到前面的元素如果和之前某个元素相等就会造成重复所以在交换前要检查一遍。二刷的时候我把这段逻辑推导了好几遍才真正理解它等价于“每个位置上相同值的元素只能放一次”。复盘这类题我最大的体会是暴搜题不丢人丢人的是暴搜没有章法。回溯时恢复现场的习惯、去重时先排序的习惯这些细节决定了考场上能不能一遍过样例。3.3 动态规划状态设计永远排在转移方程前面DP题是复试中的分水岭也是二刷复盘时最值得花时间的部分。我挑一道区间DP的经典题型来说给定一个字符串求最长的回文子序列长度。因为子序列不要求连续可以跳过某些字符。第一次做这题时我的第一反应是枚举所有子序列复杂度想都不敢想。后来学到区间DP的状态设计思路dp[l][r] 表示字符串从下标l到下标r这个闭区间内最长回文子序列的长度。这个设计的巧妙之处在于区间长度从短到长扩展每个状态只依赖两个相邻的短区间for (int len 2; len n; len) { for (int l 0; l len - 1 n; l) { int r l len - 1; if (s[l] s[r]) { dp[l][r] dp[l 1][r - 1] 2; } else { dp[l][r] max(dp[l 1][r], dp[l][r - 1]); } } }这个转移看起来很自然但难点根本不在这里而在“为什么dp[l][r]要定义成闭区间而不是开区间”“为什么长度要从2开始枚举”“空串和长度为1的串怎么初始化”。这些问题想通了区间DP的题基本就拿下了。我复盘DP题的方法很笨但很有效每道题都问自己三个问题。第一状态表示的是“什么情况下”的“什么值”第二我当前状态能从哪些相邻状态推过来第三初始化边界是多少。很多DP题不会做都是因为第一个问题没想清楚就急着套公式。4. 二刷实测踩坑记录与排查思路4.1 数组开小引发的连锁事故这是复盘里翻车次数最多的一类问题。有一道图论题我按题意开了100个节点的邻接矩阵结果提交后一直RE。我一开始怀疑是栈溢出又怀疑是递归爆栈折腾了半小时才发现题目里还隐藏了一个多次输入的测试点每次输入都会构建新图而我存边的数组只在程序启动时初始化一次次数一多数组越界。用表格记录一下这类问题问题现象根因排查思路本地正常运行OJ提交RE数组越界或野指针检查所有数组大小是否和最大范围一致尤其注意“每组测试”之间的残留小数据过大数据RE递归深度过大或数组开小了扩大静态数组用迭代代替递归运行时偶尔出错未检查下标负数在取值前加越界判断尤其是逆序访问时后来我给自己定了一条铁律凡是涉及数组下标的地方先确认范围再用常量定义数组大小。宁可多开一倍空间也不要为省内存埋雷。4.2 输入输出在OJ上的特殊怪癖复试OJ的测试数据经常不是一组而是“多组输入直到EOF”这个点我非常容易忘。一刷时我习惯写单组输入样例能过就完事提交就WA后来才发现题目描述里写着“输入包含多组测试数据”。多组输入的专用写法其实很固定int n, m; while (scanf(%d %d, n, m) ! EOF) { // 每组数据重新初始化 memset(graph, 0, sizeof(graph)); // 核心逻辑 }还有一个坑是输出格式。题目要求每个测试用例输出一个空行或者“Case #1:”前缀顺序错一点都不给分。我的习惯是先写死一串printf把样例的输出部分逐字符对一遍再提交。这在OJ类的判题规则里是个保命习惯。另外scanf和printf稳定性和速度都优于cin和cout。除非题目里明确使用C非基础类型否则我全程都用scanf/printf。复试环境不一定开了同步优化稳妥为上。4.3 从TLE到AC的优化步骤二刷时有一道二维数组求和的题我先用了三层循环暴力算子矩阵和样例能过一旦数据量上来就TLE。怎么优化的第一步先写前缀和把每次查询的复杂度从O(N*M)降到O(1)。第二步把查询循环里的重复计算提到了外面。第三步确认IO是scanf而不是cin。TLE的排查顺序很有讲究我建议按“算法复杂度、数据结构选择、代码常数”三步走。大多数时候卡你的是算法复杂度比如没看到题目中的N上限是10^5还在用O(N^2)的嵌套循环。优先后记得提交前自己造一组最大数据测一下别指望OJ帮你测到所有边界。还有一类优化是降低常数。比如桶排序代替sort、用数组代替vector、提前break减少循环次数等。这些优化虽然不能改变复杂度量级但在数据极限的测试点上常常就是AC和TLE的分界线。4.4 评测环境的差异本地能跑不代表能过本地VS环境差异造成的编译或运行错误在复试OJ里很常见。我最常踩的是三个第一变量重名和全局变量未初始化。本地调试可能用其他编译器对未初始化变量是0但评测机上新开一块内存就是随机值全局变量的默认初始化规则是0局部变量不是。我吃过一次亏后所有需要默认值的变量一律显式初始化。第二输出浮点数时的格式精度。有的评测系统里printf的%lf和%f行为不一样最好按题目要求原样复制格式不要自由发挥。第三不同平台上 int 和 long long 的字节数一样但运算时乘积溢出隐患存在。只要题目数据范围超过2×10^9我全部用long long加法乘法一律加上LL后缀。复试OJ的评测系统一般比较严格建议在考试前几天就把环境调成和考场一致尽量提前适应。5. 复盘方法论沉淀二刷到底要刷到什么程度5.1 错题处理不是标红就完事很多人复盘第一个错误做法是把错题标红然后就不管了。我这里提供一个我自己实践有效的流程适用于所有复试OJ错题第一步当场分析错误类型。是思路不对、代码写错还是边界漏判这个判断一定在提交后十分钟内完成不然记忆会模糊。第二步不看题解重写一遍。如果看了题解才能写出来说明这道题还没变成自己的应该再等一天后重新做。第三步隔天再做一次。二刷的精髓就在这里隔天做一次能检验你是否真的掌握了而不是把题解背下来了。只有三次都能独立AC的题我才会在回顾表里把状态改成“已掌握”。其余题目全部继续留在待办清单。5.2 训练“白板写代码”的能力复试机试和平时写代码最大的区别是紧迫感在考场的压力下人很容易写三行就想去编译一下看看有没有语法错误。这种依赖不能带到考场所以我后来专门练“一次写对”的能力平时做题时强制自己不在IDE里逐步调试而是像考试一样一次写完再检测。具体做法是拿到题目先手写思路草稿再打开编辑器直接写完整代码写完走读一遍再编译。一开始很不习惯经常因为一个拼写错误花费大量时间但坚持两周以后写代码的准确率提升非常明显。这个能力在复试机试时间紧张的时候价值巨大。5.3 建立自己的“模板库”二刷中期我开始整理自己的模板库不是网上抄来的而是每道题落笔写完后抽出其中可复用的算法骨架保存下来。模板库的分类很朴素包括输入输出模板、二分查找模板、快速排序或sort的用法、BFS队列模板、DFS递归框架、并查集实现、Dijkstra堆优化模板、区间DP模板。这个模板库不停更新二刷后期几乎每道题我都能从库里找到对应的骨架再按题目要求微调。复试考场时间有限把基础模板写成熟的体力活提前练好才能真正把时间留给思路思考。5.4 复盘收尾阶段的模拟练习到二刷收尾我停止了刷题式练习改为按复试标准进行模拟。每天固定一套题定时两小时操作流程和考场完全一致环境尽量用机房的Linux命令行或类似环境不允许查资料不允许复制模板写完就走读检查再提交。这样练了五天最后正式复试时心态稳了很多因为已经把考试的紧张感提前体验过了。模拟练习比继续刷题更有价值的地方在于它会暴露你在综合题面前的调度问题。比如有一道题明显是DP但你半小时内写不出来该不该放弃转做下一题模拟就是帮你提前想好这种策略的时刻。二刷复盘到这里其实已经接近我在复试前的最后一次系统总结了。回头看第一轮刷题是“看见题”第二轮刷题是“会做题”第三轮复盘才算真正把题目内化成自己的东西。尤其模拟练习那几套题每次提交前我都强迫自己按“读题→设计状态→写代码→走查”的顺序执行几次下来面对陌生题目的恐惧感明显降低了。最后再分享一个小技巧二刷后期每次学完一个专题我会在当天睡觉前用五分钟把做过的题目在脑海里“回忆一遍”——不翻代码只回忆题目长什么样、我当时卡在哪、正确答案大概长什么样。这个动作看着简单但长期坚持下来知识留存率比单纯多刷题高得多。如果你也在准备某所学校的复试OJ建议别一味堆题量把二刷的每一道错题重复三遍比刷三十道新题更管用。
第三次写这套题的复盘了。二刷某高校复试OJ的整个过程前后横跨了三周这一轮复盘我本来只想整理个错题清单结果翻回去看第一轮的做题记录很多当时感觉“我明白了”的题现在重新上手还是要卡一下尤其是图论和动态规划思路不到位就是写不出AC代码。复试的机试不像笔试代码提交上去当场判定对了就过错了就是零分没有情面可讲。这篇复盘想写给两类人一类是正在准备计算机类、软件类考研复试机试的同学另一类是刷了不少题但总觉得没沉淀下来的同学。我先说说背景。报考学校自建的OJ系统题量不小复试成绩里机试占比很重题目难度介于传统ACM入门题和课程作业之间考的是熟练度和基础算法的基本功。第一次刷的时候我比较莽按题号顺序从前往后AC一道忘一道。二刷才老老实实按专题、按难度重新过了一遍这一遍的效果比一刷好太多。如果你也正在准备类似的复试机试这篇复盘里的题型分布、重点算法思路、踩坑记录和复盘方法论应该能帮你少走不少弯路。1. 复盘之前先把“二刷”这件事想明白1.1 一刷和二刷的本质区别在哪里很多人刷题只刷一遍觉得见过、AC过就等于掌握了其实这是最大的错觉。一刷的典型状态是“刷题像追剧”看完题解觉得懂了照抄一遍AC了第二天再问自己“为什么这么做”往往说不上来。二刷的核心不是把题再看一遍而是合上题解、不看笔记凭记忆和推导把代码写出来再和第一次的解法对比找出差距。我用一个很通俗的比喻来理解这件事一刷是在认路二刷是在自己开一遍车。认路的时候你坐在副驾驶旁边有人指挥路口怎么走都是别人告诉你的二刷是把导航关掉自己开到终点真开错几次才能记得住。复试考场上没有题解也没有人指挥你能依赖的只有脑子里真正沉淀下来的路径。所以二刷和“再看一遍”完全是两码事。二刷的精髓是主动回忆或者叫“提取练习”。这个过程中每一次卡壳都是在帮你找弱点卡壳的地方越多复盘的价值越大。1.2 我的三轮复盘节奏是怎么定的二刷不是刷一遍就完了至少要拆成几个轮次不然还是囫囵吞枣。我当时把时间排成了三轮每轮目的完全不同第一轮广度覆盖。把OJ题库里所有涉及复试范围的基础题全部过一遍不追求难题目标是熟悉题型标记出自己完全没头绪的题目。第二轮专题攻坚。按照数据结构、搜索、图论、动态规划等专题分组刷解决第一轮遗留的难点并针对每个专题做三类事的对比练习模板题、变形题、综合题。第三轮整体复盘。也就是这篇“复盘3”把第二轮刷过但AC不稳定的题再做一遍模拟现场机试环境限时完成整理错题档案。这个节奏的前提是我有一个Excel表格记录状态。每道题一行列分别是题号、难度、一刷状态、二刷状态、第一思路是否正确、错误类型、是否需要三刷。表格看着朴素实际价值比很多人想象的都大因为机试备考最怕的就是刷了多少题不知道自己会什么表格能让你随时知道自己的真实水平分布在哪。1.3 复盘记录表应该记什么不该记什么复盘记录表不是题解抄写本不需要把完整代码贴进去只需要记录关键信息。我建议每一行至少包含这几个字段题目类型关键词比如“最短路”“区间DP”方便按专题筛选。一刷是否通过通过/看题解通过/未通过。二刷是否独立写出这是最关键的字段独立写出才叫会。卡壳点描述记录当时卡在哪个环节是状态定义想不出来还是边界条件漏了还是建图的思路歪了。一题多解备注如果有更好的解法用一句话记下来不展开写。不记什么不记AC后的全代码不记题解原文。因为这些内容会给你“我已经掌握了”的错觉。记录是为了触发回忆不是为了让记录本身看起来完整。2. 高频考点分布与题型规律2.1 各知识模块出现频率统计结合学校前几年复试命题规律和我自己刷题时的观察我把考点模块按出现频率排了个序模块典型题型出现频率核心能力模拟与字符串处理日期计算、文本处理、进制转换很高细心、边界处理排序与查找结构体排序、二分查找很高对库函数的熟练度搜索BFS最短步数、DFS回溯高状态设计、剪枝树与遍历二叉树重建、遍历序列中高递归思维图论最短路、最小生成树中高模板熟练度、变形能力动态规划线性DP、背包、区间DP中状态定义、转移推导数学素数、最大公约数、大数运算中数论基础贪心区间调度、背包变体中低证明能力这个表不是绝对的但高频模块之间的权重差异很明显。如果复习时间紧张模拟和搜索建议优先保底这两个模块最容易出题也最容易拿分图论和DP决定上限复试想拿高分必须啃下来。2.2 每类题型的核心竞争力是什么模拟题和字符串题表面上简单实则是失分重灾区核心能力是“细心”。题目描述里的每个条件都可能变成测试点比如“按字典序输出”“忽略前导零”“可能存在空行”漏掉一个就得白白丢掉AC。复现这类题的唯一方法是多读题、逐字抠细节。搜索题的核心是状态设计。BFS的“状态”不一定是二维坐标可能是三维、四维的复合状态比如“位置步数奇偶”“位置钥匙状态”。能想到把哪些信息装进状态里比会写队列难得多。DFS回溯的核心则是顺序和剪枝不同顺序的搜索树大小差很多全排列类题目不排序就剪枝效率能差几个数量级。图论题的核心是把模板变成条件反射。最短路的五种写法、并查集的路径压缩、最小生成树的两种算法这些必须做到闭着眼能写。考场上没有时间现场推演模板不熟就是送分题变送命题。变形题的难点在于“识破”一个问题看起来不像最短路但建个图、把代价抽象成边权以后就是裸的最短路。动态规划的核心是状态定义这也是大多数人的死穴。转移方程可以推状态定义想错了方向后面全白搭。我的经验是拿到一个DP题优先想“如果我只知道全局的第i个变量我能描述清楚当前局面吗”能那大概率就是一个一维状态不能就往二维、三维扩展。2.3 冷门但容易翻车的题型复盘的时候我还特意统计了“冷门但一出现就翻车”的题型这类题平时刷得少考场上遇到容易懵。主要集中在这几类大数运算不涉及高精度库函数要求自己写字符串加法乘法很多人到了考场手写高精度直接乱套。二进制与位运算判断二进制中1的个数、子集枚举、状态压缩知识点浅但平时不练会生疏。素数筛与质因数分解埃氏筛、线性筛的边界条件比较多一紧张容易写错。浮点数输出精度如果题目要求保留若干位小数输出格式错等价于零分体验极差。所以二刷的时候我特意给这些“低频但高杀伤”的题目留了时间每类挑三五道练手不求精通但求到时不慌。这也是一种很划算的时间投资。3. 二刷重点题目复盘从思路到代码3.1 最短路变体把“本质”吃透比背模板重要学校OJ上有一道题我很推荐复盘给定N个城市和M条道路每条道路有通行时间和通行费用要求在限定时间内从起点到达终点求最小费用。表面上看它是最短路但每个节点维护的值不再是单一的最短距离而是一个二元组当前时间当前费用。我第一次做这道题的时候直接套了Dijkstra模板结果样例都过不了因为优先级队列里只存了一个距离值松弛的时候发现要么时间超了、要么费用不是最优。后来才想明白这里要分两层看第一层是“时间约束”作为过滤条件第二层是“费用最小”作为优化目标。可以定义一个结构体保存状态struct Node { int city; int time; int cost; bool operator(const Node other) const { return cost other.cost; // 费用小的优先 } };每次从堆顶取一个状态出来先判断当前时间是否超限超了直接丢弃然后检查当前位置与费用组合是不是已经比之前记录的状态差是就跳过。这样做的好处是不用对时间维度单独开一个大数组只要 cost 数组记录的是“在某个时间范围内的最小费用”就能保证正确性。这道题让我意识到模板背得再熟也得先想清楚“图上每个点存的是什么信息”也就是状态空间怎么建模。最短路的本质是状态图上的最优转移点的含义可以由你自由定义定义对了就成功了一半。3.2 回溯搜索暴搜也要有章法复试OJ的DFS题一般不会考太深的剪枝但也不容小觑。有一道排列生成题输入n个数字输出所有不重复的全排列数字中含有重复元素。这个题看似简单实际暗藏两个坑一是“不重复”三个字二是输出顺序要按字典序。我一开始的做法是生成所有排列后用集合去重小数据能过数据一多直接超时时间都浪费在反复生成重复排列上。后来改用经典做法先排序然后DFS时跳过和前一个元素相同的分支。关键代码是这样void dfs(int depth) { if (depth n) { for (int i 0; i n; i) { printf(%d%c, nums[i], i n - 1 ? \n : ); } return; } for (int i depth; i n; i) { // 跳过重复元素 bool dup false; for (int j depth; j i; j) { if (nums[j] nums[i]) { dup true; break; } } if (dup) continue; swap(nums[depth], nums[i]); dfs(depth 1); swap(nums[depth], nums[i]); // 回溯还原 } }这个剪枝方式很多人不理解觉得对同一个位置的枚举交换到前面的元素如果和之前某个元素相等就会造成重复所以在交换前要检查一遍。二刷的时候我把这段逻辑推导了好几遍才真正理解它等价于“每个位置上相同值的元素只能放一次”。复盘这类题我最大的体会是暴搜题不丢人丢人的是暴搜没有章法。回溯时恢复现场的习惯、去重时先排序的习惯这些细节决定了考场上能不能一遍过样例。3.3 动态规划状态设计永远排在转移方程前面DP题是复试中的分水岭也是二刷复盘时最值得花时间的部分。我挑一道区间DP的经典题型来说给定一个字符串求最长的回文子序列长度。因为子序列不要求连续可以跳过某些字符。第一次做这题时我的第一反应是枚举所有子序列复杂度想都不敢想。后来学到区间DP的状态设计思路dp[l][r] 表示字符串从下标l到下标r这个闭区间内最长回文子序列的长度。这个设计的巧妙之处在于区间长度从短到长扩展每个状态只依赖两个相邻的短区间for (int len 2; len n; len) { for (int l 0; l len - 1 n; l) { int r l len - 1; if (s[l] s[r]) { dp[l][r] dp[l 1][r - 1] 2; } else { dp[l][r] max(dp[l 1][r], dp[l][r - 1]); } } }这个转移看起来很自然但难点根本不在这里而在“为什么dp[l][r]要定义成闭区间而不是开区间”“为什么长度要从2开始枚举”“空串和长度为1的串怎么初始化”。这些问题想通了区间DP的题基本就拿下了。我复盘DP题的方法很笨但很有效每道题都问自己三个问题。第一状态表示的是“什么情况下”的“什么值”第二我当前状态能从哪些相邻状态推过来第三初始化边界是多少。很多DP题不会做都是因为第一个问题没想清楚就急着套公式。4. 二刷实测踩坑记录与排查思路4.1 数组开小引发的连锁事故这是复盘里翻车次数最多的一类问题。有一道图论题我按题意开了100个节点的邻接矩阵结果提交后一直RE。我一开始怀疑是栈溢出又怀疑是递归爆栈折腾了半小时才发现题目里还隐藏了一个多次输入的测试点每次输入都会构建新图而我存边的数组只在程序启动时初始化一次次数一多数组越界。用表格记录一下这类问题问题现象根因排查思路本地正常运行OJ提交RE数组越界或野指针检查所有数组大小是否和最大范围一致尤其注意“每组测试”之间的残留小数据过大数据RE递归深度过大或数组开小了扩大静态数组用迭代代替递归运行时偶尔出错未检查下标负数在取值前加越界判断尤其是逆序访问时后来我给自己定了一条铁律凡是涉及数组下标的地方先确认范围再用常量定义数组大小。宁可多开一倍空间也不要为省内存埋雷。4.2 输入输出在OJ上的特殊怪癖复试OJ的测试数据经常不是一组而是“多组输入直到EOF”这个点我非常容易忘。一刷时我习惯写单组输入样例能过就完事提交就WA后来才发现题目描述里写着“输入包含多组测试数据”。多组输入的专用写法其实很固定int n, m; while (scanf(%d %d, n, m) ! EOF) { // 每组数据重新初始化 memset(graph, 0, sizeof(graph)); // 核心逻辑 }还有一个坑是输出格式。题目要求每个测试用例输出一个空行或者“Case #1:”前缀顺序错一点都不给分。我的习惯是先写死一串printf把样例的输出部分逐字符对一遍再提交。这在OJ类的判题规则里是个保命习惯。另外scanf和printf稳定性和速度都优于cin和cout。除非题目里明确使用C非基础类型否则我全程都用scanf/printf。复试环境不一定开了同步优化稳妥为上。4.3 从TLE到AC的优化步骤二刷时有一道二维数组求和的题我先用了三层循环暴力算子矩阵和样例能过一旦数据量上来就TLE。怎么优化的第一步先写前缀和把每次查询的复杂度从O(N*M)降到O(1)。第二步把查询循环里的重复计算提到了外面。第三步确认IO是scanf而不是cin。TLE的排查顺序很有讲究我建议按“算法复杂度、数据结构选择、代码常数”三步走。大多数时候卡你的是算法复杂度比如没看到题目中的N上限是10^5还在用O(N^2)的嵌套循环。优先后记得提交前自己造一组最大数据测一下别指望OJ帮你测到所有边界。还有一类优化是降低常数。比如桶排序代替sort、用数组代替vector、提前break减少循环次数等。这些优化虽然不能改变复杂度量级但在数据极限的测试点上常常就是AC和TLE的分界线。4.4 评测环境的差异本地能跑不代表能过本地VS环境差异造成的编译或运行错误在复试OJ里很常见。我最常踩的是三个第一变量重名和全局变量未初始化。本地调试可能用其他编译器对未初始化变量是0但评测机上新开一块内存就是随机值全局变量的默认初始化规则是0局部变量不是。我吃过一次亏后所有需要默认值的变量一律显式初始化。第二输出浮点数时的格式精度。有的评测系统里printf的%lf和%f行为不一样最好按题目要求原样复制格式不要自由发挥。第三不同平台上 int 和 long long 的字节数一样但运算时乘积溢出隐患存在。只要题目数据范围超过2×10^9我全部用long long加法乘法一律加上LL后缀。复试OJ的评测系统一般比较严格建议在考试前几天就把环境调成和考场一致尽量提前适应。5. 复盘方法论沉淀二刷到底要刷到什么程度5.1 错题处理不是标红就完事很多人复盘第一个错误做法是把错题标红然后就不管了。我这里提供一个我自己实践有效的流程适用于所有复试OJ错题第一步当场分析错误类型。是思路不对、代码写错还是边界漏判这个判断一定在提交后十分钟内完成不然记忆会模糊。第二步不看题解重写一遍。如果看了题解才能写出来说明这道题还没变成自己的应该再等一天后重新做。第三步隔天再做一次。二刷的精髓就在这里隔天做一次能检验你是否真的掌握了而不是把题解背下来了。只有三次都能独立AC的题我才会在回顾表里把状态改成“已掌握”。其余题目全部继续留在待办清单。5.2 训练“白板写代码”的能力复试机试和平时写代码最大的区别是紧迫感在考场的压力下人很容易写三行就想去编译一下看看有没有语法错误。这种依赖不能带到考场所以我后来专门练“一次写对”的能力平时做题时强制自己不在IDE里逐步调试而是像考试一样一次写完再检测。具体做法是拿到题目先手写思路草稿再打开编辑器直接写完整代码写完走读一遍再编译。一开始很不习惯经常因为一个拼写错误花费大量时间但坚持两周以后写代码的准确率提升非常明显。这个能力在复试机试时间紧张的时候价值巨大。5.3 建立自己的“模板库”二刷中期我开始整理自己的模板库不是网上抄来的而是每道题落笔写完后抽出其中可复用的算法骨架保存下来。模板库的分类很朴素包括输入输出模板、二分查找模板、快速排序或sort的用法、BFS队列模板、DFS递归框架、并查集实现、Dijkstra堆优化模板、区间DP模板。这个模板库不停更新二刷后期几乎每道题我都能从库里找到对应的骨架再按题目要求微调。复试考场时间有限把基础模板写成熟的体力活提前练好才能真正把时间留给思路思考。5.4 复盘收尾阶段的模拟练习到二刷收尾我停止了刷题式练习改为按复试标准进行模拟。每天固定一套题定时两小时操作流程和考场完全一致环境尽量用机房的Linux命令行或类似环境不允许查资料不允许复制模板写完就走读检查再提交。这样练了五天最后正式复试时心态稳了很多因为已经把考试的紧张感提前体验过了。模拟练习比继续刷题更有价值的地方在于它会暴露你在综合题面前的调度问题。比如有一道题明显是DP但你半小时内写不出来该不该放弃转做下一题模拟就是帮你提前想好这种策略的时刻。二刷复盘到这里其实已经接近我在复试前的最后一次系统总结了。回头看第一轮刷题是“看见题”第二轮刷题是“会做题”第三轮复盘才算真正把题目内化成自己的东西。尤其模拟练习那几套题每次提交前我都强迫自己按“读题→设计状态→写代码→走查”的顺序执行几次下来面对陌生题目的恐惧感明显降低了。最后再分享一个小技巧二刷后期每次学完一个专题我会在当天睡觉前用五分钟把做过的题目在脑海里“回忆一遍”——不翻代码只回忆题目长什么样、我当时卡在哪、正确答案大概长什么样。这个动作看着简单但长期坚持下来知识留存率比单纯多刷题高得多。如果你也在准备某所学校的复试OJ建议别一味堆题量把二刷的每一道错题重复三遍比刷三十道新题更管用。
