1. 项目概述从一道题看透博弈论与SG函数最近在刷AcWing上的算法题做到第893题“集合-Nim游戏”时感觉这道题真是把博弈论里SG函数的核心思想给讲透了。它不像一些纯理论的证明题那么枯燥而是给你一个具体的游戏规则让你用代码去实现胜负判断非常适合用来理解和掌握SG函数这个强大的工具。很多朋友一听到“博弈论”、“SG函数”就觉得头大感觉是数学竞赛里的东西离日常编程很远。其实不然这类问题在游戏AI、资源竞争调度甚至一些分布式系统的状态协调中都有潜在的应用。这道题被标记为“模板题”是非常贴切的因为它几乎涵盖了SG函数应用的所有标准步骤定义有向图游戏、计算每个状态的SG值、利用SG定理判断初始状态的胜负。如果你能独立把这道题啃下来并且理解每一行代码背后的逻辑那么博弈论的大门就算是对你敞开了。这篇文章我就结合自己反复调试和思考的过程把这道题的解题思路、代码实现细节以及容易踩的坑掰开揉碎了讲清楚。无论你是正在备战算法竞赛还是单纯对博弈论感兴趣相信都能从中获得可以直接“抄作业”的实操经验。2. 核心思路拆解为什么SG函数是博弈问题的“通用裁判”在直接看代码之前我们必须先搞清楚面对“集合-Nim游戏”这类问题我们的大脑应该遵循什么样的思考路径。盲目套模板是学不会的必须理解其内在的逻辑链。2.1 问题重述与游戏建模题目描述可以抽象为给定一个集合 S包含若干个正整数即每次可以取走的石子数。现在有 n 堆石子每堆有 hi 个。两名玩家轮流操作每次可以选择任意一堆石子并从该堆中取走石子但取走的数量必须是集合 S 中的某个数。无法操作者判负。我们的核心任务是给定所有 hi判断先手是否必胜。第一步也是最重要的一步是进行“游戏分解”。这不是一个整体的游戏而是由 n 个独立的“子游戏”组成的。每个子游戏就是“一堆石子”。为什么可以独立因为规则规定玩家每次只能对一堆石子进行操作从某一堆里取走一定数量的石子。各堆石子之间没有直接的相互影响比如从一堆取走石子不会增加或减少另一堆的数量。这种“每次操作仅影响其中一个独立组件”的特性正是应用“SG定理”的前提。于是一个复杂的 n 堆游戏被我们拆解成了 n 个一模一样的“单堆有向图游戏”。接下来我们只需要研究清楚一个单堆游戏的胜负规律就能通过SG定理推导出全局的胜负。2.2 SG函数为每个游戏状态贴上“胜负标签”SG函数是整个博弈论现代体系的基石。它的核心思想是为有向图游戏中的每一个状态局面分配一个非负整数值即SG值。这个值精妙地编码了该状态的胜负属性。它的定义是递归的终点状态无法进行任何移动的状态即没有出边的状态其SG值为 0。对应到我们的问题就是某一堆石子数为0不能再取了。非终点状态设当前状态为 x它可以转移到若干个后继状态 y1, y2, ..., yk。那么状态 x 的 SG 值等于它所有后继状态 SG 值的集合的mexminimum excludant即最小非负整数。这个定义有点绕我用一个生活化的类比来解释。想象每个状态是一个“盒子”盒子里装着一些数字它的后继状态的SG值。SG值就是这个盒子所缺少的最小非负整数。比如一个盒子里面有 {0, 1, 3}那么它缺少的最小非负整数是 2所以它的SG值就是2。如果盒子是空的 {}那么缺少的最小非负整数就是0。SG值的神奇之处在于SG(x) 0意味着状态 x 是“必败状态”P-position。因为从这个状态出发玩家无法操作终点或者无论怎么操作都会将对手送入一个SG值不为0的状态即必胜状态。SG(x) ≠ 0意味着状态 x 是“必胜状态”N-position。因为玩家总可以找到一个操作将状态转移到某个SG值为0的后继状态从而把必败局面丢给对手。这样SG函数就将复杂的博弈推理转化为了一个相对机械的数值计算过程。我们不需要再去画庞大的博弈树只需要递归或递推地算出每个状态的SG值即可。2.3 SG定理组合游戏的胜负判决书当我们把n个独立的子游戏组合起来时SG定理给出了全局胜负的终极公式全局的SG值等于所有子游戏SG值的异或XOR和。即设 n 个子游戏的状态分别为 s1, s2, ..., sn那么组合游戏的SG值为SG(s1) ^ SG(s2) ^ ... ^ SG(sn)。判断准则极其简洁若异或和 ≠ 0则先手必胜。若异或和 0则先手必败。这其实就是经典Nim游戏结论的推广。在经典Nim中每堆石子可以取任意正数个其SG值恰好等于该堆的石子数。SG定理告诉我们对于更一般的、每堆有自己的取法规则集合S的游戏我们只需要先算出每堆在自身规则下的SG值然后再将它们异或起来就能得到答案。至此我们的解题路线图已经完全清晰预处理对于给定的集合 S计算出石子数量从 0 到最大堆石子数题目中hi的最大值记作 MaxH的所有状态的SG值。因为每堆游戏是独立的且规则相同我们可以一次性算好避免重复计算。单堆SG计算对于石子数为 i 的状态它的后继状态就是i - s其中 s 属于集合 S且i - s 0。我们收集这些后继状态的SG值求其mex即为SG(i)。全局判断读入每一堆的石子数 hi查找其预计算好的SG(hi)然后将所有SG(hi)进行异或。根据异或结果是否为0输出答案。注意这里有一个关键优化点。计算SG(i)时我们需要知道所有SG(i-s)。这天然是一个递推或记忆化搜索的过程。我们可以从SG(0)0开始逐步计算到SG(MaxH)。在计算SG(i)时所有小于 i 的SG值都已经计算完毕可以直接查询。这比纯递归高效得多。3. 代码实现与逐行解析理解了理论我们来看C实现。我会把代码分成几个功能模块并详细解释每一部分的作用和编写时的考量。3.1 头文件、变量定义与输入#include iostream #include cstring #include unordered_set using namespace std; const int N 110, M 10010; // N: 集合S最大大小M: 最大石子数 int s[N], sg[M]; // s[]: 存储可取石子数的集合 sg[]: 记忆化存储每个石子数对应的SG值 int k, n; // k: 集合S中元素个数 n: 石子堆数 int main() { cin k; for (int i 0; i k; i ) cin s[i]; cin n; ... }头文件选择iostream用于输入输出cstring用于memset函数初始化数组unordered_set是计算mex的关键它提供了O(1)平均时间复杂度的查找比数组标记更通用尤其当SG值可能很大时。数组大小N110,M10010是根据题目数据范围k≤100, hi≤10000设定的。适当留一点余量是好习惯。变量作用s[N]: 存储题目给出的集合S。sg[M]: 这是我们的“记忆化数组”或“DP表”。sg[x]表示石子数为 x 时该单堆游戏的SG值。初始化为-1表示未计算。k, n: 分别对应集合大小和石子堆数。3.2 核心计算SG值的记忆化搜索函数这是整个程序的灵魂。我们采用记忆化搜索Memoization DFS的方式来计算SG值。// 记忆化搜索计算SG值 int dfs(int x) { if (sg[x] ! -1) return sg[x]; // 记忆化已经计算过直接返回 unordered_setint S; // 用于存储当前状态x的所有后继状态的SG值 for (int i 0; i k; i ) { int take s[i]; // 本次可以取走的石子数 if (x take) { S.insert(dfs(x - take)); // 递归计算后继状态x-take的SG值并插入集合 } } // 计算 mex找出集合S中不存在的最小非负整数 for (int i 0; ; i ) { if (!S.count(i)) { sg[x] i; // 找到mex赋值并返回 return sg[x]; } } }函数签名int dfs(int x)输入当前石子数x返回其SG值。记忆化检查第一行判断sg[x]是否为 -1。如果不是-1说明之前已经计算过直接返回结果。这是避免指数级重复计算的关键将时间复杂度从O(k^n)降到了O(M * k)。在本题中M最大为10000k最大为100计算量在百万级别完全可以接受。后继状态集合我们用一个unordered_setint S来存储所有可能的后继状态x - take的SG值。使用集合是为了自动去重因为不同的取法take可能到达相同的后继状态虽然本题中集合S元素互异但习惯上这样写更稳健。递归计算对于集合S中的每个合法取法x take我们递归调用dfs(x - take)来计算后继状态的SG值并将其插入集合S。这里递归的深度最多为x但由于记忆化的存在每个状态只会被计算一次。计算mex这是最精妙的一步。用一个从0开始的无限循环for (int i 0; ; i )检查当前的i是否在集合S中。S.count(i)在集合中返回1不在返回0。当找到第一个不在S中的i时它就是mex也就是当前状态x的SG值。将其存入sg[x]并返回。为什么循环能结束因为集合S的大小最多是k可取法的个数它是一个有限集。而自然数是无限的所以必然存在一个最小的自然数不在这个有限集中。最坏情况下如果S包含了0,1,2,...,k-1那么mex就是k。所以这个循环最多执行k1次。实操心得在计算mex时初学者容易犯两个错误。一是用数组代替集合但数组需要开足够大的全局空间且要知道SG值的上界。而unordered_set是动态的更安全通用。二是忘记初始化sg数组为-1。如果初始化为0那么if(sg[x] ! -1)的判断就会出错因为sg[0]0是有效值必须能正确返回。3.3 初始化与主逻辑流程memset(sg, -1, sizeof sg); // 初始化sg数组为-1表示未计算 sg[0] 0; // 边界条件石子数为0时无法操作SG值为0 int res 0; // 用于累加所有石子堆SG值的异或和 while (n -- ) { int h; cin h; res ^ dfs(h); // 计算当前堆的SG值并与之前的结果异或 } if (res) puts(Yes); // 异或和非零先手必胜 else puts(No); // 异或和为零先手必败初始化memset(sg, -1, sizeof sg)将整个sg数组填充为-1。然后显式地将sg[0]设为 0这是递归的基准情况。主循环依次读入每堆的石子数h。对于每一堆调用dfs(h)计算其SG值。这里dfs函数会通过记忆化搜索高效地计算或直接返回已计算的结果。然后使用^运算符将结果累加到res中。胜负判断所有堆处理完毕后检查res。不为0则输出”Yes”否则输出”No”。这个判断直接对应SG定理。3.4 完整代码整合将上述所有部分组合起来就得到了ACAccepted的完整代码#include iostream #include cstring #include unordered_set using namespace std; const int N 110, M 10010; int s[N], sg[M]; int k, n; int dfs(int x) { if (sg[x] ! -1) return sg[x]; unordered_setint S; for (int i 0; i k; i ) { int take s[i]; if (x take) { S.insert(dfs(x - take)); } } for (int i 0; ; i ) { if (!S.count(i)) { sg[x] i; return sg[x]; } } } int main() { cin k; for (int i 0; i k; i ) cin s[i]; cin n; memset(sg, -1, sizeof sg); sg[0] 0; int res 0; while (n -- ) { int h; cin h; res ^ dfs(h); } if (res) puts(Yes); else puts(No); return 0; }4. 深度剖析时间复杂度、空间复杂度与优化思考写完能AC的代码只是第一步理解其性能边界和潜在优化点才能算是真正掌握。4.1 复杂度分析时间复杂度这是分析的重点。整个算法的时间主要花费在计算sg数组上。我们需要计算从 0 到MaxH所有hi的最大值的每个状态的SG值。对于每个状态xdfs(x)函数需要遍历集合S中的所有k种取法。对于每种合法取法需要查询或计算后继状态x-s的SG值。由于记忆化的存在每个状态x的dfs(x)主体计算部分即mex计算只会执行一次。因此总的时间复杂度为O(MaxH * k)。其中MaxH ≤ 10000,k ≤ 100最坏运算量在10^6级别对于C来说非常轻松。空间复杂度sg数组O(MaxH)约10000 * 4字节 ≈ 40KB。dfs递归调用栈最深深度为MaxH但在记忆化优化下实际递归树是线性的不会爆栈MaxH10000在通常的栈空间限制内是安全的。unordered_set S在每个dfs调用中临时创建最多存储k个元素。由于递归深度可能较大但同一时间存在的集合数量等于递归深度总的空间开销是 O(MaxH * k) 的但常数较小。这是主要的空间开销点但仍在可接受范围内。4.2 从记忆化搜索到递推DP我们当前的实现是“自上而下”的记忆化搜索。实际上由于SG(x)只依赖于更小的SG(y)(y x)这个问题完全可以写成“自下而上”的递推形式也就是更标准的动态规划。递推版伪代码如下// 初始化 sg[0] 0; for (int x 1; x MaxH; x ) { unordered_setint S; for (int i 0; i k; i ) { if (x s[i]) S.insert(sg[x - s[i]]); } // 计算 mex for (int i 0; ; i ) { if (!S.count(i)) { sg[x] i; break; } } }两种实现的对比记忆化搜索 (DFS Memoization)优点思维更直观更贴近SG函数的递归定义。代码写起来更“懒”只计算需要用到状态即输入中出现的hi如果hi的分布很稀疏可能比递推计算所有状态更快。缺点有递归调用开销并且需要处理递归栈。对于极深的状态虽然本题不深有栈溢出风险。递推 (DP)优点运行效率通常略高于递归没有栈溢出风险。代码结构是简单的循环一目了然。缺点必须计算从0到MaxH的所有状态即使有些状态用不到。当MaxH非常大而实际用到的状态很少时可能浪费计算。在本题数据范围内两种方法性能差异微乎其微。记忆化搜索的写法在算法竞赛中更为常见因为它更具通用性对于状态转移不那么规整的问题也能处理。4.3 关于mex计算的进一步优化我们目前用unordered_set和循环找mex对于每个状态x时间复杂度是 O(k)构建集合 O(mex值)查找。mex值最大可能为k。所以每个状态是 O(k) 的。有一种更高效的、O(k) 时间内计算mex的方法适用于k较大的情况本题k≤100没必要使用一个布尔数组vis大小设为k2因为mex最大为k1。遍历后继状态将其SG值作为下标标记vis[sg_val] true。然后从0开始遍历vis数组第一个vis[i] false的i就是mex。这种方法将mex查找的循环从while不确定循环变成了确定性的for循环在常数上可能更优但需要提前知道SG值的上界。在通用模板中使用unordered_set是更稳妥和清晰的选择。5. 典型问题排查与实战调试技巧即便思路清晰代码在编写和调试过程中也难免遇到问题。下面是我在解决这类问题时总结的几个常见坑点和调试方法。5.1 常见错误与原因分析错误现象可能原因解决方案输出全部错误或部分错误1.sg数组未初始化或初始化错误。2.dfs函数中未正确实现记忆化导致重复计算或死循环。3. mex计算逻辑错误例如循环条件写错。1. 确认memset(sg, -1, sizeof sg)和sg[0]0已正确执行。2. 在dfs函数开头添加cout “calculating: ” x endl;观察是否对同一x重复进入计算主体。3. 在计算mex的循环后输出x和计算出的sg[x]核对是否正确。时间超限 (TLE)1. 没有使用记忆化进行了指数级的重复递归。2. 集合S使用不当如用了set而非unordered_set导致插入和查找是O(log k)。3. 在dfs中错误地传递了大型容器如vector作为参数导致拷贝开销巨大。1.这是最可能的原因。务必检查if(sg[x] ! -1) return sg[x];这行代码是否存在且正确。2. 确认使用的是#include unordered_set和unordered_setint S。set在数据量小时影响不大但习惯用哈希集合更好。3. 确保S是函数内局部变量不要作为参数传递。段错误 (Segmentation Fault)1. 数组越界。例如s[i]的i可能超过k或dfs(x-s[i])中的x-s[i]为负数。2. 递归深度过深导致栈溢出本题数据范围通常不会。1. 仔细检查所有数组访问的下标。在dfs中if (x take)这个判断至关重要确保不会递归到负数状态。2. 可以尝试将递归改为递推DP版本。答案对个别大数据错误1. 异或运算^使用错误或者res未初始化为0。2. 输入数据范围理解错误数组sg或s开小了。1. 检查res是否初始化为0以及res ^ dfs(h)是否写对。2. 重新审题确认hi和k的最大值适当调大N和M的常量定义。5.2 实用的调试策略当你的代码没有按预期工作时可以按以下步骤排查小数据测试构造最小的、能体现问题特征的测试用例。输入k1, s[0]1(只能取1个)n1, h[0]1。手动推导SG(0) 0。SG(1)后继状态只有1-10其SG值为0。后继集合S {0}。mex({0}) 1。所以SG(1)1。全局异或和 SG(1) 1非零先手必胜。应该输出”Yes”。用这个用例跑你的程序看输出是否正确。这是检验基本逻辑的试金石。打印关键变量在dfs函数中计算完sg[x]后将其打印出来。sg[x] i; // 调试用cout sg[ x ] sg[x] endl; return sg[x];对比你手动计算的小数据如x1,2,3的SG值看是否一致。验证记忆化在dfs函数开头打印进入计算的状态。if (sg[x] ! -1) return sg[x]; // 调试用cout dfs computing: x endl;对于重复的输入同一个x应该只打印一次。如果看到多次打印同一个x说明记忆化失效了很可能是sg数组初始化不对。边界条件检查特别注意x0的情况。确保你的dfs函数能正确处理它直接返回sg[0]0。同时检查在for循环遍历取法s[i]时if(x take)这个条件是否包含了xtake的情况即取完。5.3 一个更复杂的测试用例为了确保代码健壮性可以测试一个稍复杂的例子输入 3 2 5 7 3 15 11 3集合 S{2, 5, 7}三堆石子15, 11, 3你可以手动或写个小脚本计算前20个SG值然后验证程序的输出。通过这类测试能很好地巩固对SG函数计算过程的理解。6. 从模板题到举一反三SG函数的应用扩展掌握这道模板题后SG函数就不再是黑盒了。你可以尝试解决一些变体问题深化理解。6.1 变体一每次操作可以涉及多堆Anti-SG 或 Misère Nim经典规则是“每次只能操作一堆”。如果规则变为“每次必须操作且必须对至少一堆进行操作也可以对多堆进行操作但每堆的操作必须独立且符合其规则”这通常被称为“反常游戏”Misère Play。其胜负判定有时会与正常规则不同需要特别分析。不过对于大部分“每次操作仅影响一个独立子游戏”的题目SG定理依然适用。6.2 变体二图上的移动游戏SG函数起源于“有向图游戏”。最经典的例子是“移棋子”游戏在一个有向无环图上一个棋子放在某个起点两人轮流沿有向边移动棋子无法移动者输。这个游戏的SG值定义与我们的石子游戏完全一致终点出度为0的点SG值为0非终点其SG值为所有后继节点SG值的mex。多个这样的棋子游戏组合起来胜负判断同样是所有棋子所在节点SG值的异或和。这直接将博弈问题转化为了图论问题。6.3 变体三公平组合游戏的其他模型除了取石子公平组合游戏还有很多模型例如翻硬币游戏一排硬币每次可以翻转连续若干枚但最右边的必须从正面翻到反面。剪纸游戏一张网格纸每次沿格线剪一刀剪下部分丢弃。Chomp游戏一块巧克力每次吃掉左下角一块及其右方和上方的所有部分。这些游戏看似千差万别但抽象后都可以建模为“状态”和“合法操作”进而尝试计算其SG函数。解题的关键在于识别出独立的子游戏并找到高效计算单个子游戏SG值的方法有时需要找规律有时需要DP。6.4 在算法竞赛中的定位与学习建议“集合-Nim游戏”在AcWing上属于“数学知识”章节下的“博弈论”部分难度标注为“简单”。但它所蕴含的思想是深刻的。在更高级的竞赛如ICPC、CCPC中博弈论问题往往不会直接裸考SG定理而是将其作为核心组件与其他算法如数论、图论、DP结合。对于想深入学习的同学我的建议是吃透模板把这道题的代码和理解做到肌肉记忆级别。刷同类题在AcWing、LeetCode、Codeforces等平台搜索“SG函数”、“博弈论”、“Game Theory”标签的题目进行专项练习。学习经典模型了解Bash Game、Wythoff Game、Fibonacci Nim等经典博弈模型理解它们如何归约到SG函数或者有其独特的简洁结论。尝试推导SG值规律对于某些游戏SG值可能有周期性或简单的公式。尝试自己推导小数据下的SG值观察规律并尝试证明。这是提升思维能力的关键。回过头看这道“集合-Nim游戏”就像一把钥匙帮你打开了公平组合游戏理论的大门。它所展示的“分解-求解-组合”的思路不仅是解决博弈问题的利器也是一种普适的算法设计思想。当你再遇到复杂的、轮流的、完全信息的游戏时不妨想一想它能被分解成独立的子游戏吗每个子游戏的SG值能算出来吗如果能那么答案就在那个异或和里了。