接龙博弈题解：状态压缩与记忆化搜索的对抗性优化

1. 这道题为什么让一半人卡在考场里出不来

每年普及组第二轮的最后一道题，都是那种“读完题觉得能做，写完代码发现只能过样例”的存在。2024 年这道接龙题（chain）也是一样的路数：题面不长，规则用日常语言就能讲明白，但一旦坐到键盘前把状态定义写下来，复杂度就会立刻失控。我从考场复盘和赛后讨论里反复看到同一个现象——大部分选手能想到“枚举下一个接谁”，也能写出一份看起来正确的深度优先搜索，然后在第三个测试点开始大面积超时，最后连部分分都没兜住。这道题真正筛选的不是谁会写递归，而是谁能把“游戏规则”翻译成一个状态空间可控的模型，并且在时间预算内把这个模型压缩到能跑。它适合已经能熟练写基础搜索、正在冲一等奖的选手精读，也适合教练拿去当“如何从暴力推到正解”的教学素材；如果你还在纠结数组下标，这篇的代码部分可以先跳过，先看建模那两节。我把题目抽象成一句人话：有一堆元素摆在那里，两个人轮流挑一个接在队列末尾，每次挑的元素必须和队尾满足题目给的接续条件，谁先接不上谁输，问先手有没有必胜策略。接续条件在不同版本复述里有出入，官方题面为准，但我在下面用一个可替换的判定函数ok(x, y)来承载它——无论它是最大公约数、按位与、还是数值大小关系，替换这一个函数就行，剩下的优化手段是通用的。

2. 把“接龙”这层皮剥掉，看清它到底是什么模型

2.1 从游戏规则到状态机：哪三个量决定了局面

很多人一上来就写dfs(last)，只传一个“上一个接的是谁”。这样写在小样例上能跑出正确答案，但它隐含了一个致命假设：每个元素只能被用一次这个约束，被悄悄丢掉了吗？没有，只是被丢进了全局数组vis[]里。全局状态一旦参与递归，回溯就必须写对，而更麻烦的是，你没办法做记忆化——因为同样的last，在vis不同的情况下是完全不同的两个局面，缓存下来就是错的。

所以一个能推导正解的状态，必须同时抓住三样东西：已经用了哪些元素、当前队尾是谁、现在轮到谁行动。第三项在博弈类递归里其实可以省掉，用“当前行动者的胜负”这种相对定义就够，这也是 minimax 的常规写法：win(S)表示面对局面 S 的这个人是否必胜，转移就是“存在一步走到对方的必败局面”。第二项last是接续判定的输入，不能省。第一项是约束，不能省。于是状态自然写成(mask, last)，其中mask是一个二进制集合。

这里有个容易被忽略的细节：last有必要单独存吗？last一定属于mask，所以它被mask包含了，看起来冗余。但问题是你没法从mask反推出“最后一个是谁”，因为mask只是个集合，它不记录顺序。所以last必须显式存。这个“看起来冗余但必须存”的判断，是状态设计里最常见的分水岭，我见过太多人在这里为了省一维而写出错误答案。

再往下想一步：如果题目的接续条件具备某种“传递性”或者“只和数值大小有关”，能不能把mask降成“还剩几个”或“当前最大值”？这要具体看条件。凡是需要“记住历史用了谁”的，说明接续关系和元素身份强相关，状态压缩就跑不掉；凡是能证明“用掉哪些元素不影响后续可选集合的可行性”的，就说明存在贪心或排序后 DP 的空间。这一步判断做对了，后面的路会顺很多。

2.2 为什么贪心必错：一个两分钟就能构造的反例

考场上总有人想：每次挑一个“能接的元素里最不挑食的”，也就是它对后面元素的兼容性最强，是不是就稳了？这个思路在区间调度类问题里确实成立，但放在对抗性游戏里立刻崩塌，因为你的对手不会配合你。

