怎么用它
读到一个眼熟但说不清的词，先在这儿看一句话；要真学会它，点进那一章。 链接指的是真正教这个概念的那一章，不是第一次提到它的那一章 —— 比如「剪枝」第 3 章就出现过，但教它的是第 16 章。
一、这本书反复在教的方法
- 对拍 写一份慢但肯定对的程序当标准答案，再随机造大量数据，让它和你的正解逐字节比对。⚠ 它只能证明「在生成器造得出的数据上没问题」—— 生成器太温柔，错误代码照样全过。第 20 章 →
- 标准答案 对拍里那份「慢而肯定对」的程序，通常就是最朴素的暴力。⚠ 最好用**完全不同的思路**写：同一个思路写两遍，只能验出打字错误。第 20 章 →
- 生成器 造随机数据的小程序，从 argv[1] 读种子，保证每轮数据不同、且可复现。⚠ 造数据比算法本身更容易骗过你 —— 要往极端里造，让「错误的直觉」在你的数据上必定失败。第 37 章 →
- 剪枝 在搜索树上提前掐掉「不可能合法」或「不可能更优」的分支。⚠ 剪过头会漏掉正确答案，而且对拍不一定抓得到 —— 先想清楚剪的是哪一类分支。第 16 章 →
- 记忆化 把递归算过的结果存下来，同样的参数第二次直接返回 —— 从递归通向 DP 的那座桥。第 17 章 →
- 均摊 把「个别几次很贵」摊到整段操作上算平均代价：两层循环也可以是 O(n)。⚠ 理由不是「内层转得少」，而是「每个元素一辈子只会进出一次」。第 35 章 →
- 未定义行为 C++ 标准没规定会发生什么的写法（越界、比较器写错、有符号溢出…）。⚠ 它的表现随编译器 / 优化等级 / 机器变 —— 所以由它产生的数字不可复现，本书不把这类数写进断言。第 10 章 →
二、基础技巧
- 前缀和 s[i] = a[1..i] 的和。预处理一遍之后，任意区间和都是 O(1)。第 6 章 →
- 差分 前缀和的逆运算：给区间整体加一个数，只改两个位置。第 6 章 →
- 双指针 两个下标都只往前走、不回头，于是两层循环塌成 O(n)。第 7 章 →
- 滑动窗口 双指针的一种：右指针扩张、左指针收缩，维护一个满足条件的区间。第 7 章 →
- 二分查找 在有序序列上每次砍掉一半，O(log n) 找到位置。⚠ 边界写法必须一次钉死（lower / upper 差一个等号），靠试是试不出来的。第 8 章 →
- 二分答案 答案不好直接求，就猜一个答案再写个 check 验证它可行不可行 —— 前提是可行性单调。第 9 章 →
- 分治 拆成同形状的子问题分别解决，再把结果合并；归并排序、快速幂、线段树都是它。第 12 章 →
- 归并排序 分治排序：左右各自排好，再线性合并。合并这一步是它真正值钱的地方。第 10 章 →
- 逆序对 i < j 但 a[i] > a[j] 的数对个数 —— 归并排序合并时顺手就能数出来。第 11 章 →
- 快速选择 只往一边递归的快排：平均 O(n) 求第 k 小。第 12 章 →
三、搜索
- 递归 函数调用自己。三要素：这个函数负责什么、边界（出口）、递推关系。⚠ 要把自己当成**使用者**而不是执行者 —— 直接相信 f(更小的输入) 会算对。第 1 章 →
- 调用栈 每层递归的参数、局部变量、返回地址堆成的那一摞。栈的高度就是递归深度。第 1 章 →
- 爆栈 递归太深把栈用完了，程序直接崩（段错误），而且不会告诉你「是递归太深」。⚠ 「多深算深」= 栈有多大 ÷ 一层多少字节，两个数都随系统和编译器变，要自己量。第 30 章 →
- 决策树 把「每一步有哪些选择」画成一棵树，搜索就是在这棵树上走一遍。第 3 章 →
- 回溯 进入 → 递归 → **撤销**：走完一个分支要把状态恢复原样，否则下一个分支带着脏数据跑。第 4 章 →
- 深度优先搜索 一条道走到黑，走不动再退回来换一条。第 13 章 →
- 广度优先搜索 一圈一圈地扩散，第一次到达即最短（边权都为 1 时）。⚠ 标记必须在**入队时**做，不能等出队 —— 否则同一个点会被重复塞进队列。第 14 章 →
- 多源 一开始就把所有起点一起塞进队列，扩散出来的自然是「到最近的那个起点的距离」。第 15 章 →
- 状态 描述「当前局面」所需的全部信息；搜索和 DP 的难点通常不在写代码，而在想清楚状态是什么。第 15 章 →
- 迭代加深 限定深度反复 DFS：省下 BFS 的内存，又不至于像 DFS 那样一头扎到底。第 18 章 →
四、贪心与动态规划
- 贪心 每一步都做当下最优的选择。难点从来不是写代码，是**证明它为什么对**。第 19 章 →
- 交换论证 贪心正确性的常用证法：假设最优解和贪心不同，把它们交换一步，证明结果不会变差。第 19 章 →
- 动态规划 把「已经决定完前 i 个」的局面归成一类只算一次；先学记忆化搜索，再学递推。第 21 章 →
- 转移方程 写清「这个状态的答案能由哪些更小的状态得到」的那个式子。第 23 章 →
- 填表顺序 按依赖关系决定先算谁：区间 DP 按区间长度、树形 DP 按后序遍历。第 26 章 →
- 滚动数组 发现只用得到上一行，就只留两行（甚至一行），空间从 O(nW) 降到 O(W)。⚠ 压成一维之后循环方向就有讲究了：01 背包必须倒序，正序解出来的是完全背包。第 23 章 →
- 01 背包 每件物品最多拿一件，求容量内的最大价值 —— 全书 DP 的枢纽。第 24 章 →
- 完全背包 每件物品可以拿任意多件；一维写法里它和 01 背包的差别只有循环方向。第 24 章 →
- 多重背包 每件物品最多拿 k 件。第 24 章 →
- 二进制拆分 把 k 件拆成 1、2、4、…，于是多重背包变成 01 背包，复杂度里的 k 变成 log k。第 24 章 →
- 分组背包 物品分成若干组，每组最多挑一件 —— 循环顺序必须是「组 → 容量 → 组内物品」。第 25 章 →
- 区间 DP 状态是一个区间，按区间长度从小到大填表。第 26 章 →
- 树形 DP 状态挂在树的节点上，靠后序遍历保证「先算完孩子再算父亲」。第 27 章 →
- 状压 DP 把一个集合压成一个整数当状态用。⚠ 它没有消灭指数，只是把底从 n! 换成了 2ⁿ —— 所以适用范围写死在 n ≤ 20 左右。第 28 章 →
- 最长上升子序列 经典线性 DP；O(n²) 好懂，配上二分能到 O(n log n)。第 22 章 →
五、图论
- 邻接矩阵 用 n×n 的二维数组存边：查一条边 O(1)，但内存是 n²。第 29 章 →
- 邻接表 每个点挂一串出边；稀疏图上内存和遍历都是 O(n + m)。第 29 章 →
- 链式前向星 用数组模拟的邻接表：一个 head[] 加一串 next[]，没有任何动态分配。第 29 章 →
- 连通块 互相能走到的一片点。数连通块就是「对每个没访问过的点起一次搜索」。第 30 章 →
- 拓扑排序 给有向无环图排出一个「谁都排在自己依赖之后」的顺序；顺带就能判环。第 31 章 →
- 入度 指向一个点的边数。拓扑排序就是「入度减到 0 才入队」的 BFS。第 31 章 →
- 最短路 从起点到各点的最小边权和。第 32 章 →
- 松弛 看一条边 (u,v)：如果 dist[u] + w 比 dist[v] 小，就把 dist[v] 改小。所有最短路算法都在做这件事。第 33 章 →
- Dijkstra 每次取当前最近的点定死，再用它去松弛邻居；配堆是 O(m log n)。⚠ 它靠「最近的那个不会再变小」这句话成立 —— 有负权边时这句话就断了。第 32 章 →
- Floyd 三重循环求所有点对最短路；k 必须在最外层。第 33 章 →
- Bellman-Ford 把所有边松弛 n−1 轮；第 n 轮还能松弛就说明有负环。第 33 章 →
- SPFA Bellman-Ford 的队列优化：谁的 dist 变小了就把谁排队。⚠ 最坏复杂度仍是 O(nm) —— 它通常快，但不是「更快的 Dijkstra」。第 33 章 →
- 负环 边权和为负的环，绕一圈距离就更小，最短路因此不存在。⚠ 这道题问的通常是「**从起点走得到的**负环」—— 角落里走不到的那个不影响答案。第 33 章 →
- 最小生成树 选 n−1 条边把所有点连起来且总权最小。第 34 章 →
- Kruskal 边按权排序，能不成环就加进来（用并查集判成环）。第 34 章 →
- Prim 从一个点开始，每次把「连到集合外最便宜的那条边」加进来。第 34 章 →
- 切割性质 任意把点分成两半，横跨这两半的最小边一定在某棵最小生成树里 —— Kruskal 和 Prim 都是它的推论。第 34 章 →
六、数据结构
- 并查集 维护「谁和谁在一组」：合并两组、查询是否同组，都近乎 O(1)。第 36 章 →
- 路径压缩 查询时顺手把沿路的点全挂到根上，下次就一步到位。第 36 章 →
- 按秩合并 合并时让矮的树挂到高的树下面，避免树被拉成一条链。第 36 章 →
- 堆 一棵「父亲总不大于孩子」的完全二叉树，取最小值 O(1)，插入 / 删除 O(log n)。第 37 章 →
- 建堆 把一个数组整理成堆。自底向上做只要 O(n)，不是 O(n log n)。第 37 章 →
- 树状数组 支持「单点修改 + 前缀和查询」的数组，两个操作都是 O(log n)。第 38 章 →
- lowbit x & (-x)：取出 x 二进制里最低的那个 1。树状数组的每个位置「攒多长」就是它决定的。第 38 章 →
- 线段树 把区间递归对半分成一棵树，支持区间查询和区间修改。第 39 章 →
- 懒标记 区间修改先在节点上记一笔「欠着的修改」，真要看子节点时再下推。第 39 章 →
- 下推 把懒标记传给两个孩子。⚠ 「必须下推」只是一个常见理由，不是定律 —— 有些标记可以不下推（本书实测过）。第 39 章 →
- 单调栈 栈里元素保持单调：新元素进来时，把「已经没戏的」全弹掉。第 35 章 →
- 单调队列 两头都能弹的单调结构，用来 O(1) 取滑动窗口最值。第 35 章 →
- 哨兵 在数组两端塞一个「必定会触发结算」的假元素，省掉一堆边界判断。第 35 章 →
七、数学
- 欧几里得 gcd(a, b) = gcd(b, a mod b)，一行递归求最大公约数。第 40 章 →
- gcd 最大公约数。第 40 章 →
- lcm 最小公倍数，等于 a / gcd(a,b) * b。⚠ 先除再乘，反过来会溢出。第 40 章 →
- 质数 只有 1 和自己两个因数的正整数（1 不是质数）。第 41 章 →
- 试除 判一个数是不是质数，只要拿 2..√x 去除。第 41 章 →
- 埃氏筛 从每个质数出发，把它的倍数全划掉。内层从 i² 开始就够。第 41 章 →
- 线性筛 让每个合数**只被它的最小质因子划一次**，总次数正好等于合数个数。⚠ 次数少不等于跑得快 —— 本书实测它并没有赢埃氏筛，因为它是跳着写内存的。第 41 章 →
- 最小质因子 一个合数最小的那个质因数；线性筛顺手就能把它记下来，这才是线性筛真正的好处。第 41 章 →
- 快速幂 把指数看成二进制，O(log b) 求 a^b。第 42 章 →
- 取模 每一步都对 p 取余，防止溢出。⚠ 取模之下不能做除法 —— 要「除以 x」得乘 x 的逆元。第 43 章 →
- 逆元 模 p 意义下 x 的倒数：x · inv(x) ≡ 1 (mod p)。第 43 章 →
- 费马小定理 p 是质数且 x 不是 p 的倍数时，x^(p−1) ≡ 1，于是 inv(x) = x^(p−2)。第 43 章 →
- 组合数 C(n, k)：从 n 个里选 k 个的方案数。第 43 章 →
- 杨辉三角 C(n,k) = C(n−1,k−1) + C(n−1,k) 递推出来的那张表 —— 不用除法，也就不用逆元。第 43 章 →
- 溢出 结果超出类型能表示的范围。计数类答案一律 long long。⚠ **对拍查不出溢出** —— 两份程序会一起溢出成同一个错值。这只能靠脑子。第 40 章 →
没找到想查的词？那多半是这本书还没讲到它 ——收官页那张表列了目前缺的几块（高精度、字符串、位运算…）。