第一次做一本通6.7练习3的取石子我上来就想直接算各堆数量的异或和结果连样例都过不了才意识到这个游戏不是普通Nim——因为你可以把一堆石子分成两堆堆的数量会边玩边变。当时我的第一反应是暴力把所有可能状态跑一遍自然就写成了记忆化搜索跑完却发现SG(x)的规律异常整齐直接按x模4分类就能O(n)出答案。这篇文章把记忆化搜索和分类讨论两条路线都撸一遍适合正在准备提高组博弈论专题的选手也适合那种拿到博弈题只会凭空猜结论的初学者——至少看完能知道结论是怎么来的验证过之后才敢放心用。1. 题目与核心思路拆解1.1 游戏规则还原这道题出自《信息学奥赛一本通》提高篇第6.7章的练习3题面大体是输入n再输入n个正整数a_i表示n堆石子。两名玩家轮流操作每轮必须从下面两种操作里选一种选一堆非空石子从中取走任意正整数个最少取1个最多把这一堆全部取走选一堆石子把这一堆拆成两堆非空的石子。原本一堆有x个拆成y个和x-y个其中1≤y≤x-1。当场上没有任何非空石子堆时轮到谁操作谁就输了。现在要判断初始局面下先手必胜还是先手必败。有个新手特别容易忽略的点拆堆不会减少石子总数但它会增加堆数改变整个局面的“结构”。所以哪怕石子总数一模一样也可能因为能否拆分而出现完全相反的胜负结果。这一点只有用SG函数才讲得清楚。1.2 普通Nim的直觉为什么失效如果规则只有“从一堆里取任意个”就是经典Nim胜负判断是全部a_i的异或结果非零则先手胜。但一旦加入“拆堆”操作每堆石子就不再是普通的独立Nim堆。一个大小为x的堆可能变成两个独立游戏的组合SG(a)与SG(b)这种变化没法用单纯的a_i异或覆盖。我当初就是栽在这里看到“取石子”直接当成Nim第二组样例明明异或不为0答案却是先手必败。后来才反应过来必须把每个堆看成公平组合游戏里的独立子游戏用SG函数刻画它的“胜负潜力”再把所有堆的SG异或起来得到整局的胜负。1.3 两条解法路线的关系这道题最后的答案是一个很简洁的分类讨论结论单堆SG只和x mod 4有关。但直接背结论容易翻车我建议按“记搜→打表→分讨”的顺序理解。记忆化搜索是暴力解法枚举所有取法和拆法严格按SG定义计算。优点是通用、正确性直观缺点是状态规模一大就跑不动分类讨论是优化解法在暴力算出的SG序列上发现模4规律把单堆SG变成O(1)公式整体判断O(n)两者是验证关系先用暴力打一张SG表再用公式重算一遍完全吻合之后分讨代码才敢放心去交。这其实就是竞赛里做博弈题的高效流程先把暴力写出来再让暴力替你找规律。2. 解法一记忆化搜索打印SG表2.1 SG函数的定义与两种转移对于大小为x的一堆石子定义SG(x)为这个单堆局面的SG值。根据SG函数定义SG(x) mex{ 所有后继状态对应的SG值 }mex表示“集合中最小的没有出现过的非负整数”。对这个游戏来说后继状态来自两类操作取走从x里取走k个k从1到x剩下x-k个石子构成新状态对应SG(x-k)拆分把x拆成i和x-ii从1到x-1得到两个独立堆对应SG(i) XOR SG(x-i)。把这两类后继的SG值全部收集起来取mex就是SG(x)。这里的关键是XOR的含义拆分出两个堆时两个子游戏同时存在总SG是各自SG的异或。这是Sprague-Grundy定理的结论学博弈论绕不开它。你只需要记住“两个独立博弈组合起来SG值异或即可”前面所有拆分转移都能靠这一条解释。2.2 先手算几个小值热身边界SG(0)0空堆没有可操作空间。x1只能取走1个后继只有SG(0)0所以SG(1)mex{0}1x2取1个到SG(1)1取2个到SG(0)0拆成(1,1)得到1 XOR 10后继集合{0,1}mex2所以SG(2)2x3取走分别到SG(0)0、SG(1)1、SG(2)2拆成(1,2)得到1 XOR 23。后继集合{0,1,2,3}mex4所以SG(3)4。注意SG(3)4不是3。这说明“取走”和“拆分”同时存在时SG值会偏离石子数量本身。第一次算到SG(3)时我就愣了一下但正是这种偏离提醒我这题不能用普通Nim的套路硬套。2.3 完整记忆化搜索代码下面这段C代码直接按SG定义记忆化搜索。为了不用靠肉眼去猜vis数组开多大我直接用set保存后继SG值。虽然常数略大但打表阶段完全够用而且不会有越界风险。#include bits/stdc.h using namespace std; const int MAXA 1003; int memo[MAXA]; int getSG(int x) { if (x 0) return 0; if (memo[x] ! -1) return memo[x]; setint s; // 操作1取走 k 个 for (int k 1; k x; k) { s.insert(getSG(x - k)); } // 操作2拆成两堆非空 for (int i 1; i * 2 x; i) { s.insert(getSG(i) ^ getSG(x - i)); } int res 0; while (s.count(res)) res; return memo[x] res; } int main() { int n; cin n; memset(memo, -1, sizeof(memo)); int ans 0; for (int i 0; i n; i) { int a; cin a; ans ^ getSG(a); } cout (ans ? Yes : No) endl; return 0; }这里有一个值得养成的习惯拆分枚举i到x/2就够因为(i, x-i)和(x-i, i)等价。重复枚举不改变mex结果但白白增加一倍时间。暴力阶段可能感觉不到遇到更复杂的拆分规则时就会很疼。2.4 复杂度边界与适用环境记忆化搜索的复杂度要理清楚虽然getSG会递归但每个x只算一次不会出现指数级递归。计算某个x时内部循环大约要枚举x次取走和x/2次拆分所有x加在一起是O(1.5 * maxA²)级别的枚举量。做个简单估算如果maxA是1000枚举量大概150万次几毫秒跑完如果maxA是10万枚举量大概1.5*10^10次再快也顶不住如果maxA是1e9连memo数组都开不出来记搜直接出局。所以记搜适合小范围打表也适合作为找规律引擎。真要交题通常还得靠第二种写法。3. 解法二分类讨论秒杀大范围数据3.1 从SG表里挖出模4规律把getSG(0)到getSG(16)打出来表格长这样x012345678910111213141516SG(x)012435687910121113141615一眼就能看出规律。除SG(0)0外对正整数xx mod 4 1或2时SG(x) xx mod 4 3时SG(x) x 1x mod 4 0时SG(x) x - 1。用大白话说自然数列从左往右排每次碰到“余3”的数它和后面那个“余0”的数就把SG值互换一下。比如3和4互换7和8互换11和12互换。这个规律不是我蒙的是暴力跑完前几千个数反复核对后确定的。后面写分类讨论时才敢直接上公式。3.2 规律为什么成立一个归纳验证思路完整数学归纳法写起来比较占篇幅但核心思路可以说清楚。假设对所有yxSG(y)都满足上面的模4规律。计算SG(x)时取走操作会遍历SG(0)到SG(x-1)。由于归纳假设这一串值在值域上会形成特定覆盖。比如x mod 4 0时0到x-2的SG值几乎覆盖0到x-2而x-1是余3的数它的SG值是x突破了x-1本身于是x-1这个值空了出来拆分操作贡献SG(i) XOR SG(x-i)。因为SG(i)不会大于i1SG(x-i)不会大于x-i1异或结果要恰好等于那个“空缺值”需要比较苛刻的条件用归纳法对四类余数逐一排除即可。所以mex确实会落在公式给出的值上。只是完整证明要分四类讨论写起来比较长对OI选手来说更实用的做法是先写暴力在1到10000范围逐项验证公式验证通过再提交。我强烈推荐在本地跑一段校验逻辑心里踏实bool check() { for (int x 0; x 10000; x) { int real getSG(x); int formula; if (x % 4 0) formula x - 1; else if (x % 4 3) formula x 1; else formula x; if (x 0) formula 0; if (real ! formula) return false; } return true; }这种“暴力验证公式提交”的组合拳在考场上比死磕严格证明更省时间也更符合实战节奏。3.3 分类讨论的代码与使用门槛公式在手代码短得不能再短#include bits/stdc.h using namespace std; long long getSG(long long x) { if (x 0) return 0; // 空堆的SG是0 if (x % 4 0) return x - 1; // 原SG比数量少1 if (x % 4 3) return x 1; // 原SG比数量多1 return x; // 其余情况SG等于数量 } int main() { int n; cin n; long long ans 0; for (int i 0; i n; i) { long long a; cin a; ans ^ getSG(a); } cout (ans ? Yes : No) endl; return 0; }整段复杂度O(n)数据范围拉到1e9也毫无压力。唯一要注意的是x0时必须特判不能走x%40分支返回-1。3.4 大范围输入的两个隐蔽坑第一个坑是数字类型。a_i如果到1e9级别用int读入理论上也没问题但公式里x-1和x1在极端数据下仍然在int范围内。不过为了杜绝一切溢出隐患我习惯一律开long long运行时间几乎不受影响。第二个坑是输出格式。一本通OJ在博弈题输出上不统一有的要“Yes/No”有的要“First/Second”有的要“先手必胜/先手必败”。我上面的代码按“Yes/No”写交题前务必看清原题要求。改错输出格式是特别冤的丢分点。第三个坑藏在规律本身如果题目把“拆成两堆”改成“拆成三堆”或者把“取任意正整数”改成“必须取1到k个”这套模4规律立刻失效。分类讨论只是这道题的结论不是所有取石子游戏的通行证。4. 常见问题与排查技巧实录4.1 布尔数组充当mex集合时的越界不少选手写记搜时喜欢用一个bool vis[1005]下标直接取SG值。前期SG值小看起来没事但随x增大拆分产生的异或值很容易超过1005。比如SG(3)和SG(7)的异或是4^812虽然不大但如果两个堆规模都在800左右异或结果可能到1000多再大就超出数组边界了。我的做法是打表阶段用set 保存后继值简单稳妥追求速度可以用动态vector 或用一个足够大的数组但必须提前估算上界。不知道SG最大值时set是安全性与可读性最平衡的选择。4.2 拆分枚举重复拖慢时间有人第一次写拆分会把循环写成for (int i 1; i x; i)枚举1到x-1。结果(i, x-i)和(x-i, i)被算了两次虽然mex结果不变时间却白白翻倍。数据范围一大这种浪费会非常明显。正确写法是让i枚举到x/2停止天然去重。这个习惯其实适用于所有需要枚举“两两组合”的博弈题包括拆三堆、合并堆等变种提前想清楚对称性能省大量常数。4.3 SG(0)这个边界老被忽略memo数组初始化为-1时如果getSG(0)不做特判递归到0会卡住或读到脏数据。所以每个博弈题解我都会强调0状态要先返回0。另外分类讨论公式里0也要单独处理否则x%40分支会算出-1这种非法结果。如果OJ数据包含0堆或空堆这个坑会直接导致WA。哪怕题面说明a_i是正整数保留这个特判也没有任何副作用。4.4 输出格式与多组数据的迷惑点一本通部分博弈题是单组输入但也有题是多组数据。多组数据时要在每组开始前重新初始化memo或者把求解逻辑放进独立的函数里避免上一组的记忆化残留污染下一组结果。如果最终答案用的是整场博弈的SG值ans要记住判断规则是“非零先手必胜零先手必败”这是博弈论里的通用结论不是这题的特例。ans初值为0每读入一堆就异或一次对应SG值最后判断即可。我个人真正吃透这道题靠的不是死背那个模4公式而是亲手把记搜代码跑了一遍盯着SG表看了半分钟突然发现3和4、7和8、11和12在互换。从那以后我遇到博弈题就多了一道固定流程暴力打表找规律再写优化版。这套流程在后面很多变种题里都救过我比如限制取子上限、允许合并堆、允许拆三堆虽然最终规律各不相同但“先暴力后规律”的节奏完全没变。如果你现在正在磕博弈论专题建议拿到题先别急着猜结论花两分钟把暴力写出来让数据告诉你答案长什么样。