举个具体的小例子：假设有四个元素 A、B、C、D，接续关系是 A 后面能接 B 和 C，B 后面什么都不能接，C 后面能接 D，D 后面什么都不能接，而 B 和 C 之间互不相接。先手如果贪心地挑“兼容性最好”的那个（假设是 B），那么对手下一步就无路可走——听起来是先手赢了对吧？等等，这里要小心“谁先接不上谁输”的判定：先手接了 B，对手接不上，对手输，先手赢。这局贪心碰巧对了。

换个构造：A 后面只能接 B，B 后面能接 C，C 后面能接 D，但先手还有另一个起手选择 E，E 后面能接 F，F 后面就断了。如果先手选 A，双方一路接到 D，一共走了四步，第四步是对手走的，轮到先手接不上，先手输。如果先手选 E，走到 F 后是对手接不上，先手赢。两个起手选择，一个赢一个输，而“兼容性最好”这个指标根本没法区分它们——这就是对抗性游戏和单人多步决策的本质差别：你要优化的是“对手的最优应对下我的结果”，不是“我自己能走多远”。

我建议每个准备冲这道题的人都亲手把这个反例画出来，画成树，标上“轮到谁”。画完你就再也不会想着用贪心蒙了。这个动作花五分钟，能省掉考场上四十分钟的无效调试。

2.3 先看数据范围再动手：范围就是出题人给你的路标

这是我最想强调的一条经验：不要读完题就开始写，先翻到数据范围表，把它当成出题人写给你的解题说明书。普及组最后一题的范围通常会给好几档，比如 n ≤ 10、n ≤ 20、n ≤ 200、n ≤ 2000 之类，每一档对应一个复杂度的预期解法。

• n ≤ 10 到 20，明摆着告诉你“状态压缩可以过”，2^20 大约是 104 万，乘以 n 是两千万级别，刚好在时限内。
• n ≤ 200 左右，多半是 O(n^3) 的区间 DP 或者 O(n^2) 的图上 DP。
• n 到 2000 甚至 10^5，那基本可以确定正解是数学结论或者排序后的一次线性扫描，暴力只能拿前面几档分。

判断出这一点，你的策略就清晰了：先把低档分的暴力写对、写稳、写快，再去想高档的正解。我在机房见过太多人，暴力分没拿稳就一头扎进正解推导，最后正解没推出来，暴力也因为一个越界 RE 掉了三档，总分比老老实实写暴力的人还低。这不是技术问题，是节奏问题。

3. 状态压缩这条路怎么走：从能跑对到跑得动

3.1 一份“绝对正确但一定超时”的参考实现

先写一版绝对正确的暴力，作为后面所有优化的对照组。这一步不能跳，因为你的记忆化版本如果和暴力对不上，你根本不知道是优化写错了还是暴力写错了——有两个版本才有对拍的资格。

#include <bits/stdc++.h> using namespace std; const int MAXN = 22; int n; int a[MAXN]; bool used[MAXN]; // ok(x, y)：y 能否接在 x 后面。按官方题面替换此函数即可。 inline bool ok(int x, int y) { return __gcd(a[x], a[y]) > 1; // 示例条件，仅作占位 } // 返回：当前行动者（面对 last 已固定、used 已确定）是否必胜 bool dfs(int last, int cnt) { if (cnt == n) return false; // 没有元素可接了，当前行动者输 for (int i = 1; i <= n; ++i) { if (used[i]) continue; if (last != 0 && !ok(last, i)) continue; used[i] = true; bool opp = dfs(i, cnt + 1); used[i] = false; if (!opp) return true; // 走到一个对手必败的局面，我必胜 } return false; // 所有走法都让对手必胜，我必败 } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); puts(dfs(0, 0) ? "Yes" : "No"); return 0; }

其中last = 0是个哨兵，表示“还没开始接”，第一步不校验接续条件。这个哨兵技巧很常用，比在循环外面单独写一遍首步处理要干净得多，也不会漏掉 n = 0 这种边界（虽然这道题 n 不会为 0，但习惯要养）。

