★ 看到「第 X 章也用这道题」时该怎么做
跨章重复是有意安排的：同一道题，第 11 章用归并排序做、第 38 章用树状数组再做一遍； 第 20 章用贪心做错、第 23 章用 DP 做对。第二次遇到时不要翻上次的代码 —— 用新学的方法从头写一遍， 然后拿上一次那份当对拍的标准答案。这正是这个站每一章都在教的做法。
⚠ 先写暴力，再交题
这些题绝大多数是洛谷的题，交上去只会告诉你「对 / 不对」。 真正能查出问题的是对拍：先写一份慢但肯定对的暴力，再写正解， 用随机数据比对 —— 每一章的「★ 对拍」那一步给的就是现成的架子。
筛一下共 214 条
- 1洛谷 P1028 数的计算 NOIP2001。递归入门第一题，先想清楚「函数负责什么」
- 1洛谷 P5461 赦免战俘 递归分治，能把递归「画」出来，很直观
- 1洛谷 P1255 数楼梯 ★ 第 2、17、21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 斐波那契。会 TLE —— 别急着优化，记住这个感觉，第 17 章解决它
- 1洛谷 P1044 栈 ★ 第 21、43 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 进阶。想不出来就先跳过，学完第 17 章再回来
- 2洛谷 P1228 地毯填补问题 和汉诺塔同一个套路：切成四块，其中三块想办法变成同一个小问题。想通了代码很短
- 2洛谷 P1255 数楼梯 ★ 第 1、17、21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 斐波那契本尊。递归会 TLE —— 先用递推过掉，高精度部分慢慢写
- 2洛谷 P1464 Function 照着题意直接写递归会跑不完，正好体会「子问题重叠」。加个数组就过了
- 2洛谷 P1096 Hanoi 双塔问题 NOIP1998。汉诺塔的变形，先推出公式，再写高精度。想不出来可以先跳过
- 3洛谷 P1706 全排列问题 ★ 第 13 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 模板题，必须一次写对
- 3洛谷 P1157 组合的输出 从排列改成组合，只需改一个地方 —— 想清楚是哪个
- 3洛谷 P1036 选数 NOIP2002。子集和的变形，多了个质数判断
- 3洛谷 P2036 PERKET 标准的「每个都选或不选」，和本章例题几乎同构
- 4洛谷 P1219 八皇后 Checker Challenge USACO。本章原题加了输出前三个解，必须一次写对
- 4洛谷 P1025 数的划分 NOIP2001。搜索 + 剪枝，关键是想清楚「怎么避免数出重复的划分」
- 4洛谷 P1123 取数游戏 标准的「选或不选 + 冲突检查 + 撤销」，和本章几乎同构
- 4洛谷 P1731 生日蛋糕 ★ 第 16 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOI1999。剪枝的天花板，不剪必超时。现在做不出很正常，学完第 16 章再来
- 5洛谷 P1996 约瑟夫问题 本章原题（要输出出局顺序，所以老实模拟就行）。模板题，必须一次写对
- 5洛谷 P1618 三连击（升级版） 枚举 + 约束。想清楚「枚举哪一个数就够了」，别三个都枚举
- 5洛谷 P1042 乒乓球 NOIP2003。纯模拟，坑全在边界上 —— 最后一局没打完也要输出
- 5洛谷 P1563 玩具谜题 NOIP2016。模拟 + 方向绕，先在纸上把「朝内朝外」画清楚再动手
- 6洛谷 P8218 求区间和 一维前缀和模板题，五分钟应该写完
- 6洛谷 P1719 最大加权矩形 二维前缀和 + 枚举矩形。经典组合，值得写熟
- 6洛谷 P2367 语文成绩 ★ 第 38 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 差分模板题。不用差分会 TLE，正好验证这一章学没学会
- 6洛谷 P3406 海底高铁 差分的实战应用，要先想清楚「哪一段被走了几次」
- 7洛谷 P1147 连续自然数和 滑动窗口模板题。连续自然数天然是正数，前提刚好满足
- 7洛谷 P1102 A-B 数对 ★ 第 8 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 排序 + 双指针（或二分）。注意重复元素 —— 这一章第 12 步刚踩过的坑
- 7洛谷 P1638 逛画展 滑动窗口 + 计数数组，求「包含全部种类的最短区间」。经典变形
- 7洛谷 P1873 砍树 ★ 第 8、9 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 这题其实是二分答案（下一章）。先自己想想能不能用双指针 —— 想清楚「为什么不能」，比会做还有价值
- 8洛谷 P2249 查找 lower_bound 模板题。先手写一遍，再用 STL 写一遍，对比结果
- 8洛谷 P1102 A-B 数对 ★ 第 7 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 上一章用双指针做过，现在用「排序 + 两次二分」再做一遍 —— 这题正好是 U-L 的用武之地
- 8洛谷 P1873 砍树 ★ 第 7、9 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 二分答案。做不出来很正常，下一章就讲它 —— 但可以先自己试试
- 8洛谷 P1024 一元三次方程求解 ★ 第 9 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2001。实数二分，注意精度和循环终止条件（不能用 l < r）
- 9洛谷 P1182 数列分段 Section II 本章原题。必须一次写对
- 9洛谷 P1873 砍树 ★ 第 7、8 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 入门二分答案。check 是「按这个高度砍，能得到多少木材」
- 9洛谷 P2678 跳石头 NOIP2015。最小值最大化，check 是贪心地数「要移走几块石头」
- 9洛谷 P1024 一元三次方程求解 ★ 第 8 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2001。实数二分，终止条件要用精度（while (r - l > 1e-6)）而不是 l < r
- 10洛谷 P1177 排序 ★ 第 11、37 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 排序模板题。先用 sort 交一遍，再用自己手写的归并交一遍
- 10洛谷 P1068 分数线划定 NOIP2009。标准的多关键字排序，本章后半场的原题
- 10洛谷 P1104 生日 三关键字排序 + 稳定性要求。正好练「用输入顺序当兜底关键字」
- 10洛谷 P1271 选举学生会 数据范围很大但值域很小 —— 想想能不能不用比较排序（计数排序）
- 11洛谷 P1908 逆序对 ★ 第 38 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 本章原题，模板。注意开 long long
- 11洛谷 P1966 火柴排队 NOIP2013。要先想明白「答案等价于求某个排列的逆序对数」，转化是难点
- 11洛谷 P1177 排序 ★ 第 10、37 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 上一章那道模板题，这次专门用手写归并交一遍
- 11洛谷 P1115 最大子段和 ★ 第 12 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 先用 O(n) 的做法过掉，再试着用分治写一遍 —— 练「跨越中点的那部分怎么算」
- 12洛谷 P1115 最大子段和 ★ 第 11 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 本章原题。先用扫描版过掉，再用分治版交一次
- 12洛谷 P1923 求第 k 小的数 快速选择模板题。n 到 500 万，sort 也能过，但正好拿它练手写
- 12洛谷 P1226 快速幂 ★ 第 42 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 另一个经典分治：a^b = (a^(b/2))² —— 每次问题规模减半。第 42 章会细讲
- 12洛谷 P1010 幂次方 NOIP1998。递归分解 + 输出格式，练「把问题切成同形状的小问题」
- 13洛谷 P1596 Lake Counting S 本章模板题，只是改成八连通 —— 改方向数组即可
- 13洛谷 P1451 求细胞数量 和本章几乎一模一样，先拿它练手
- 13洛谷 P1162 填涂颜色 ★ 第 30 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 要从「外面」往里染色 —— 想想为什么不能从里面开始
- 13洛谷 P1706 全排列问题 ★ 第 3 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 回头复习第 3 章：确认自己看得出它和本章是同一个 DFS
- 14洛谷 P1443 马的遍历 ★ 第 15、30 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 BFS 模板题，只是方向从 4 个变成 8 个（马走日）
- 14洛谷 P1746 离开中山路 和本章例题几乎一样，起终点由输入给定
- 14洛谷 P1747 好奇怪的游戏 两个起点各跑一次 BFS
- 14洛谷 P1332 血色先锋队 ★ 第 15 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 多源 BFS —— 把所有起点一开始就全塞进队列，想想为什么这样是对的
- 15洛谷 P1332 血色先锋队 ★ 第 14 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 多源 BFS 模板题，本章前半场的原题
- 15洛谷 P1443 马的遍历 ★ 第 14、30 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 单源 BFS，但邻居有 8 个方向。先把「邻居是什么」想清楚
- 15洛谷 P1379 八数码难题 ★ 第 18 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 本章后半场原题。BFS 能过，学完第 18 章可以回来用双向 BFS 再写一遍
- 15洛谷 P1135 奇怪的电梯 NOIP2007。状态是「在第几层」，边是「上 K[i] 层或下 K[i] 层」—— 典型的状态图 BFS
- 16洛谷 P1074 靶形数独 NOIP2009。搜索顺序剪枝的教科书 —— 先填候选最少的格子，和本章「先安排重的猫」是同一个道理
- 16洛谷 P1120 小木棍 剪枝的经典硬骨头，要用到五六种剪枝。做不出来很正常，把题解里每个剪枝都想明白就是收获
- 16洛谷 P1731 生日蛋糕 ★ 第 4 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOI1999。最优性剪枝的教科书，需要预处理「最小体积/面积」当估价函数
- 16洛谷 P1518 两只塔姆沃斯牛 换换脑子：状态是「两头牛的位置和朝向」，用第 15 章的状态图思路
- 17洛谷 P1216 数字三角形 ★ 第 21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 IOI1994。本章原题，先交记忆化版，再交递推版
- 17洛谷 P1002 过河卒 ★ 第 21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2002。方案数计数，把 max 换成 +
- 17洛谷 P1434 滑雪 记忆化搜索的经典题。这题用递推很难写，用记忆化很自然 —— 体会一下
- 17洛谷 P1255 数楼梯 ★ 第 1、2、21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 第 1 章那道会 TLE 的题，现在回去用记忆化解决它
- 18洛谷 P1379 八数码难题 ★ 第 15 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 本章原题。用双向 BFS 或 IDA* 各交一遍，对比一下耗时
- 18洛谷 P2324 骑士精神 SCOI2005。IDA* 的经典题，估价函数是「有几个棋子不在位」
- 18洛谷 P1032 字串变换 NOIP2002。双向 BFS 的经典题，起点终点都明确 —— 正好符合前提
- 18洛谷 P1516 青蛙的约会 换换脑子：这题看着像搜索，其实是数学（扩展欧几里得）。练「先判断该不该搜」
- 19洛谷 P1223 排队接水 本章原题。注意它要输出的是排队顺序和平均等待时间（保留两位小数），比本章多一步输出格式
- 19洛谷 P1803 凌乱的yyy / 线段覆盖 本章第二道题的原题，端点重合的约定也和这里一致
- 19洛谷 P2240 部分背包问题 ★ 第 20 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 按「单位价值」排序 —— 排序关键字是算出来的，不是直接给的。想清楚交换论证为什么在这里成立（而在 01 背包里不成立，见第 23 章）
- 19洛谷 P1094 纪念品分组 NOIP2007。排序之后用第 7 章的对撞双指针，最贵的配最便宜的。交换论证要动点脑筋
- 19洛谷 P1090 合并果子 ★ 第 20、37 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2004。每次合并最小的两堆 —— 但一次排序不够用，因为合并出来的新堆还要重新参与排序。这题在等第 37 章的堆，先用 sort 硬做也能过
- 20洛谷 P1080 国王游戏 NOIP2012。交换论证的教科书题：按 a×b 排序。先自己推交换论证，再看题解。（要写高精度，可以先只做证明部分）
- 20洛谷 P1048 采药 ★ 第 23 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2005。就是本章的 01 背包 —— 故意先用性价比贪心交一发，看着它 WA，再学第 23 章的 DP。这一发 WA 值得挨
- 20洛谷 P2240 部分背包问题 ★ 第 19 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 同一个贪心，这里是对的。和上一题对照着做，本章第 9 步那段论证会刻进脑子里
- 20洛谷 P5019 铺设道路 NOIP2018。贪心是对的，但你得说得出为什么。先写暴力对拍，再想证明
- 20洛谷 P1090 合并果子 ★ 第 19、37 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2004。「每次合并最小的两堆」是对的，但「一次排序后顺着合并」是错的 —— 又一个「差一点点就错」的例子。第 37 章会用堆重做它
- 21洛谷 P1216 数字三角形 ★ 第 17 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 IOI1994。本章原题，先交记忆化版再交递推版，对比一下提交记录里的用时和内存
- 21洛谷 P1255 数楼梯 ★ 第 1、2、17 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 爬楼梯的原题，但 n 到 5000 —— 答案上千位，必须写高精度。递推部分你已经会了，这题练的是高精度加法
- 21洛谷 P1002 过河卒 ★ 第 17 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2002。二维递推，把 max 换成 +（计数）。注意马的控制点和边界，以及 long long
- 21洛谷 P1044 栈 ★ 第 1、43 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2003。卡特兰数。状态不好设 —— 先老实写搜索，再从搜索里找状态，正是本章第 13 步那套流程
- 21洛谷 P1077 摆花 ★ 第 24 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2012。状态要开二维（第几种花、已经摆了几盆），是通向第 23 章背包的过渡题
- 22洛谷 B3637 最长上升子序列 模板题，n ≤ 5000，O(n²) 就能过。先交 O(n²) 再交 O(n log n)，对比一下用时
- 22洛谷 P1020 导弹拦截 NOIP1999。必须用 O(n log n)。第二问要用 Dilworth 定理（最少的不升子序列个数 = 最长上升子序列长度），而且两问一个用 lower_bound 一个用 upper_bound —— 本章第 10 步那个坑的实战版
- 22洛谷 P1439 最长公共子序列 两个排列的 LCS 可以转成 LIS 来做（把第二个序列按第一个的位置重新编号）。转化很巧，值得专门想明白
- 22洛谷 P1091 合唱队形 NOIP2004。正着做一遍 LIS、倒着做一遍，然后枚举中间那个人 —— 「跑两遍 DP」的经典入门题
- 22洛谷 P2782 友好城市 排序之后就是 LIS。难点在看出「排完序之后这题就是 LIS」，这一步才是 DP 题的真正门槛
- 23洛谷 P1048 采药 ★ 第 20 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2005。最标准的 01 背包模板题，时间就是重量、价值就是价值。先交二维再交一维，对比一下内存
- 23洛谷 P1049 装箱问题 NOIP2001。只有体积没有价值 —— 把体积同时当价值就行。这一步转化是背包题的第一道门槛
- 23洛谷 P1164 小A点菜 求「恰好花完」的方案数。本章第 12 步那个套路的直接应用：初值 f[0] = 1，其余 0，转移从 max 换成加法
- 23洛谷 P1060 开心的金明 NOIP2006。价值 = 价格 × 重要度，读懂题就是模板。适合用来确认自己是真的会了
- 23洛谷 P2925 干草出售 USACO。「恰好装满」的味道，而且数据范围大到必须用一维 —— 二维会 MLE
- 23洛谷 P1877 音量调节 状态是「能不能达到某个音量」（布尔背包）。转移变成 f[j] |= f[j-w]，倒序的道理一模一样
- 24洛谷 P1616 疯狂的采药 完全背包裸题，就是第 23 章 P1048 的完全背包版。两题对着交一遍，方向的差别一辈子忘不了
- 24洛谷 P1853 投资的最大效益 完全背包 + 多年滚动。每年跑一次完全背包，本金滚到下一年 —— 「DP 套在循环里」的入门题
- 24洛谷 P1776 宝物筛选 ★ 第 35 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 多重背包模板题，n·k 大到不拆分必 TLE。二进制拆分的标准练习
- 24洛谷 P2347 砝码称重 NOIP1996。布尔多重背包（能不能称出某个重量），转移是 f[j] |= f[j-w]。数据小，拆不拆都能过 —— 正好拿来验证「拆完答案不变」
- 24洛谷 P1077 摆花 ★ 第 21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 NOIP2012。多重背包的方案数版本：max 换成加法、初值 f[0]=1（第 23 章第 12 步那个套路）
- 24洛谷 P5365 英雄联盟 进阶。要先看出「买 k 个皮肤的花费」是分组背包/多重的味道，而且答案要开 long long。适合确认自己是真的会了
- 25洛谷 P1855 榨取kkksc03 二维费用裸题（钱和时间两个上限）。注意两个上限都只有 200 —— 这就是本章第 7 步说的那个信号
- 25洛谷 P1507 NASA的食物计划 同样是二维费用（体积和质量），换了张皮。两题对着写一遍，「多一层循环」就再也忘不了
- 25洛谷 P1757 通天之分组背包 分组背包模板题。输入是「每件物品自带组号」，先归类再跑 —— 正好练一遍本章那个输入格式的转换
- 25洛谷 P1064 金明的预算方案 NOIP2006。主件 + 附件，看上去是新题型，其实是分组背包：把「主件单买 / 主件+附件1 / 主件+附件2 / 主件+两个附件」当成一组里的四件互斥物品。★ 这题是「看出它是分组背包」的经典训练
- 25洛谷 P1541 乌龟棋 NOIP2010。四种卡片各用了几张 → 四维费用，也就是四层循环。本章那句「多一维就多一层」的极致版本
- 25洛谷 P5322 排兵布阵 BJOI2019。进阶：先想清楚「对第 i 座城堡派 x 个兵能赢几个对手」，再把每座城堡的所有 x 当成一组。适合确认自己是真的会了
- 26洛谷 P1775 石子合并（弱化版） 本章原题，直线版。写完直接交，一遍就该过
- 26洛谷 P1880 [NOI1995] 石子合并 ★ 环形版，而且要同时求最小和最大。关键技巧是「破环成链」：把序列复制一遍接在后面，跑长度为 n 的所有区间。求最大值只需要把 min 换成 max —— 但那个错误贪心对最大值同样是错的
- 26洛谷 P1063 [NOIP2006 提高组] 能量项链 环形区间 DP 的另一张皮。合并的代价换了个公式，框架一个字不用改 —— 正好确认自己抓到的是框架而不是那道题
- 26洛谷 P1040 [NOIP2003 提高组] 加分二叉树 ★ 区间 DP + 输出方案，本章第 11 步那套 from[l][r] 回溯原样能用。而且它的「根」就是本章的「断点」
- 26洛谷 P4170 [CQOI2007] 涂色 区间 DP 经典。转移里多了一个「两端颜色相同」的特判，想清楚那个特判为什么成立
- 26洛谷 P1220 关路灯 进阶：状态在区间之外还要多记一维「人现在站在左端还是右端」。适合确认自己是真的会了「状态该怎么定」
- 27洛谷 P1352 没有上司的舞会 本章原题。注意它的输入多一行 0 0 结尾，而且根同样要自己找
- 27洛谷 P2016 战略游戏 ★ 最小点覆盖：选最少的点，让每条边至少有一个端点被选。和本章是一对「反着的」题 —— 转移里那个 max 变成 min，f[u][1] 那一项也要跟着变。写完对比一下两份代码，只差几个字
- 27洛谷 P1122 最大子树和 状态只有一维（这题不需要「选不选」），但正好练「有负数时该不该要这个儿子」。提示：max(0, f[v])
- 27洛谷 P2015 二叉苹果树 ★ 树形背包：状态是 f[u][j] = 在 u 的子树里保留 j 条边。它把本章的树形 DP 和第 23 章的背包缝在了一起，是最经典的进阶题
- 27洛谷 P1273 有线电视网 进阶的树形背包（分组背包版），正好回收第 25 章。想清楚「每个儿子是一组」这句话
- 27洛谷 P3478 [POI2008] STA-Station 换根 DP 入门：先求出以 1 为根的答案，再 O(1) 推到每个点当根。它是树形 DP 的下一站，值得提前看一眼
- 28洛谷 P1171 售货员的难题 本章原题（TSP 模板）。写完直接交，一遍就该过
- 28洛谷 P1433 吃奶酪 ★ 就是本章「忘了加回起点」解的那道题 —— 不用回来。另外它给的是坐标、距离是浮点数，正好练一下「浮点只能按容差比」（第 20 章那个坑）
- 28洛谷 P1896 [SCOI2005] 互不侵犯 ★ 另一大类状压：棋盘按行 DP，状态是「这一行的国王摆放方案」。先想清楚「同一行内合法」和「相邻两行合法」怎么用位运算判
- 28洛谷 P1879 [USACO06NOV] Corn Fields 棋盘状压的入门版，比 P1896 简单一档。适合先做这道再做上面那道
- 28洛谷 P2704 [NOI2001] 炮兵阵地 进阶：影响范围跨两行，所以状态要记「前两行」。经典中的经典
- 28洛谷 P3959 [NOIP2017 提高组] 宝藏 进阶：状压 + 分层。做得动这道，状压 DP 就算入门了
- 29洛谷 B3643 图的存储 本章的模板题：同时输出邻接矩阵和邻接表。写完对着本章三份代码检查一遍
- 29洛谷 P5318 【深基18.例3】查找文献 ★ 第 30 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 建图 + DFS/BFS，而且要求邻居按编号从小到大访问 —— 正好逼你想清楚「前向星的邻居是倒序出来的」这件事
- 29洛谷 P3916 图的遍历 ★ 第 30 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 反向建图的经典入门题。它会让你真正理解「有向图存一遍 vs 存两遍」的区别
- 29洛谷 P1113 杂务 ★ 第 31 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 建图 + 拓扑序 DP（第 31 章的预习）。这题的边是有向的，正好和本章的无向图对照着写
- 29洛谷 P2853 [USACO06DEC] Cow Picnic 多次 DFS，n 和 m 都不大 —— 适合拿三种存法各写一遍，实测比一比
- 29洛谷 P1330 封锁阳光大学 进阶：二分图判定。它的数据里有重边和自环的坑，正好呼应本章第 11 步
- 30洛谷 P5318 【深基18.例3】查找文献 ★ 第 29 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 本章的模板题：一张图上分别跑 DFS 和 BFS。要求邻居按编号从小到大 —— 正好逼你想清楚建图之后要不要排序
- 30洛谷 P3916 图的遍历 ★ 第 29 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 反向建图 + 从大到小跑 DFS。做完你会真正明白「有向图存一遍 vs 存两遍」
- 30洛谷 B3625 迷宫寻路 网格连通性 —— 故意留一道网格题，用本章的图版思路再做一遍，对照第 13 章
- 30洛谷 P1443 马的遍历 ★ 第 14、15 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ BFS 求最短步数，但「邻居」是马走日的 8 个方向 —— 这一章那句话的最好注脚：换的只是邻居
- 30洛谷 P1141 01迷宫 ★ 连通块 + 记住每块的大小。多次询问，一次染色全部答完 —— 「连通块编号」这个技巧非常常用
- 30洛谷 P1162 填涂颜色 ★ 第 13 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 进阶：从外圈往里灌水（补集思维）。它会逼你想清楚「哪些点该当起点」
- 31洛谷 B3644 【模板】拓扑排序 本章模板题。写完对着 fast.cpp 逐行检查一遍
- 31洛谷 P1113 杂务 ★ 第 29 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 拓扑序 + DP：每个任务的最早完成时间。第 21 章那句「依赖谁就先填谁」在这里字面成立
- 31洛谷 P1347 排序 ★ 边一条一条加进来，每加一条就判一次「已确定 / 有矛盾 / 还不确定」。逼你想清楚「拓扑序唯一」是什么意思
- 31洛谷 P4017 最大食物链计数 拓扑序上做计数 DP。答案要取模，正好复习第 42 章要讲的那些坑
- 31洛谷 P1983 [NOIP2013 普及组] 车站分级 进阶：难点全在建图上，边要靠「虚点」来省。建完图之后就是模板
- 31洛谷 P2712 摄像头 判环 + 拓扑删点。编号很大要离散化，是很好的综合练习
- 32洛谷 P3371 【模板】单源最短路径（弱化版） 本章模板题。朴素 O(n²) 就能过，先拿它把三句话写熟
- 32洛谷 P4779 【模板】单源最短路径（标准版） ★ 同一道题卡了朴素版，必须堆优化。正好把第 7 步那张表在评测机上再验一次
- 32洛谷 P1339 [USACO09OCT] Heat Wave G 无向图版：一条边存两遍。写完想一想为什么无向图不影响这一章的任何结论
- 32洛谷 P1629 邮递员送信 ★ 去程一遍 Dijkstra，回程把所有边反向再跑一遍。「反向建图」是很值钱的一招
- 32洛谷 P1462 通往奥格瑞玛的道路 进阶：二分答案 + Dijkstra 判可行。第 9 章那套二分答案在图上的第一次登场
- 32洛谷 P1073 [NOIP2009 提高组] 最优贸易 进阶：需要分层图 / 正反两遍最短路。想清楚「状态」是什么，这道题就塌了
- 33洛谷 B3647 【模板】Floyd 本章模板题。写完对着 brute.cpp 逐行检查三重循环的顺序
- 33洛谷 P3385 【模板】负环 ★ 判负环模板。注意它问的是「从 1 出发能不能走到负环」—— 正是本章第 1 步那件事
- 33洛谷 P1119 灾后重建 ★ Floyd 的神题：村庄按时间一个个修好，正好就是「k 一层一层加进去」。做完你会真的懂 k 为什么在最外层
- 33洛谷 P2865 [USACO06NOV] Roadblocks G 次短路。把「最短」拆成两个状态，松弛的写法要改一改
- 33洛谷 P1266 速度限制 进阶：状态里要带上「当前速度」——「状态是什么」这件事比算法本身难
- 33洛谷 P2850 [USACO06DEC] Wormholes G 虫洞 = 负权边，问有没有负环。多组数据，注意每组都要清干净
- 34洛谷 P3366 【模板】最小生成树 本章模板题。⚠ 它不连通时要求输出 orz，正好对应本章那句 IMPOSSIBLE
- 34洛谷 P1546 [USACO3.1] 最短网络 ★ 邻接矩阵给的稠密图 —— 正好是本章第 12 步那张表里「朴素 Prim 占优」的那一档
- 34洛谷 P1195 口袋的天空 ★ 只要连成 k 棵树 —— 那就少合并 k−1 次。做完你会发现 Kruskal 的循环本来就在数这个
- 34洛谷 P2820 局域网 要「删掉的边权和最大」—— 换个说法就是「留下的最小」。第 6 步那条恒等式的邻居
- 34洛谷 P1547 [USACO05MAR] Out of Hay S ★ 问的是最小生成树里「最长的那条边」。想一想：为什么它一定是所有生成树里最小的「最长边」
- 34洛谷 P2872 [USACO07DEC] Building Roads S 进阶：已有一些路（权值当 0）+ 坐标算距离。建图比算法难，正是本章说的「m 会很大」
- 35洛谷 P5788 【模板】单调栈 最裸的那一问：每个数右边第一个更大的在哪。本章第 5 步那段代码去掉算面积就是它
- 35洛谷 P1886 滑动窗口 / 单调队列 本章后半章的原题，两行输出一个字不差
- 35洛谷 SP1805 HISTOGRA - Largest Rectangle in a Histogram 本章前半章的原题。⚠ 记得开 long long
- 35洛谷 P2866 [USACO06NOV] Bad Hair Day S ★ 换个方向问「右边第一个更高的」—— 正好检验你有没有把方向背成死的
- 35洛谷 P1440 求m区间内的最小值 单调队列，但窗口是「前 m 个」—— 边界比模板题还容易写错，正好练第 10 步那个差一
- 35洛谷 P1776 宝物筛选 ★ 第 24 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 多重背包，n·W 到了 10⁷ 级别 —— 本章第 11 步那份 O(nW) 的用武之地
- 35洛谷 P4147 玉蟾宫 进阶：把柱状图那道题在「每一行」上做一遍，就是最大子矩形。这一步跨得比看起来小
- 36洛谷 P3367 【模板】并查集 本章那道题去掉最后一行输出。写完拿 count.cpp 的思路给自己数一遍跳步数
- 36洛谷 P1551 亲戚 最裸的连通性查询，5 分钟的题 —— 用它确认你默写的版本是对的
- 36洛谷 P1892 [BOI2003] 团伙 ★ 「敌人的敌人是朋友」：扩展域并查集，把点数翻倍。第一次见会觉得很妙
- 36洛谷 P2024 [NOI2001] 食物链 ★★ 带权 / 扩展域并查集的经典题，难度上一个台阶。想清楚「三倍点」或者「到根的距离模 3」
- 36洛谷 P1197 [JSOI2008] 星球大战 ★ 并查集只能合并、不能拆开 —— 所以要把时间倒过来跑。这条限制正是这一章那片森林的必然结果
- 36洛谷 P1955 [NOI2015] 程序自动分析 ★ 先离散化再并查集；先做完所有「相等」再验「不等」—— 顺序错了就全错
- 36洛谷 P3958 [NOIP2017 提高组] 奶酪 把「两球相交」当成一条边，就是连通性。练的是「看出这是并查集」这一步
- 37洛谷 P3378 【模板】堆 本章那道题去掉最后一行输出。先手写一遍，再用 priority_queue 写一遍，两份互相对拍
- 37洛谷 P1090 [NOIP2004 提高组] 合并果子 ★ 第 19、20 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 堆 + 贪心的入门题（哈夫曼）。回头看第 19、20 章：这个贪心为什么对，交换论证还在不在
- 37洛谷 P1177 【模板】排序 ★ 第 10、11 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 用堆排序过一遍：建堆 O(n) + n 次 pop。顺带体会「原地排序、不要额外空间」
- 37洛谷 P1801 黑匣子 ★★ 对顶堆：一个大根堆 + 一个小根堆，中间卡着第 k 小。想清楚两边什么时候要互相倒一个过去
- 37洛谷 P1168 中位数 ★★ 对顶堆最经典的用法，和上一题是同一招。做完这两道，堆才算真的会用
- 37洛谷 P2085 最小函数值 ★ 多路归并：n 个递增序列里取前 m 小。堆里永远只放 n 个候选 —— 和本章「大小为 k 的堆」同源
- 37洛谷 P1631 序列合并 ★ 上一题的双序列版。想清楚「为什么不用把 n² 个和全造出来」
- 38洛谷 P3374 【模板】树状数组 1 ★ 第 39 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 本章那道题的原题（单点加 + 区间和）。先合上页面默写 lowbit / add / sum 三段再交，别翻回第 7 步
- 38洛谷 P3368 【模板】树状数组 2 ★ 反过来：区间加 + 单点查。做法是在「差分数组」上建树状数组 —— 第 6 章那对逆运算在这儿又用上了一次
- 38洛谷 P2367 语文成绩 ★ 第 6 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 第 6 章用纯差分做过（那时数组不再变，最后统一还原一次）。这道题边改边问，才非上树状数组不可 —— 两份代码摆在一起，多出来的正是「可修改」这三个字
- 38洛谷 P1908 逆序对 ★ 第 11 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 第 11 章用归并做过，本章第 13 步用树状数组重做了一遍。交一份树状数组版，然后和你第 11 章那份对拍 —— 生成器都不用换
- 38洛谷 P1972 [SDOI2009] HH 的项链 ★★ 难度上一个台阶：询问离线、按右端点排序，每种颜色只在「最后一次出现的位置」记 1。想明白「为什么排完序就能一遍扫完」，树状数组才算真的会用
- 39洛谷 P3372 【模板】线段树 1 本章那道题的原题（区间加 + 区间和）。动手前先把 lz[o] 的含义一字不差说出来 —— 主语是「儿子们」
- 39洛谷 P1531 I Hate It ★ 单点改 + 区间最大值 —— 自测清单里「只需改哪两处」的实测场。改完回头看：pushup 换了，而 apply 里那个「乘区间长度」为什么就没了
- 39洛谷 P3374 【模板】树状数组 1 ★ 第 38 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 第 38 章交过的那道，这次用线段树再交一遍。本章第 13 步已经把两份代码摆在一起了，但亲手交两遍才有体感：行数、耗时、以及「哪一份改成区间最值只要动两处」
- 39洛谷 P1198 [JSOI2008] 最大数 ★ 强制在线（上一次询问的结果参与下一次输入），离线排序那条路被堵死了。顺带练「只往末尾插入」的建树写法
- 39洛谷 P3373 【模板】线段树 2 ★★ 加法和乘法两个懒标记，难点全在下推顺序：先乘后加，而且乘的时候加标记要跟着一起乘。做完这道，「lz 的主语是儿子」才算刻进去
- 40洛谷 P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题 设 P = x₀·a、Q = x₀·b，则 a·b = y₀/x₀ 且 gcd(a,b) = 1，枚举因子即可。⚠ 先判 y₀ % x₀ 是不是 0 —— 这是本章第 7 步那半章坑的同类
- 40洛谷 P1888 三角函数 五行题：最小两边之比约分，约的就是 gcd。用它确认你默写的循环版是对的（约分和第 7 步那个 lcm「先除后乘」是同一个手法）
- 40洛谷 P1372 又是毕业季I ★ 答案是 n/k，但要说得出为什么 —— 提示：取 d、2d、…、kd，需要 kd ≤ n。练的是「看出它是 gcd」这一步，不是 gcd 本身
- 40洛谷 P2651 添加括号III ★ 除法表达式加括号能否变成整数：a₂ 必在分母、a₁ 必在分子，其余都能挪到分子。约分之后判整除 —— gcd 在这里是化简工具，不是答案
- 40洛谷 P2152 [SDOI2009] SuperGCD ★★ 高精度 gcd。取模在高精度下太贵，得换成「更相减损 + 提取因子 2」的二进制 gcd。本章第 9 步那条「每两步至少减半」的界，在这里换了一种形式再出现一次
- 41洛谷 P3383 【模板】线性筛素数 本章那道题的原题。默写 6 行线性筛，那句 break 保证了什么，先说出来再交
- 41洛谷 P1075 [NOIP 2012 普及组] 质因数分解 n ≤ 2×10⁹ 且是两个质数之积 —— 筛不动，只能试除，而且试到 √n 就够。本章第 3 步那句「为什么只要试到 √x」在这儿是唯一的解法来源
- 41洛谷 P1217 [USACO1.5] 回文质数 ★ 上界 10⁸，直接筛会爆内存。正解要反过来：先造回文数再判质数（偶数位的回文数必被 11 整除，可以整段跳过）。练的是「筛不是万能的」
- 41洛谷 P1865 A % B Problem 筛 + 前缀和：cnt[i] 记 1..i 有几个质数，区间一减就出来。第 6 章那把尺子在这儿原样再用一次。⚠ 越界要输出 Crossing the line
- 41洛谷 P3912 素数个数 ★ n 到 10⁸。本章第 10 步那个实测（线性筛在大 n 上并没有赢）就是为这道题准备的 —— 交之前先想清楚你要用哪一种筛，以及为什么
- 42洛谷 P1226 【模板】快速幂||取余运算 ★ 第 12 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 第 12 章分治时见过它一次，那时它只是「分治的一个例子」；这一章它是主角。默写五行，⚠ 初值别写成 1 —— 第 5 步说过为什么是 1 % p
- 42洛谷 P1965 [NOIP 2013 提高组] 转圈游戏 每轮位移 m，k 轮之后落在 (x + m·10^k) mod n —— 一次快速幂。练的是「把题目翻译成一个幂」这一步
- 42洛谷 P1082 [NOIP 2012 提高组] 同余方程 ★ 求 ax ≡ 1 (mod b) 的最小正整数解，也就是逆元。b 不保证是质数，所以要用 exgcd（第 40 章第 13 步那份）。这道题正好卡在第 40 和第 43 章中间，先做它，第 43 章会顺很多
- 42洛谷 P3390 【模板】矩阵快速幂 ★ 把「乘」换成矩阵乘，五行骨架一个字不用改 —— 这才是快速幂真正的威力：它要的只是结合律。k ≤ 10¹²，正好用上本章第 4 步「次数只和 b 有关」那条
- 42洛谷 P1045 [NOIP 2003 普及组] 麦森数 ★★ 求 2^P−1 的位数和末 500 位。位数用对数算（不是快速幂），末 500 位用高精度快速幂 —— 同一道题里「取模」被换成了「只留末 500 位」，而那五行照样成立
- 43洛谷 P1313 [NOIP 2011 提高组] 计算系数 (ax+by)^k 里 x^n·y^m 的系数 = C(k,n)·a^n·b^m。模数 10007 是质数、k ≤ 1000 < 10007 —— 本章第 6 步那个「p > n」的前提在这里是满足的，可以放心用逆元那套，顺带把第 42 章的快速幂用上
- 43洛谷 P1044 [NOIP 2003 普及组] 栈 ★ 第 1、21 章也用这道题 —— 再遇到时换新方法重做，别抄上次的 ★ 卡特兰数 C(2n,n)/(n+1)。第 1 章用递归数过它、第 21 章用 DP 递推过它，这一章给出闭形式 —— 三种做法摆在一起，是整条路线最完整的一次回看。n ≤ 18 不用取模，正好看清楚原始的样子
- 43洛谷 P2822 [NOIP 2016 提高组] 组合数问题 ★ 问 C(i,j) 里有多少个被 k 整除。用第 3 步那份杨辉三角边推边对 k 取模、判 0，再套一层二维前缀和（第 6 章）。⚠ 这道题恰恰不能用逆元那套 —— k 不保证是质数，想清楚为什么
- 43洛谷 P3807 【模板】卢卡斯定理 ★★ 本章第 6 步说「这套公式要求 p > n，p ≤ n 时会全错」，而这道题的 p ≤ 10⁵、n+m 可以更大 —— 它就是那个失效的场。Lucas 把 n 和 m 按 p 进制拆开，每一位都退回到 p > n 的情形。先跑一遍本章的 smallP.cpp 看它是怎么错的，再来读 Lucas 会顺很多