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

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 和 CB 后面什么都不能接C 后面能接 DD 后面什么都不能接而 B 和 C 之间互不相接。先手如果贪心地挑“兼容性最好”的那个假设是 B那么对手下一步就无路可走——听起来是先手赢了对吧等等这里要小心“谁先接不上谁输”的判定先手接了 B对手接不上对手输先手赢。这局贪心碰巧对了。换个构造A 后面只能接 BB 后面能接 CC 后面能接 D但先手还有另一个起手选择 EE 后面能接 FF 后面就断了。如果先手选 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开到 22mask开到1 22那就是 9200 万字节接近 90MB很悬。这时候要么把维度调成memo[last][mask]让last在前访问局部性更好因为相邻的mask值在内存里连续要么改用unordered_map做稀疏存储。经验上能开数组就别用哈希表哈希表的常数在小数据量下能吃你一倍时间。char memo[MAXN][1 20]; // last 在前mask 在后缓存友好 // 0 未访问, 1 必胜, 2 必败3.3 状态编码方案对比三种写法的手感差异方案存储形态单次查询开销适用规模我的评价char memo[last][mask]连续二维数组一次乘法寻址n ≤ 20首选稳、快、代码短int memo[mask][last]连续二维数组一次乘法寻址n ≤ 18能用但局部性略差unordered_mapint,int哈希表哈希可能的冲突链状态稀疏时只在前两种开不下时才考虑第三行那种哈希表的写法很多人觉得“反正状态不多用 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 donebrute是那份 O(n!) 的暴力fast是记忆化版本。跑 500 轮小数据如果两边一次都没分歧基本可以放心提交了。反过来如果第一轮就分歧那输入文件in.txt已经被打印出来了直接拿它单步调试比在脑子里空想快十倍。4.3 又慢又错常见问题速查表现象可能原因排查办法样例过大数据 WA状态转移写反把“对手必胜”当成“我必胜”检查if (!opp)的取反逻辑画一棵三层的博弈树手推对拍前几十轮全对第 N 轮分歧未初始化或数组越界读到了脏数据把所有全局数组清零开-fsanitizeaddress编译跑一遍全部 TLE包括小数据记忆化没生效memo写入位置不对或维度写错在函数入口加计数器统计实际调用次数和 2^n·n 对比大数据 RE递归深度超限或1 n溢出n ≥ 31 时1 n是未定义行为改用1LL n或提前特判部分点 WA且集中在 n 较小的点首元素哨兵处理漏了last 0时走到了conn[0][i]单独判断last 0走首步分支表格里最后一行那个坑我实打实踩过。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) 或者排序这个反射弧建立起来之后读题速度会快很多。最后分享一个我自己的习惯每次做完一道有博弈性质的题我都会把最后的递归函数单独抄到一个本子上只抄转移那五行旁边写一句“这一步在问什么”。抄到第五道题的时候你会发现这些转移几乎是同一个模子刻出来的区别只在“局面怎么表示”和“什么叫做一步合法的走法”。这两件事想清楚了剩下的都是工程问题——而工程问题是可以靠多写多练磨出来的不靠灵感。