这份代码的正确性可以直接用数学归纳法证明，不需要怀疑。它的复杂度是 O(n!)，n = 12 的时候就已经跑到几亿次调用了，所以它只能用来对拍。

3.2 记忆化的三个坑，踩一个就全盘皆输

把used[]换成mask之后，第一反应是在外面挂一个memo[mask][last]。这里藏着三个坑，我按踩到的概率从高到低排。

坑一：把“轮次”也塞进状态里。有人会想，mask的位数就决定了轮到谁，所以不用存轮次——这个推论是对的。但也有人反过来，觉得要存一个turn表示轮到谁，结果memo多开一维，内存翻倍，而且缓存命中率下降。正确做法是相信“mask的 1 的个数奇偶性就是轮次”这个不变量，别多存。

坑二：备忘录的初值没考虑“必败”这个合法结果。用int数组初始化为 0，然后用 0 表示“未访问”，1 表示“必胜”，这时候“必败”就没地方放了。要么用 -1 初始化，要么用char数组配一个单独的vis数组。后者更快，缓存更友好，是我常用的写法。

坑三：状态空间够不够装。memo[1 << 20][20]是两千万个char，大约 20MB，能过。但如果你把last开到 22，mask开到1 << 22，那就是 9200 万字节，接近 90MB，很悬。这时候要么把维度调成memo[last][mask]让last在前（访问局部性更好，因为相邻的mask值在内存里连续），要么改用unordered_map做稀疏存储。经验上，能开数组就别用哈希表，哈希表的常数在小数据量下能吃你一倍时间。

char memo[MAXN][1 << 20]; // last 在前，mask 在后，缓存友好 // 0 = 未访问, 1 = 必胜, 2 = 必败

3.3 状态编码方案对比：三种写法的手感差异

第三行那种哈希表的写法，很多人觉得“反正状态不多，用 map 存一下”。实测下来，同样的状态数，哈希表的常数是数组的三到五倍，而且容易被卡。真要省内存，把char换成 2 bit 的位域更划算，但代码复杂度上去了，不推荐在考场上折腾。

还有个小细节：mask的位数最好从 0 开始编号，元素下标也用 0 到 n-1，这样1 << i就是现成的。如果元素从 1 开始编号，mask就浪费了一个最低位，1 << n也要跟着 +1，容易写错。这种一致性上的小毛病，在紧张的考场上就是 RE 的来源。

3.4 常数优化：把两千万次调用压到能过

状态压缩的复杂度写出来是 O(2^n · n^2)，但你实际跑到的时间往往比理论值难看，原因全在常数上。我按收益从大到小列几个改法。

第一，把接续判定表预先打好。ok(i, j)里如果是最大公约数那种计算，每次调用都是一次除法，两千万次调用就是两千万次__gcd，这在时限紧的时候非常致命。开一个bool conn[MAXN][MAXN]，读入后 O(n^2) 预处理一遍，递归里只做一次数组查询。这一步通常能省掉 30% 到 50% 的时间。

bool conn[MAXN][MAXN]; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) conn[i][j] = (i != j) && ok(i, j);

第二，把“还剩哪些元素”预计算成邻接表。每次递归遍历 1 到 n 找未使用的元素，其实浪费了大量时间在已使用的元素上。可以用位运算技巧快速枚举mask的补集里的位：

