Day9这个编号对于备考408和复试机试的人来说不只是“又学了九天”那么简单。它通常意味着基础语法和简单模拟题已经过完第一轮正要开始碰数据结构核心算法的那道坎。我在自己的机试复习计划里也是从第9天开始明显感觉题目难度上了一个台阶不再是无脑写循环而是要依靠递归、树、图这些真正的算法工具去解题。这篇内容就复盘一下我当时Day9是怎么安排的同一天练了哪些题型踩过哪些输入输出和调试的坑以及怎么把408统考和上机训练放在同一天还能保持效率。如果你准备的是复旦这类上机环节占比不低的院校或者只是单纯想把算法基本功打扎实这份Day9的记录可以直接拿来当模板用。1. Day9在机试备考路线中的定位与计划拆解1.1 机试备考的四个阶段Day9属于哪个区间机试的准备周期我习惯分成四个阶段。第一阶段是Day1到Day8主要做三件事熟悉C的STL、过一遍基本语法、刷大量“简单模拟题”。所谓简单模拟就是你输入什么就输出什么不需要太多算法思想只要把题目描述翻译成代码就行。这个阶段的目标只有一个让你提起键盘就能把想法写出来不会因为语法不熟而卡住。第二阶段就是Day9到Day16开始进入数据结构的算法专题栈、队列、链表、哈希、二叉树、并查集、图论基础。这个阶段的核心任务和第一阶段完全不同不是“会写代码”而是“会套模板”并且要理解每个模板为什么这样写。第三阶段是Day17到Day24做专题强化和限时训练。每一类题不再允许慢慢想而是要求15到20分钟内完成模拟考场压力。第四阶段是考前最后一周只做两件事整套机试模拟卷限时训练以及熟悉考场环境。为什么这样分阶段因为机试考的从来不是智商而是熟练度。知识只有从“看着题解能看懂”变成“不看题解能直接写出来”考试时才有可能在有限时间内完成。Day9正好卡在第二个阶段的开头是新旧知识的分界点。1.2 第9天的特殊性为什么这一天最容易拉开差距前八天的内容大部分人都能咬牙坚持下来因为模拟题再难也只是多写几行代码。但一到Day9面对二叉树的后序遍历递归、并查集的路径压缩这些概念很多人就会明显感觉“脑子转不过来了”。我自己复习到Day8的时候写的代码基本还是“主函数从头写到尾”的暴力解法。到了Day9开始学树的递归第一次意识到代码的流程不完全由我来控制而是由数据结构本身的定义来决定。你给我一棵树递归的时候它是先走左边还是先走右边本质上是树的结构说了算不是我在脑子里一步步模拟出来的。这种思维转变就是机试第一道分水岭。能扛过这个阶段的人后面学图论会轻松很多扛不过去就会一直停留在“会做简单题、但中等题完全没思路”的水平。所以Day9真正要训练的不是某个具体算法而是建立“递归直觉”和“抽象建模”的能力。1.3 同时兼顾408统考与机试复习的时间分配到了Day9这个节点408四门课的统考复习不能停机试训练也不能放松很多人的第一反应是焦虑一天就24小时哪来那么多时间我的做法是给两件事分主次但不是简单的五五开。上午精神最好的时间段留给机试通常安排两个半到三个小时。下午留给408的统考复习以真题和教材为主。晚上的时间用来复盘把当天机试的错题和模板重新整理一遍再挤半小时背背操作系统的概念题。具体到时间段大概是这个样子时间段内容目标8:00 - 9:00408科目中的零散知识点记忆用琐碎时间维持统考进度10:00 - 12:30机试专题训练完成当天算法学习目标14:30 - 16:30408统考真题或教材精读保持统考复习节奏19:30 - 21:00机试复盘 第二天计划把当日内容变成长期记忆为什么机试优先放在上午因为编程是需要高度集中注意力的活动上午头脑清醒写代码的效率最高。408统考虽然重要但更多是积累性的科目下午状态稍微弱一点也能看进去。两个月的备考周期里这种分配让我的机试水平得到明显提升同时408的进度也没有落下。2. 408四门科目对机试的支撑点分析2.1 数据结构是机试复习中的绝对核心如果你问一个经历过机试的过来人复试上机最常考哪类题答案几乎都是数据结构。这不是偶然机试命题老师通常是教授数据结构的老师他们最熟悉的考核方式就是树、图、排序和字符串处理。具体来说树的遍历对应递归和深度优先搜索图的最短路径问题对应Dijkstra算法拓扑排序对应图论基础连通块数量对应并查集排序和查找对应的则是归并排序、堆排序和二分查找。这些内容在408统考的数据结构科目中都有但两者考察方式完全不同。统考考的是“给你一段伪代码问你时间复杂度是多少”机试考的是“给你一个实际问题你能不能写出可运行的代码”。所以我在机试准备中把数据结构的优先级拉到了最高。每天至少保证有一个小时在写树的递归或者图的遍历在此基础上才谈得上其他的算法专题。2.2 操作系统、计网、组成原理与机试的关联度很多408考生会犯一个错误四门课平均分配机试复习时间。实际上机试中对操作系统、计算机网络、计算机组成原理的直接考察远少于数据结构。操作系统在机试中比较常见的出现方式是“模拟题”比如进程调度算法的模拟给你一批进程和到达时间要求输出某个调度策略下的执行顺序又比如死锁的银行家算法本质上是一个状态判断问题。这类题考察的重点不是操作系统理论有多深而是你能不能把状态机用代码写出来。计算机网络在机试中的占比更低最多会出现子网掩码计算、CRC校验之类的计算题但这些知识点在408统考复习中顺带就掌握了不需要单独刷题。计算机组成原理和机试的交集就更少偶尔考一下进制转换或者补码运算都是纯送分题。四门课的优先级可以参照下面这张表408科目机试高频题型备考优先级数据结构树、图遍历、并查集、排序、哈希、字符串匹配极高操作系统进程调度模拟、死锁判断、银行家算法、页表模拟中计算机网络子网划分、CRC校验、拥塞窗口计算低计算机组成原理进制转换、补码计算、Cache映射模拟低之所以这样分配是因为机试的命题范围其实比408统考窄很多。数据结构是上机考试的核心考察点操作系统偶尔作为背景出现其他两门基本不用在机试上专门花时间。3. Day9实战内容拆解二叉树递归与并查集模板3.1 Day9的专题选择为什么是二叉树和并查集第9天我没有直接去刷图论题而是安排了二叉树和并查集两个专题。原因是这两块内容刚好构成后面学习更复杂算法的“前置技能”。二叉树的递归是理解深度优先搜索的基础。树本身就是递归结构每个结点的左子树和右子树还是一棵树那么对整棵树的操作天然就可以通过“对根结点做什么 对左子树递归 对右子树递归”来实现。学完二叉树递归再去看图的深度优先遍历思路几乎是平移过去的。并查集则是图论专题的敲门砖。很多图相关的问题比如判断两个点是否连通、计算连通分量个数用并查集比直接用DFS或BFS代码更简洁也更容易写对。把这两个专题放在同一天一个侧重思维训练一个侧重模板记忆学习过程中不容易疲劳效率也高。3.2 二叉树遍历的递归模板与层序实现二叉树相关题目在机试中出现频率极高而遍历是一切操作的基础。以下是一套我在Day9当天整理的C模板直接涵盖了前序、中序、后序和层序遍历。#include iostream #include queue using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 前序遍历根 - 左 - 右 void preorder(TreeNode* root) { if (root nullptr) return; cout root-val ; preorder(root-left); preorder(root-right); } // 中序遍历左 - 根 - 右 void inorder(TreeNode* root) { if (root nullptr) return; inorder(root-left); cout root-val ; inorder(root-right); } // 后序遍历左 - 右 - 根 void postorder(TreeNode* root) { if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-val ; } // 层序遍历按层从左到右输出 void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); for (int i 0; i size; i) { TreeNode* cur q.front(); q.pop(); cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } cout endl; } }递归的出口条件为什么是root nullptr因为这是递归的“基情况”当访问到空结点时说明这一支已经走到头了直接返回不做任何操作。前序、中序、后序的代码结构几乎一样唯一区别是cout这行代码放在递归调用前、中间还是后面。这个顺序决定了访问结点的时机。层序遍历之所以用队列是因为队列先进先出可以保证同一层的结点按从左到右的顺序被处理。如果用栈就会变成深度优先顺序完全不对。3.3 并查集模板与易错点并查集的原理可以理解成一个“朋友圈”管理工具每个人的信息记录在一个数组里初始时每个人都是自己的老大当两个人有关系时就把其中一个人的老大改成另一个人的老大判断两个人是不是一个圈子就看两个人的最终老大是不是同一个人。下面是机试中最常用的并查集模板#include iostream using namespace std; const int MAXN 100010; int parent[MAXN]; // 查找根节点并进行路径压缩 int find(int x) { if (parent[x] x) return x; return parent[x] find(parent[x]); } // 合并两个集合 void merge(int a, int b) { int ra find(a); int rb find(b); if (ra ! rb) { parent[ra] rb; } } int main() { int n, m; cin n m; for (int i 1; i n; i) { parent[i] i; } while (m--) { int op, a, b; cin op a b; if (op 1) { merge(a, b); } else { if (find(a) find(b)) { cout Y endl; } else { cout N endl; } } } return 0; }这里最关键的是find函数里的路径压缩parent[x] find(parent[x])。朴素版本只返回祖先不改变路径多次调用后树会越来越高最坏情况退化成链表。路径压缩让每次查找都把沿途结点直接挂到根节点下面后续查找复杂度摊还下来接近常数时间。写并查集时容易踩的坑有这几个。第一初始化从1到n不要漏掉下标0。第二合并时先find再比较两个结点可能本来就在同一个集合里。第三判断连通时一定要调find不能直接比较parent[a] parent[b]因为没做路径压缩以前两个结点的父节点可能不同但最终祖先相同。4. 机试实战中的输入输出处理与调试经验4.1 在线评测OJ的输入输出陷阱机试是在在线评测系统上进行的代码不是给人看而是给机器判分。这就导致输入输出比正常的开发环境严格得多也坑得多。最常见的坑是“多组输入”。很多题目不给测试组数直接是一组数据直到文件结束。正确的写法是用while (scanf(%d, n) ! EOF)或者用C的while (cin n)。如果你只读一次样例可能跑得出来但后台评测数据里只要有多组输入程序就直接只跑了一遍后半部分完全错误。第二个坑是输出格式。机试要求输出什么就输出什么不要加任何多余提示语。“请输入n”这种在本地控制台很友好的写法在OJ上会被当成多余字符直接判错。行末空格也是重灾区有好多题对空格敏感可以在输出循环里用i 0 ? cout val : cout val这样的写法控制空格。第三个坑是换行。经常有题目要求每一组输出的结果之间空一行或者每组结尾多一个换行这些题面里都会写明。但很多人读题不仔细样例能过就提交结果被这种格式分反复扣。4.2 调试三板斧打印、断点、对拍机试复习过程中调试能力甚至比算法能力更重要。我自己的调试方法通常分三个层次。第一个层次是打印法。在关键变量和分支处加cout把中间结果打出来。比如并查集合并之后打印一下parent数组就能立刻看出合并逻辑对不对。好处是直接简单坏处是每次都要重新编译调试完容易忘了删调试代码。第二个层次是用IDE的断点调试。单击行号打上断点运行到断点处程序会停住这时候可以一行一行地看变量变化。这个方法适合排查数组越界、指针问题这种比较难定位的错误。缺点是断点调试比较慢少量数据还行数据量大一点就很不方便。第三个层次是对拍。这个方法是我觉得切入机试效率提升最大的技巧。实现方式是写一个保证正确的暴力程序哪怕时间复杂度很高再写一个你正在验证的高效程序然后写一个随机数据生成器分别跑这两个程序反复比较输出是否一致。举例来说写了一个快速排序版本担心边界条件写错就写一个冒泡排序的暴力版生成100组随机数组两个程序跑出来的排序结果必须完全一样。只要有一组不一致就说明新代码在某个边界上出了问题。这个方法能帮你自动发现隐藏的bug比肉眼一行行检查高效得多。4.3 机试中代码常见的几个隐蔽坑实操中有些错误非常隐蔽样例完全测不出来。这里整理几个我踩过、也被身边同学反复踩的cin/cout性能问题。在线评测系统的数据量动辄十万、百万级别默认状态下cin/cout比scanf/printf慢很多。要么直接全部用scanf/printf要么在main最开头加两行ios::sync_with_stdio(false); cin.tie(nullptr);可以大幅提升读写速度。endl会刷新缓冲区。cout endl不仅要换行还会清空输出缓冲区这个操作很耗时。大批量输出时应该用\n。数组大小开小了。有些题要求结点数最大是100000你开成10000本地测试没问题评测系统直接段错误。建议数组按题面最大值再乘以2或者直接用vector动态分配。递归爆栈。树的深度达到几万层递归可能直接把栈空间耗尽。某些OJ的栈空间很小这时候要把递归改成循环或者用vector模拟栈。使用long long的习惯。涉及加法、乘法结果可能超过int范围的题目一定要用long long否则溢出后数值变负数查半天查不出来。4.4 样例通过但提交错误的排查顺序“样例能过提交就错”应该是所有机试党最崩溃的时刻。遇到这种情况我的排查顺序很固定按顺序来能省一半时间。第一检查边界条件。题目说了n的范围至少要测n 0、n 1、n 最大值这三种情况。很多错误都出在“长度为1的数组”“空树”“空串”这种极端输入上。第二检查全局变量是否需要重置。在循环中处理多组数据时如果某个全局数组或者计数器没有在每组数据开始前重置上一组的数据就会污染下一组。这个bug非常阴险因为样例刚好只有一组数据。第三检查出口和返回值。递归函数是否所有分支都有返回值循环是否可能死循环while的条件在结束时是否更新了循环变量第四检查输出是否有多余字符。调试代码没删干净、空格和换行不对、多打印了提示语这些都会导致明明逻辑正确却被判错。很有把握的解法提交失败时八成是格式问题。5. 常见问题与避坑技巧实录5.1 超时问题的排查思路机试最怕的不是错而是超时。明明算法思路没问题但评测结果是Time Limit Exceeded这种挫败感很影响心态。遇到超时我一般先干一件事算复杂度。数据量n 10^5如果代码是两层for循环嵌套复杂度就是O(n^2)也就是十亿次运算几乎必定超时。这时候应该想的是如何降到O(n log n)或者O(n)能不能用哈希表替代数组查找能不能用前缀和优化区间求和能不能用二分把查找从线性变成对数如果复杂度没问题那就是常数项的问题。cin/cout是否关闭了同步endl是否用多递归是否太深这些细小的性能点平时注意不到但在只有一两秒时限的题目里就会放大。还有一个很实用的技巧在做题的时候每写完一题就顺手记录它的时间复杂度和空间复杂度以及判断数据范围要求什么样的复杂度。培养这种计算意识之后基本看一眼数据规模就能知道自己的解法会不会超时。5.2 卡题超过30分钟该怎么办机试的时间非常宝贵一道题卡半小时不出来的情况相信每个刷题的人都经历过。我的原则是卡住超过30分钟就立刻换题实验室测试题可以跳机试只能有限时死磕一道题是最愚蠢的浪费。换题不是放弃而是留到后面。先把能拿的分拿到手稳定一下心态再回头重新读题。很多时候你做完后面的题再回来看脑子清醒了反而一眼就能看出之前卡住的地方。时间管理上还要留一个缓冲考前十分钟不要再折腾新题。检查一下每道题的输出格式、有没有遗漏的题目要求、编译环境是否正常版本。很多机试是要求把代码提交到指定目录目录名、文件名、大小写都不能错这些细节在紧张状态下最容易出问题。5.3 每天Day9该留什么复盘记录机试复习的复盘不只是“今天学了多少”这种心理安慰而是要有实际的记录结构。我在Day9晚上整理了一份固定格式的笔记后来的每一天都沿用它。题目类型今日完成情况出错原因整改方案二叉树递归遍历3题其中1题超时递归出口写错统一使用nullptr判断并查集模板应用2题1题漏初始化和合并忘记判断根节点是否相同每次merge前先find层序遍历变体1题队列顺序搞反复习BFS模板笔记中要记录的不只是题号更重要的是“错误原因”和“整改方案”。这两个字段才是复盘的精华。今天我犯过一个错误把它记下来明天就不会再犯一周后再翻一遍错误就会变成肌肉记忆。除此之外我还把每个专题的模板代码单独建了一个文件夹。比如tree_template.cpp、union_find_template.cpp每个文件开头注释清楚它的适用场景和易错点。这样一来后续复习不需要翻厚厚的题解只需要打开模板文件扫一眼整个专题的脉络就全回来了。Day9过去之后你会发现后面的Day10、Day11在学习节奏上会顺畅很多。因为模板库有了调试方法有了复盘体系也有了。剩下的事情就简单了遇到新题调模板套思路跑测试。我在实际备考中的体会是Day9当天最重要的是建立“模板化”的意识。算法题数量无穷无尽但万变不离其宗。所有机试题最终都能归到若干个数据结构的基础操作上。二叉树递归和并查集只是开始后面还有最短路径、拓扑排序、KMP每一个专题都值得你花一个“Day9式”的时间去彻底吃透。等到复试那天你坐在机房里看到题目脑子里浮现的不再是空白而是“这题可以用哪个模板解决”的时候这一阶段的努力就算真正到位了。