下面这份题单按知识点和难度递进整理。建议先独立判断题型，再决定使用胜负 DP、SG、Minimax 或数学策略。

难度是相对博弈论学习阶段而言，不完全等同于平台评分。

一、入门：胜负状态 DP

目标：熟悉最基本的递推：

存在一个必败后继 → 当前必胜
所有后继都必胜   → 当前必败

顺序	题目	训练内容
1	AtCoder DP Contest K - Stones	一维胜负 DP，博弈入门首选
2	CSES - Stick Game	多询问打表，输出每个状态胜负
3	Kattis - Bachet's Game	给定取数集合，胜负 DP
4	Codeforces 1194D - 1-2-K Game	从打表结果中寻找模数规律
5	Codeforces 1537D - Deleting Divisors	数论状态与必败状态分析

完成这一组后，应能熟练写出：

win[0] = false;

for (int state = 1; state <= n; state++) {
    win[state] = false;

    for (int next : getNextStates(state)) {
        if (!win[next]) {
            win[state] = true;
            break;
        }
    }
}

---

二、Nim 与基础 SG 函数

目标：掌握：

• mex；
• 单个游戏的 SG 打表；
• 多个独立子游戏的异或；
• 找具体必胜操作。

顺序	题目	训练内容
6	洛谷 P2197 - Nim 游戏	Nim 异或和模板
7	CSES - Nim Game I	普通 Nim 判断胜负
8	洛谷 P1247 - 取火柴游戏	不仅判断胜负，还要构造必胜操作
9	P4279 [SHOI2008] 小约翰的游戏	反常 Nim，最后行动者输
10	CSES - Nim Game II	限制每次取走数量的 Nim
11	CSES - Stair Game	阶梯 Nim，识别真正参与异或的层

这组题建议自己总结三个模板：

普通 Nim
反常 Nim
限制取法 SG

---

三、经典数学博弈

目标：看到特定操作模型时，能够快速识别经典结论。

顺序	题目	训练内容
12	洛谷 P2252 - 取石子游戏	威佐夫博弈、黄金分割、Beatty 序列
13	UVa 10368 - Euclid's Game	欧几里得博弈、辗转相除中的决策
14	Codeforces 1370C - Number Game	奇偶性、质数与必败状态
15	Codeforces 1451D - Circle Game	几何边界与对称策略
16	Codeforces 1738C - Even Number Addicts	奇偶性分类讨论
17	AtCoder AGC002 E - Candy Piles	排序、棋盘模型与奇偶策略

这部分不要只背结论。每道题都建议写出：

1. 哪些是必败状态；
2. 必胜状态如何走到必败状态；
3. 为什么必败状态不能走到另一个必败状态。

---

四、SG 进阶：拆分与多个子游戏

目标：理解以下结构：

同一次操作产生的独立子游戏 → SG 异或
不同操作的结果             → mex

顺序	题目	训练内容
18	CSES - Grundy's Game	将一堆拆成两个不同大小的堆
19	Codeforces 138D - World of Darkraft	一次操作把棋盘拆成独立子游戏
20	洛谷 P2148 - E&D	多组子游戏、局部 SG 推导
21	洛谷 P2575 - 高手过招	棋盘状态转化为多个 Nim 子游戏
22	AtCoder AGC017 D - Game on Tree	树上 SG，子树异或
23	Codeforces 768E - Game of Stones	复杂单堆游戏的 SG 规律
24	Codeforces 850C - Arpa and a game of Mojtaba	质因数分组、状态压缩、SG
25	Codeforces 2004E - Not a Nim Problem	数论与 SG 的综合难题

推荐顺序：

CSES Grundy's Game
→ CF 138D
→ AGC017D
→ 洛谷 P2148
→ CF 768E
→ CF 850C / 2004E

其中后两题属于高难综合题，可以留到最后。

---

五、取数得分与区间博弈 DP

目标：掌握“当前玩家相对对手的最大得分差”：

$$dp[state]=\max(\text{当前收益}-dp[next])$$

顺序	题目	训练内容
26	AtCoder DP Contest L - Deque	标准区间博弈 DP
27	CSES - Removal Game	两端取数、得分差
28	Codeforces 1728D - Letter Picking	字符串字典序、区间博弈
29	AtCoder ABC201 D - Game in Momotetsu	网格上的最大最小得分 DP
30	AtCoder AGC026 C - String Coloring	可作为字符串状态思维拓展，不是纯模板题

前两道做完后，应能熟练写出：

dp[l][r] = max(
    a[l] - dp[l + 1][r],
    a[r] - dp[l][r - 1]
);

CF 1728D 很适合训练“收益不是数字，而是字典序胜负”的情况。

---

六、状态压缩 Minimax

目标：元素较少时，使用 mask 表示已经选择或删除的元素。

顺序	题目	训练内容
31	AtCoder ABC354 E - Remove Pairs	状态压缩胜负 DP 入门
32	AtCoder ABC278 F - Shiritori	mask + 最后一个元素
33	AtCoder ABC349 E - Weighted Tic-Tac-Toe	完整 Minimax、终局评价
34	Codeforces 1033C - Permutation Game	按状态依赖顺序计算胜负
35	AtCoder ABC380 F - Exchange Game	多集合状态与记忆化 Minimax