int rest = full ^ mask; while (rest) { int i = __builtin_ctz(rest) + 1; // 最低位的 1 的位置 rest &= rest - 1; // 清掉最低位的 1 if (!conn[last][i]) continue; ... }

__builtin_ctz是 GCC 内建函数，返回二进制末尾零的个数。用它枚举集合中的元素，比逐个判断used[i]快得多，因为循环次数从 n 降到实际可选数。

第三，把递归改成带显式栈的迭代。这一步收益不明显，而且容易写错，我一般不推荐在考场上做。但如果你真的被递归深度卡了（比如 n 接近 22、机位的栈空间还设得小），那就得改。改之前记得先确认一下不是别的地方的问题，别白白重构。

第四，注意记忆化的写入位置。有些人只在“所有分支都试完”之后才写memo，这在必胜分支上会导致重复计算——因为一旦找到必胜走法就提前返回了，memo根本没写。正确做法是在返回前统一写入，或者对提前返回的分支也写。这个细节不写清楚，性能能差一倍。

char dfs(int last, int mask) { if (mask == full) return 2; // 无路可走，必败 char &res = memo[last][mask]; if (res) return res; int rest = full ^ mask; while (rest) { int i = __builtin_ctz(rest) + 1; rest &= rest - 1; if (!conn[last][i]) continue; if (dfs(i, mask | (1 << (i - 1))) == 2) { return res = 1; // 对手必败 => 我必胜 } } return res = 2; }

这份代码里res是引用，return res = 1这种写法虽然不太好看，但它保证了“返回值”和“写入缓存”是同一个动作，不会漏写。我在比赛里会这么写，赛后整理代码再改得漂亮点。

4. 怎么知道自己的代码是对的：对拍是唯一答案

4.1 造数据的三种套路，一个都不能少

写完记忆化版本之后，最大的风险不是超时，而是“样例过了但答案是错的”。这种情况在博弈题里特别常见，因为样例往往只覆盖最直白的路径。我的做法是三类数据混着造。

第一类，纯随机小数据。n 取 1 到 10，元素值在 1 到 30 之间随机。这类数据能覆盖绝大多数逻辑分支，是发现“状态转移写反了”的主力。注意元素值范围不要开太大，否则接续条件会变得极稀疏，随机出来的图几乎全是孤立点，测不出东西。

第二类，稠密图和稀疏图两个极端。通过调整元素值域来控制接续关系的密度。值域小，接续关系就稠密，搜索树会爆；值域大，接续关系稀疏，很容易出现“走了两步就断”的短链。这两个极端能分别测出“记忆化没生效”和“边界处理错误”。

第三类，手工构造的对抗数据。专门造那种“贪心选法会输、正解选法会赢”的盘面，用来验证你的转移是不是真的在求对手的最优应对。这类数据造起来费脑子，但只要造出两三个，就能挡住一类系统性错误。

// data_gen.cpp：随机小数据 #include <bits/stdc++.h> using namespace std; int main() { srand(time(0)); int n = rand() % 10 + 1; printf("%d\n", n); for (int i = 1; i <= n; ++i) printf("%d ", rand() % 30 + 1); puts(""); return 0; }

4.2 对拍脚本：三十行换一个安心

对拍这件事，很多人在考场上懒得做，觉得“我样例都过了”。但样例的覆盖面可能不到 5%，剩下的 95% 全靠运气，这个赌注太大了。我平时用的脚本很短，跑起来几秒钟一轮。

#!/bin/bash for i in $(seq 1 500); do ./data_gen > in.txt ./brute < in.txt > out1.txt ./fast < in.txt > out2.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "WA on case $i" cat in.txt break fi done echo "done"

brute是那份 O(n!) 的暴力，fast是记忆化版本。跑 500 轮小数据，如果两边一次都没分歧，基本可以放心提交了。反过来，如果第一轮就分歧，那输入文件in.txt已经被打印出来了，直接拿它单步调试，比在脑子里空想快十倍。

4.3 又慢又错？常见问题速查表

表格里最后一行那个坑，我实打实踩过。conn[0][i]在 C++ 里不会报错，它读到的是数组第 0 行的值，而那一行你压根没赋值，全是零，于是所有首步都被判定为“不能接”，答案永远是“先手输”。这种错误样例都过得去（因为样例可能没测首步分支），一交上去就 WA 一片。开数组时把conn声明成bool并且全局初始化，是良好的防御习惯。

5. 部分分策略：这道题的分数不是拿满分才叫得分

5.1 考场时间分配：先保三档，再冲第四档

普及组的最后一道题，满分 100 分，但通常有四到五档数据。按我的经验，n ≤ 10 那一档用纯暴力就能过，n ≤ 20 那一档记忆化能过，再往上的档位就需要真正的正解了。也就是说，你把暴力和记忆化都写扎实，大概能拿到 60 到 70 分，这已经是相当可观的分数。

问题在于，很多人不愿意接受“先拿 70 分”，非要一口气冲满分，结果在最后四十分钟里把已经跑对的代码改崩了，反而掉到 30 分。我的建议是：写下记忆化版本之后，先把这份代码单独存一份备份，文件名加个_backup或者直接复制到另一个文件里。之后再怎么折腾正解，崩了就回滚。这个动作两秒钟，但能救你一整场。

时间上我一般这么切：读题和建模二十分钟，写暴力五分钟，写记忆化二十分钟，对拍十五分钟，剩下的时间全部给正解推导和提交前检查。如果正解在最后二十分钟还没推出来，果断放弃，回去把已有的代码再对拍一遍、再检查一遍文件名和输入输出格式。

5.2 特判能救命：把无解和显然解提前拦掉

有几类情况可以直接 O(1) 或 O(n log n) 判掉，不需要进搜索。

第一类，全场没有可接的元素对。如果所有元素两两都不满足接续条件，那先手第一步就接不上，直接输出失败。这一条能挡掉一批构造数据。

第二类，元素里有重复值。有些接续条件对相等元素有特殊行为（比如“必须严格大于”就不允许重复），如果题目明确说了“可以相同”，那重复元素的存在可能让某些剪枝失效，需要单独考虑。这个要看具体题面，我不展开。

第三类，n 特别小（n = 1）。只有一个元素的时候，先手接了这一个，对手接不上，先手赢。这种边界如果靠搜索去处理，其实是能过的，但显式判掉更保险，也省得被脏状态影响。

这些特判写起来都是两三行，收益却很实在。我个人的原则是：凡是能在常数时间内判掉的显然情况，就不要交给搜索去撞。

5.3 从这道题能带走的东西：不止一个 100 分

这道题的价值不在它本身，而在于它把“状态压缩 + 博弈递归 + 记忆化”这个组合拳演示得非常完整。我把可迁移的经验列一下，都是我后来在别的题里真用上的。

• 状态设计的第一原则是“够用且最小”。存多了浪费内存和缓存，存少了信息缺失导致错误。判断标准是：给定这个状态，后续的所有决策是否唯一确定。这道题里(mask, last)刚好满足，多一个“轮次”就是浪费。
• 对抗性问题的转移永远是“存在一步让对手必败”。这个模式在取石子、棋盘博弈、轮流染色里全都通用。记住这个模板，遇到新的博弈题，先套模板再想特例。
• 记忆化之前先想清楚“状态是否可能重复出现”。如果递归路径上每个状态的mask都不同，那记忆化一点用没有，白开数组。这道题里不同的选取顺序会到达相同的mask，所以记忆化有效——这个判断必须在写代码前完成。
• 数据范围是出题人给的提示，不是摆设。看到 2^20 这种数字就该条件反射想到状态压缩，看到 2000 就该想到 O(n^2) 或者排序，这个反射弧建立起来之后，读题速度会快很多。

最后分享一个我自己的习惯：每次做完一道有博弈性质的题，我都会把最后的递归函数单独抄到一个本子上，只抄转移那五行，旁边写一句“这一步在问什么”。抄

到第五道题的时候你会发现，这些转移几乎是同一个模子刻出来的，区别只在“局面怎么表示”和“什么叫做一步合法的走法”。这两件事想清楚了，剩下的都是工程问题——而工程问题，是可以靠多写多练磨出来的，不靠灵感。