我不是天赋型选手考研机试准备得也晚大四开学才真正翻开《算法笔记胡凡》。当时室友已经把PAT甲级题库刷了大半我连scanf和gets对空格的处理区别都说不清。如今回头复盘这本书几乎完整铺平了我从C语言半吊子到机试顺利过关的全程。写这篇笔记不是要复述目录而是想把我自己踩过的坑、反复读才读懂的地方、以及不同阶段该怎么用这本书的节奏理出来。内容包括语法补盲、在线评测系统的使用思路、基础算法和数据结构的掌握深度以及最后的冲刺安排照着走可以少走不少弯路。1. 为什么是《算法笔记》这本书的定位与高效使用方式1.1 它解决的并不是算法难题而是从零到机试的完整链路市面上讲算法的书不少但大部分有一个共同问题默认读者已经有较好的代码功底。《算法导论》推公式、讲证明适合当字典而不是入门教材《挑战程序设计竞赛》题目质量高但进阶曲线陡峭第一遍读很容易卡死。胡凡和曾磊这本《算法笔记》的定位在我看来最贴近国内机试和考研场景——它默认你是会写一点C但没系统练过算法题的状态然后从语言层面的坑开始一路铺到DFS、BFS、动态规划和最短路中间不留断层。配套的在线评测环境是PAT和Codeup这两个平台的题目风格和书中例题几乎可以一一对应。我的习惯是每看完一节的算法讲解就先把书里的例题自己敲一遍再找训练实战指南里对应标签的题目补两三道。只读书不敲代码的后果是看懂归看懂一上OJ就输出格式错误、段错误、超时轮着来。书读三遍代码敲三十遍这句话放在算法学习上一点都不夸张。1.2 我不是竞赛选手这本书的章节并不需要每章都精读这是我用这本书最大的心得。《算法笔记》的覆盖面很广从排序、二分到图论、DP、字符串哈希都有。作为目标是考研机试或保研机试的普通学生很多章节不需要做到竞赛级难度。比如Graph章节里的强连通分量、拓扑排序的变种可以适当后置而像二分边界、DFS剪枝、BFS层数、背包问题这种机试常客值得花大块时间彻底吃透。相比之下数学章节里的简单数论部分非常值得精读。GCD、素数表生成、分数四则运算这些内容又短又实用性价比很高。我自己的电子书阅读器里给第一章到第九章都加了书签后面几轮翻阅基本只看这些最核心的页码。这本书的正确打开方式是按需反复精读核心章节而不是从第一页线性刷到最后一页。2. C/C基础与OJ提交最先卡住我的不是算法是输入输出2.1scanf、gets、getline的血泪教训我刚上手时觉得自己的C语言功底还行——学校里教过指针结构体自己也写过课程设计。但OJ上第一道害死人不偿命的3n1猜想直接让我写了十几分钟才通过问题不在思路在循环输入的处理。书上重点强调的while(scanf(%d, n) ! EOF)我一开始根本记不住总是习惯性写while(n--)导致读到末尾时出乱子。另一个高频踩坑是读字符串。scanf(%s, str)遇到空格会断gets能读带空格的整行但已经在新版C标准里被移除了C里cin.getline和getline(cin, str)又是两套东西。书里第2章把这些细节列表整理得很清楚但看懂了和用顺了是两回事。我后来专门花了一天写了几个测试程序分别输入hello world这类带空格的字符串验证每种读法的行为差异才算真正过了这一关。OJ的判分机制不会因为你的代码本机运行正常就放你一马它只看你在评测环境下的输入输出是否正确。2.2 浮点比较、类型溢出和lld基础篇里的巨坑入门模拟这一章里的题目经常涉及浮点数判断比如给定两个分数判断大小关系。书里特意提到不能直接比较浮点数应使用fabs(a - b) eps这个坑在后面的几何题目里也会反复出现。类型溢出是另一个我印象极深的点。有一道求阶乘和的题目社群里很多人用int死活过不了换成long long立刻通过。书上在变量类型小节就强调过数据范围但人就是这样的——没栽过跟头不会长记性。从那之后我养成一个习惯看到题目中数据范围达到10^9级别第一反应就是开long long结果计算过程也尽量先乘除再加减避免中间结果炸掉。printf里输出long long用%lld而不是%d这个细节我在一次考场上差点栽了后来每次写输出都会特意确认格式符。3. 排序、二分与贪心基础算法章节如何做到真正掌握3.1 排序可以只用sort但必须懂边界和比较函数书里的插入排序、归并排序、快速排序原理都讲得很细致代码也很标准。对第一次学的人来说手写一遍这些经典排序是值的毕竟复试面试老师如果让你现场说快排思路你总得知道基准元素和分区是怎么回事。但对机试来说背过《algorithm》头文件里的sort函数用法才是正经事。sort(a, a n)默认升序自定义比较器时要注意怎么写cmp函数。比如按分数降序、分数相同按学号升序cmp必须严格返回是否应该排在前面的布尔值否则sort可能产生未定义行为。书里的例子很简单但真正复杂的是对vectorpairint,int、struct数组这类自定义类型的排序。我自己的经验是尽量多定义几个不同的cmp函数把所有字段先后的位置排列组合都试一遍把边界情况想清楚再提交。3.2 二分模板循环条件的第三个分支也是最隐蔽的雷区二分查找是我前几轮学习里最大的痛点。while(left right)还是while(left right)mid (left right) / 2还是(left right 1) / 2最后left是答案还是right是答案不同教材给法不一记混了就死循环或者答案偏一位。我的复盘结论是这样的书里给的二分模板并不是唯一的但不建议自己现场改编就把书上那套当成固定模板用熟。可以把找第一个满足条件的位置、找最后一个满足条件的位置这两类题各练上十道形成肌肉记忆。边界条件不是靠临场推理去想清楚的而是靠反复敲代码自然而然记住的。后面做浮点二分比如求平方根时直接让循环跑满100次省得想精度问题这也是书里没细说但很实用的技巧。3.3 贪心不是技巧是证明后放心用的直觉贪心算法章节看起来很简单就是找局部最优解但真正考试时最怕的就是你以为这是贪心结果不是。书里的经典例子是区间贪心区间不相交、区间选点思路不复杂按右端点排序然后依次选右端点最靠左的区间。但为什么按右端点排而不是按左端点书上讲了反证思路这部分建议认真看因为面试可能会问。我自己的体会是贪心题一定要先小规模手动推几个例子不要看着像就直接写。很多时候一个简单样例就能暴露出反例。书里给的贪心策略的证明思路章节交换论证、反证法值得花时间读虽然不能保证你成为贪心高手但能减少很多无谓的“直觉性错误”。4. 栈、队列、链表与树从码得出到抽象得清的分水岭4.1 数据结构用数组模拟比指针实现更实用《算法笔记》讲链表、树、图时大量使用静态实现——用数组下标代替指针。这是我读这本书收获最大的地方之一。刚开始我很不理解觉得用struct node *next才是正统的链表写法后来在OJ上做了一道树的遍历题发现指针写法在初始化、释放内存、访问空指针上各种出问题而书里用int left[maxn],int right[maxn]存左右孩子下标的方式简单到几乎没有出错机会。考场上时间紧张能少一个错误点就少一个错误点。静态实现不需要new、不需要delete、不需要担心root NULL的出口判断本质上就是用整型下标做逻辑地址。树的前序中序后序遍历、层序遍历、根据两种遍历重建二叉树这些经典操作全可以用静态实现边写边想清楚。4.2 树的遍历序列由遍历顺序反向重建二叉树树这章最需要反复练习的是给出二叉树的前序遍历序列和中序遍历序列重建二叉树的递归写法。我第一遍自己推导时总是卡在左子树区间长度上。书里给了模板每次递归都传入四个参数前序序列区间左右端点和中序序列区间左右端点。理解这个区间划分是理解整棵树的钥匙。实际做题时我进一步想明白了中序序列中根节点的位置是关键因为根节点左侧就是左子树的所有节点、右侧就是右子树的所有节点再通过左右子树的节点数量在前序序列里切分出左子树和右子树对应的区间。递归进入下一层就好比问题规模不断缩小出口条件是区间为空。这章不只是树的题必考它还为后面DFS的递归思想做了铺垫值得多花时间。4.3 栈、队列的一句话本质与表达式求值栈的后进先出和队列的先进先出概念非常直白但机试里不会只考概念而是把它们用在场景里。最典型的是括号匹配和表达式求值中缀转后缀、后缀求值。书里的思路是先写求后缀表达式函数再写计算后缀表达式函数两个函数之间通过栈衔接。学的时候不要求快跟着例题代码一步步debug建议把中间每个状态下的栈内容打印出来看一遍很快就理解了。STL中stack、queue、vector这些容器也不是一次性全用熟的。我的经验是每种容器至少做两道真实题目比如用queue做BFS、用stack做括号匹配自然就记住了。不要试图在没写代码的情况下靠背诵掌握STL背得再熟该忘还是忘。5. 搜索篇DFS、BFS与回溯练习时的思维卡点记录5.1 递归的信任黑箱不理解它就永远写不好DFS不少初学者包括我对DFS的第一反应是恐惧函数里面调用自己这怎么想得明白书里在第8章也花了大量篇幅在递归上。破解方法只有一个学会信任递归——假设递归函数已经完成了它的子任务你只需要处理本层逻辑和终结条件。以从n个数中选k个数求和为例DFS函数的核心思路其实只有两件事当前这个数是选还是不选。选就把它加入当前和再递归处理下一个数不选就直接递归下一个数。递归出口是已经处理到最后一个数且当前和满足条件。我当时的卡点是老想去想递归里面到底发生了什么想了半天也想不通。后来接受了黑箱思维把每一层递归只看作一个独立的函数调用思路立刻顺了。书上的回溯法比如八皇后问题本质就是DFS加上恢复现场的撤销步骤理解了递归回溯就自然而然了。5.2 BFS的状态表示与最短路计数的经典错法BFS广度优先搜索在《算法笔记》里最常见的应用是在二维地图上求从起点到终点的最短步数。核心数据结构是queue配合vis数组标记是否访问过。写BFS题时有一个高频错误忘记在入队时就标记vis而是在出队时才标记。这样会导致同一个节点被不同方向的节点重复入队当队列特别长时结果可能超时或MLE。我在这里耗费了很久对照书上的代码逐行看才意识到这个顺序问题。BFS的另一个关键点是如何定义状态。在迷宫里状态就是坐标(x, y)在有隐藏钥匙的场景里状态就要变成(x, y, key_status)。书上对状态的拓展思路让我彻底明白了为什么有些看似是BFS的题用二维数组标记会错或者永远走不到目标。状态定义一旦错了整个算法的复杂度模型就错了。5.3 剪枝从能过样例到能在时限内过搜索章节后半部分的剪枝技巧是应试拉开差距的关键点。书里举例的选数、N皇后、吃奶酪都能体现剪枝的价值。最基本的三类剪枝可行性剪枝当前情况已经不可能满足条件、最优性剪枝当前情况已经不可能优于当前最优解、重复性剪枝通过状态记录避免同一状态重复搜索。我一开始觉得剪枝是卡常的偏门技巧直到自己做了一道数独题——不剪枝根本跑不完剪枝后秒出答案才真正体会到搜索优化的力量。做题时的顺序建议是先写不剪枝的朴素DFS验证正确性再逐步加剪枝条件每加一个就提交一次看效果。这个流程很枯燥但能直观感受到剪枝对时间复杂度数量级的改变。6. 动态规划整本书最劝退也最值得二刷的章节6.1 斐波那契数列的三种写法从递归到递推再到记忆化DP章节劝退率极高很多人学到这章就直接放弃了。书里用了很友好的例子开始斐波那契数列。递归写法直观但效率极低因为大量重复计算递推写法从底向上只需要一个数组保存前两个值O(n)完成记忆化递归则是自顶向下查表本质和递推等价。这三个层次的对比是我理解DP的第一块基石DP就是用状态记录避免重复计算的递归优化。从这种角度再看后面经典的数塔问题、最大连续子序列和、最长回文子串就会比较自然地想到用一维或二维数组去记录中间状态而不是每次都从头算。状态转移方程不是凭空掉下来的它来源于对一个重复子问题的归纳。书里给的每个例题都可以手写一遍暴力递归→记忆化→递推的演变过程做完这些题的演变DP的思路就立住了。6.2 背包问题与最长子序列状态设计是灵魂背包问题几乎是机试必考01背包、完全背包、多重背包书里都讲了区别只在于循环顺序和滚动数组的写法。我个人的感受是01背包的二维写法一定要先写熟理解dp[i][v] max(dp[i-1][v], dp[i-1][v-w[i]] c[i])为什么能优化成一维时就会明白为什么要倒序枚举容量。完全背包为什么正序枚举同样可以从是否可以重复选择当前物品这个角度想明白。最长不下降子序列LIS和最长公共子序列LCS是我之前一直混淆的两个模型。LIS的状态是以当前元素结尾的最长不下降序列长度转移靠往前找LCS的状态是两个前缀的最长公共子序列长度转移分字符相等和不等两种情况。把两道题对照着写一遍就能更好地体会到状态设计依赖问题本身的次序结构这句话的含义。DP做不出来的题九成原因是状态定义不会而不是转移方程难推。6.3 我走过的DP弯路不要执着于看懂别人的状态转移方程我早期的一个严重错误是遇到一道DP题不会做立刻去翻题解看了状态转移方程后恍然大悟觉得自己会了但其实下次做仍然不会。问题出在状态来的过程被跳过了。后来我强迫自己无论花多长时间都要先自己设计状态哪怕设计错了也要写下来再跟题解对比找出是状态维度少了一层还是初始化条件不对。经过十几道这种先错后对的题我才慢慢摸到状态设计的直觉这个阶段是看再多题解也替代不了的。7. 图论与数学专题应试性价比最高的模块化学习7.1 图的存储邻接表与vector的完美结合图论开篇的存储方式很重要。《算法笔记》推荐优先使用邻接表存图C实现上用vectorint Adj[MAXN]或vectorNode Adj[MAXN]不仅写法简单而且不需要处理邻接矩阵浪费空间的问题。对于带边权的图定义一个结构体Node存放编号v和边权w即可。我自己写DFS、BFS图遍历时感受到这种存储方式对思维的简化遍历某个节点的所有邻居只需要for (int i 0; i Adj[u].size(); i)不用像邻接矩阵那样还要判断if (g[u][i] ! 0)。以后做Dijkstra、Prim这类需要找邻居更新的算法时邻接表同样顺手。7.2 Dijkstra、Floyd与最小生成树背模板之外的细节单源最短路径Dijkstra算法书里给出了朴素的O(V^2)写法和堆优化写法。刚开始建议先掌握朴素模板题量到一定程度再上堆优化。Dijkstra的一个易错点是每次从未访问集合中选dist最小的节点这个操作很多人在代码里写min_dist INF; for(...)if(!vis[j] dist[j] min_dist)容易漏掉!vis[j]条件导致已经确定最短路的节点再次被选中。Floyd算法就简单直接得多三层循环中间节点必须放在最外层。我之前一直不理解为什么k不能放内层后来看书上解释如果k放最内层dp[i][j]可能还没用到最新的dp[i][k]或dp[k][j]结果就错了。这个细节要记住考试时不用现场证明但写时不能写错顺序。最小生成树Kruskal算法用并查集实现代码量不大。书里的并查集章节含路径压缩和按秩合并是图论的基础不只在Kruskal里用在社交网络团体数量这类题里也频繁出现。学到这里我对这本书的感受更明显了章节之间彼此关联前几章的数据结构与后面的算法题目是连环扣。7.3 数学板块素数、GCD与有理数运算短平快的拿分点数论部分内容不多但每一块都可能在机试中直接投资回报。素数筛法建议直接用埃氏筛或欧拉筛生成一张素数表后所有判素数的题都变成查表操作复杂度O(1)。GCD用欧几里得算法辗转相除法递归两三行就能写完是很多题的公共组件。书里给出的有理数四则运算模板非常实用用一个结构体存分子分母化简函数里调用gcd加法函数注意通分时用最小公倍数。我做过一道很啰嗦的分数加法题如果不用这个模板现场推一小时都不一定能调好。背熟书里的模板再稍加修改五分钟以内就能搞定。所以对于那些底子薄弱、只能临时抱佛脚的人来说数学专题是优先级最高的部分没有之一。8. 我的三轮刷题节奏与机试冲刺复盘8.1 时间段划分九月打基础、十月刷专题、十一月模考我的实际备战周期大约三个月大致分成三个阶段第一轮约3周从第2章到第8章每天保证3~4小时边读书边上OJ敲例题。重点放在C语法、排序、二分、栈队列、树和DFS/BFS。每天结束前至少独立完成1道新题不看书不看题解。第二轮约4周主攻动态规划、图论和数学专题。DP每天保持2~3道新题图论从最短路径模板开始数学专项集中刷素数、公约数和有理数。把第一轮没做透的题重新做一遍标记易错思路。第三轮约3周全部变成模拟测试。每天真题一套严格计时模拟考场环境只带笔和草稿纸。做完后逐题复盘凡是超时的、WA的都要找到根因分类记到错题本里。时间表只是参照重点是由易到难、由表及里不能一上来就长时间刷DP那样挫败感太强。8.2 错题本的分类逻辑不是把题目抄进去而是把错误模式记下来传统的错题本是抄题目抄答案对我来说效果很差。我采用的是错误模式清单做法。比如输入循环少写了! EOF导致死循环——归为输入处理二分循环边界错位——归为二分模板DFS忘记恢复现场——归为回溯状态清理BFS入队时没标记vis——归为BFS visited处理大数相乘溢出——归为类型范围每道错题都会提炼为一句警示语考前只看这个清单。这比翻完整本书效率高得多。因为算法考试里的题目变化多端但错误模式是高度可归纳的。冲刺阶段我发现绝大多数失误都集中在十几条固定错误模式里能把它们逐个消灭正确率就能稳定下来。8.3 考场上的时间策略与放弃的智慧机试一般3到4小时做若干道题题目难度基本按顺序递增但也不是绝对的我遇到过第一题就挖了个大坑的情况。我的策略是先把所有题目都扫一遍评估每道题的大致难度和考察方向。按简单→中等→难题的顺序来做但每道题最多花40分钟。如果超过40分钟还没有清晰思路先标记好跳过把后面能拿的分拿完再回头啃。简单题务必一次AC不要因为前面太顺就大意读错题。我见过太多人把最小公倍数看成最小公约数然后白白送分。提交前检查一遍变量名、输出格式、类型对应特别是printf里格式符与变量类型是否匹配。放弃某道题不等于放弃整场考试把时间留给有把握的题目才是最优策略。机试考的是在有限时间内拿到尽可能多分数并不是每道题都必须解出来。这本书陪我走过了最难熬的三个多月现在翻回去看那些当时觉得怎么也绕不过去的坎其实大多集中在递归、DP边界和BFS状态设计几个点上。如果你正在用这本书我的建议很简单多敲、多错、多复盘代码量积累到一定程度量变真的会带来质变。
