阶段 0 那四章都在练同一件事：递归思维。从这一章开始，画风变了 —— 接下来五章是基础技巧，每一个单独看都不难，但它们会作为零件出现在后面几乎每一道题里。
这一章的两个主角：
- 枚举：不知道答案是几，那就把所有可能都试一遍。 重点不是「怎么试」，而是怎么少试 —— 把能算出来的量从循环里删掉。
- 模拟：题目怎么说，代码就怎么写。 重点不是「怎么写」，而是为什么它值得写 —— 它保底、它当标准答案、它还帮你找规律。
一句话概括这一章：先能老实做对，再想办法做快。
前半场 · 枚举：百钱买百鸡
1 一句话问题
公鸡 5 钱一只，母鸡 3 钱一只，小鸡 3 只 1 钱。
用 n 钱买 n 只鸡（三种都可以是 0 只），问有多少种买法。
n = 100 就是那道流传了一千五百年的「百钱买百鸡」（出自《张丘建算经》）。
输入 100
输出 公鸡 0 只，母鸡 25 只，小鸡 75 只
公鸡 4 只，母鸡 18 只，小鸡 78 只
公鸡 8 只，母鸡 11 只，小鸡 81 只
公鸡 12 只，母鸡 4 只，小鸡 84 只
共 4 种2 先用纸笔手算一遍
把题目翻译成两个式子，这是整道题唯一需要动脑的地方：
设公鸡 x 只、母鸡 y 只、小鸡 z 只
只数： x + y + z = n
钱数： 5x + 3y + z/3 = n小鸡是 3 只才 1 钱，所以 z 只能是 3 的倍数，否则钱数根本不是整数。
第一次写这道题的人有一多半会漏掉 z % 3 == 0，然后得到一堆多出来的答案。
题目里每一个数量词都要在代码里有对应物 —— 这就是「老老实实翻译」的含义。
用 n = 100 手动试一组：假设 x = 4，那 4 + y + z = 100、20 + 3y + z/3 = 100。
从第一个式子得 z = 96 - y，代进去：20 + 3y + (96-y)/3 = 100 → y = 18，z = 78。
验一下：4 + 18 + 78 = 100 ✓，20 + 54 + 26 = 100 ✓。
手算一组就够了。注意刚才这个手算过程 —— 你根本没有「试遍所有 z」， 你是算出来的。这件事第 6 步会变成关键的一步。
3 暴力：三重循环
不动脑子的写法是把三个未知数全试一遍：
点「运行 ▶」看结果
这份代码没有任何毛病，它就是题意的逐字翻译，n = 100 秒出。
考场上先把它写出来，分数就已经保住一半了。
4 实测：它有多慢
本机实测：
| n | 三重循环 O(n³) | 两重循环 O(n²) | 一重循环 O(n) |
|---|---|---|---|
| 1000 | 0.31 秒 | 0.003 秒 | 0.001 秒 |
| 2000 | 2.42 秒 | 0.005 秒 | 0.001 秒 |
| 3000 | 8.16 秒 | 0.005 秒 | 0.001 秒 |
后两列基本都是「测不出来」—— 那点时间几乎全花在启动程序上，真正的计算不到一毫秒。
5 慢在哪：数一数白试了多少次
n = 3000 时，三重循环要跑 3001³ ≈ 270 亿次。而答案只有几百种。
慢在哪？看最里面那重循环：
for (int z = 0; z <= n; z++) {
if (x + y + z != n) continue; // ← 这一行几乎每次都成立
...
}固定了 x 和 y 之后，z 只有一个值是可能的 —— 就是 n - x - y。
其余 n 个 z 全都会在第一行被 continue 掉。
也就是说，最里层循环 99.97% 的工作量，是在把已经确定的事情重新试一遍。
6 ★ 关键的一步
枚举的第一原则：能算出来的量，不要枚举。
x、y、z 之间有约束（x + y + z = n）。有约束就意味着自由度更少：
表面上三个未知数，实际上定了两个，第三个就没得选了。
for (int x = 0; x <= n; x++)
for (int y = 0; x + y <= n; y++) {
int z = n - x - y; // ← 不枚举，直接算
...
}O(n³) → O(n²)。一行代码，八千倍。
到这里已经够快了。但这道题还能再往前走一步，而这一步值得单独看， 因为它展示了纸笔推导在竞赛里的地位：
x + y + z = n ……①
5x + 3y + z/3 = n ……②
②×3： 15x + 9y + z = 3n
减去 ①： 14x + 8y = 2n
两边 ÷2： 7x + 4y = n ← 只剩两个变量了于是连母鸡都不用枚举：枚举 x，只要 n - 7x 能被 4 整除，y 就唯一确定。
x 最多到 n/7，复杂度 O(n/7)。
还有一个漂亮的副产品：
z = n - x - y = (7x + 4y) - x - y = 6x + 3y = 3(2x + y)z 自动是 3 的倍数 —— 那个折腾人的 z % 3 == 0 判断可以整个删掉，
因为它已经被方程本身保证了。
化简一次方程，同时干掉了一重循环和一个特判。 在信息学竞赛里，纸和笔不是辅助工具，它就是解题工具本身。
7 正解
点「运行 ▶」看结果
8 ★ 对拍验证
把「一重循环」那一栏换成你自己推导 + 默写的，再点开始。
特别值得一试：先自己独立推一遍 7x + 4y = n，推错了对拍会当场抓住。
值得故意写错的地方：
- 循环写成
for (int x = 0; x < n; x++)（<而不是<=）→ 漏掉x = n这种极端情况 - 忘了
z % 3 == 0（在暴力版里试）→ 会多出一堆假答案 - 化简时把
14x + 8y = 2n约成7x + 4y = 2n（只除了左边）→ 全错 if (rest % 4 != 0) continue;写成% 3→ 一对拍就现原形
后半场 · 模拟：约瑟夫问题
9 一句话问题，然后老老实实写
n 个人围成一圈（编号 1 到 n），从 1 号开始报数，
报到 m 的人出局，然后从下一个人重新从 1 开始报。问最后剩下的是谁。
输入 7 3
输出 4 出局顺序是 3 → 6 → 2 → 7 → 5 → 1，剩下 4 号这题没什么好想的，拿个 vector 当那个圈，谁出局就删掉谁：
点「运行 ▶」看结果
这份代码唯一的技术含量就是这一行：
pos = (pos + (m - 1)) % circle.size();**那个 -1 是最容易写错的地方。**因为 vector 从 0 数起，而报数从 1 数起：
当前这个人自己就要报「1」，所以只需要再往后走 m - 1 步。
不确定的时候，拿最小的数据代进去验：m = 1 时，报到 1 就出局，
也就是当前这个人自己出局，pos 应该原地不动 —— 代进去 (pos + 0) % size ✓。
m = 1 这种边界，是模拟题的照妖镜。写完先用它试一次，能省掉一小时的调试。
点「运行 ▶」看结果
10 单步看那个圈
播放的时候，不要盯着谁出局，盯着出局之后剩下的那个圈：
- 出局一个人，圈就少一格。剩下的仍然是「一圈人，从某个人开始报数」—— 这和一开始的问题是同一个形状，只是人数少了一个。
- 这个感觉是不是很熟悉？第 2 章：大问题 = 小问题 + 一步真活 + 小问题。 约瑟夫更干脆：大问题 = 一步真活 + 小问题。
- 把 n 改成 8、m 改成 2 看一遍，你会发现幸存者总是 2 的幂次相关的位置 —— 规律是存在的，只是不明显。
11 实测：模拟有多慢
本机实测（m = 7）：
| n | 模拟 O(n²) | 递推 O(n) |
|---|---|---|
| 100 000 | 0.15 秒 | 0.003 秒 |
| 300 000 | 1.34 秒 | 0.004 秒 |
| 600 000 | 6.49 秒 | 0.007 秒 |
| 1 000 000 | 21.5 秒 | 0.006 秒 |
慢在哪很清楚：vector::erase 要把后面所有元素整体往前挪一格。
删 n 次，每次挪 O(n) 个元素 —— O(n²) 就是这么来的。
可以，链表删除是 O(1)。但报数还是要一个一个走过去，走 m 步， 总共 O(nm) —— m 大的时候照样慢。
真正的出路不是换容器，是换思路：根本不去模拟那个圈。
12 ★ 关键的一步：先打表，再找规律
不知道怎么优化的时候，有一个很实用的动作：用暴力打一张表，从表里找规律。
点「运行 ▶」看结果
m = 3 时的表（右列是「答案减 1」）：
n: 1 2 3 4 5 6 7 8 9 10
答案-1: 0 1 1 0 3 0 3 6 0 3盯住它十秒钟。把前一项加 3，再对当前的 n 取模：
(0+3)%2 = 1 ✓ (1+3)%3 = 1 ✓ (1+3)%4 = 0 ✓ (0+3)%5 = 3 ✓
(3+3)%6 = 0 ✓ (0+3)%7 = 3 ✓ (3+3)%8 = 6 ✓ (6+3)%9 = 0 ✓每出局一个人，剩下的就是一个人数少一个的、一模一样的问题。
设 f(i) = 「i 个人玩这个游戏时，幸存者的 0 基编号」。
第一个出局的是 m 号（0 基编号 m-1）。剩下 i-1 个人，从 0 基编号 m 那个人
重新开始报数 —— 这就是一个 i-1 个人的约瑟夫问题，只是所有人的编号都平移了 m。
所以：
f(1) = 0
f(i) = (f(i-1) + m) % i答案是 f(n) + 1（把 0 基编号换回 1 基）。
O(n²) → O(n)，而且一个数组都不用开。
为什么要用 0 基编号推？因为取模天然是 0 基的。 用 1 基推也能推出来，但式子里会多出好几个 +1 -1，错一个就全错。 换个编号方式让公式变干净，这是很值钱的一个习惯。
是。而且是竞赛里非常主流的一种：打表 → 猜 → 证 → 对拍验。
- 猜错了不要紧，对拍会告诉你。
- 猜对了但不会证也不要紧，考场上分数照拿。
- 但只有真的想明白「为什么」（就是上面那段推导），换一道题你才用得上。
这个站点到处都在对拍，原因之一就是：有了对拍，你才敢大胆地猜。
13 递推写法 + ★ 对拍验证
点「运行 ▶」看结果
把「递推」那一栏换成你自己默写的，再点开始。
必踩的坑：
f = (f + m) % i写成% n（用了总人数而不是当前人数）→ 全错- 循环从
i = 1开始（f(1)已经是初值了）→ 多算一次 - 最后忘了
+1→ 编号全部差一，n = 1时输出 0 - 模拟版里
(pos + m) % size（少减 1）→ 每次都多走一个人
14 回头看：这一章真正教的东西
- 老实做对，永远是第一步。 模拟版是保底分、是标准答案、是打表工具。跳过它直奔正解，是自学最容易走死的一条路。
- 枚举之前先找约束。 能被算出来的量不要枚举；能被方程消掉的变量不要枚举。 一行代码换几个数量级，这种便宜在竞赛里到处都是。
- 不会优化就打表。 暴力 + 一张表 + 十秒钟的凝视，往往比冥思苦想管用。
15 自测
- 洛谷 P1996 约瑟夫问题 —— 本章原题（要输出出局顺序，所以老实模拟就行）。模板题，必须一次写对
- 洛谷 P1618 三连击（升级版） —— 枚举 + 约束。想清楚「枚举哪一个数就够了」，别三个都枚举
- 洛谷 P1042 乒乓球 —— NOIP2003。纯模拟，坑全在边界上 —— 最后一局没打完也要输出
- 洛谷 P1563 玩具谜题 —— NOIP2016。模拟 + 方向绕，先在纸上把「朝内朝外」画清楚再动手
第 6 章前缀和与差分，是这条路线上「性价比最高」的一章： 两个循环、五行代码，就能把「反复求区间和」从 O(n) 一次降到 O(1) 一次。
而且它和这一章一脉相承 —— 同样是「把重复干的活提前算好」。