这一组需要注意：

如果 mask 不能完整决定后续操作，
还必须加入位置、上一次选择、当前玩家等信息。

你之前发的“构造排列并比较最小循环移位”也属于 Minimax，但因为顺序本身影响答案，不能简单只记录 mask。

---

七、图上博弈：DAG、环与平局

目标：区分：

• DAG 上的普通胜负递推；
• 有环图上的 WIN/LOSE/DRAW；
• 状态需要包含当前玩家或其他附加信息。

顺序	题目	训练内容
36	Codeforces 1033C - Permutation Game	隐式 DAG 上的胜负状态
37	Codeforces 917B - MADMAX	位置 × 位置 × 边权下限 状态
38	AtCoder ABC209 E - Shiritori	反图、出度、胜负平局传播
39	Codeforces 786A - Berzerk	环形图上的 WIN/LOSE/LOOP
40	Codeforces 936B - Sleepy Game	有环博弈、平局判断、方案构造

这一类最重要的递推是：

可以到达 LOSE → WIN
所有后继都是 WIN → LOSE
剩余无法确定 → DRAW

建议重点做 ABC209E 和 CF 936B。

---

八、树上博弈

目标：学会把树拆成子树，并寻找异或、深度奇偶性或删边后的独立结构。

顺序	题目	训练内容
41	AtCoder AGC017 D - Game on Tree	树上 SG 模板
42	Codeforces 812E - Sagheer and Apple Tree	深度奇偶性与 Nim
43	Codeforces 1404B - Tree Tag	树的直径、距离与追逐策略
44	Codeforces 1450E1 - Bitwise Queries	不建议作为首轮，属于拓展项

这一类中，Tree Tag 不是 SG，而是追逐博弈。核心是分析：

• Alice 一步能走多远；
• Bob 一步能走多远；
• 两人初始距离；
• 树的直径是否给 Bob 足够逃跑空间。

---

九、配对、镜像与不变量

目标：训练“不写 DP，直接证明策略”的能力。

顺序	题目	训练内容
45	Codeforces 197A - Plate Game	极简几何博弈
46	Codeforces 1396B - Stoned Game	最大堆与总数奇偶性
47	Codeforces 1451D - Circle Game	对称应对和边界分析
48	Codeforces 1370C - Number Game	数论不变量与分类讨论
49	AtCoder AGC010 D - Decrementing	gcd、奇偶性、递归化简
50	洛谷 P4136 - 谁能赢呢？	棋盘结构和奇偶策略

这组题做题时先不要急着写搜索，优先检查：

总和奇偶性
最大值与其他值之和
黑白染色
中心对称
配对回应
gcd 是否保持或规律变化

---

十、概率博弈

目标：掌握玩家决策与随机事件混合时的状态转移。

顺序	题目	训练内容
51	Codeforces 148D - Bag of mice	轮流行动中的概率 DP
52	Codeforces 540D - Bad Luck Island	三类对象相互消灭的概率状态
53	AtCoder ABC314 E - Roulettes	最优决策与期望 DP

注意区分三种节点：

自己决策：取 max
对手决策：取 min
随机转移：求加权平均

---

推荐主线：先做这 20 道

如果不想一次铺得太大，建议先完成下面这条主线：

1. AtCoder DP K - Stones
2. CSES Stick Game
3. Codeforces 1194D - 1-2-K Game
4. 洛谷 P2197 - Nim 游戏
5. CSES Nim Game I
6. 洛谷 P1247 - 取火柴游戏
7. HackerRank Misère Nim
8. CSES Stair Game
9. 洛谷 P2252 - 取石子游戏
10. CSES Grundy's Game
11. Codeforces 138D - World of Darkraft
12. AtCoder DP L - Deque
13. Codeforces 1728D - Letter Picking
14. AtCoder ABC354 E - Remove Pairs
15. AtCoder ABC349 E - Weighted Tic-Tac-Toe
16. Codeforces 917B - MADMAX
17. AtCoder ABC209 E - Shiritori
18. Codeforces 936B - Sleepy Game
19. AtCoder AGC017 D - Game on Tree
20. Codeforces 1370C - Number Game

完成这 20 道，基本能覆盖 ICPC 常见博弈题的主要识别框架。

每道题建议记录的内容

不要只记录 AC 代码。建议为每题填写下面这张复盘表：

题目：
博弈类型：
状态定义：
终止状态：
当前状态如何转移：
双方操作是否相同：
是否能拆成独立子游戏：
是否存在环：
使用算法：
必败状态：
关键证明：
容易写错的地方：

特别是 SG 题，再多记录三项：

单个子游戏是什么：
sg[x] 的后继集合是什么：
多个子游戏为什么可以异或：

刷题顺序可以概括为：

胜负 DP
→ Nim
→ SG 打表
→ 拆分游戏
→ 得分 Minimax
→ 状态压缩
→ 图上 WIN/LOSE/DRAW
→ 树上博弈
→ 数学策略与不变量