1. 从“石头游戏”到SG函数理解博弈论问题的通用解法如果你刷过一些算法题尤其是涉及到两人轮流操作、无法操作者判负的题目你大概率听说过“博弈论”。但很多人一看到“博弈论”、“SG函数”这些词就头大觉得是数学竞赛的专属离日常编程很远。其实不然这类问题在游戏AI、资源分配、甚至一些系统调度策略中都有应用。今天我们就以AcWing上这道经典的“集合-Nim游戏”为引子彻底搞懂SG函数这个博弈论问题的“万能钥匙”。这道题的本质是经典Nim游戏的变种。普通的Nim游戏里你可以从一堆石子中取走任意正整数个。而“集合-Nim”给它加了个限制你每次能取的石子数量必须属于一个预先给定的集合S。比如S{2, 5}那你一次只能取2个或5个。题目会给你多堆石子以及这个取法集合S问先手是否必胜。为什么SG函数能成为这类问题的通解简单来说它把每一个独立的游戏局面比如一堆有x个石子的石堆映射成一个非负整数值SG值。然后一个复杂游戏多堆石子的胜负就神奇地转化为了这些独立SG值之间的异或XOR运算。如果总异或值为0先手必败否则先手必胜。这个结论和普通Nim游戏的结论形式一模一样但SG函数让它的适用范围从“任意取”扩展到了“按规则取”威力巨大。所以学习这道题你收获的不仅仅是一个模板更是一种将复杂、不规则的博弈游戏转化为标准Nim模型进行快速判定的系统性思维。接下来我会带你从零推导这个思维过程并用C实现一个清晰高效的解法。2. SG函数的核心思想把“局面”变成“数字”要理解SG函数我们必须先忘掉那些复杂的数学定义从最直观的“状态图”开始想。2.1 游戏的有向图模型假设我们现在只有一堆石子数量是x允许取的石子数集合是S {2, 5}。我们可以把这个游戏看作一个有向图节点状态当前石堆中剩余的石子数i(0 i x)。i0是终止状态无法操作。边操作如果从状态i通过一次合法的操作取走s个石子其中s属于集合S且s i能够到达状态j i - s那么就存在一条从i指向j的有向边。例如对于x10从状态10可以走到8取2或5取5。从状态3只能走到1取2因为取5不合法从状态1则无法走到任何其他状态因为最小的可取数2 1。我们的目标是判断在初始状态x下先手是必胜还是必败。这是一个典型的“有向无环图DAG上的博弈”问题。2.2 最小非负整数SG值的朴素定义SG函数为每个状态i分配一个值SG(i)。它的定义基于一个核心概念“后继状态的SG值集合”。对于状态i考虑所有从i出发通过一次合法操作能到达的状态j。这些j就是i的“后继状态”。我们把这些后继状态的SG值收集起来形成一个集合记作next_SG_set。那么状态i的SG值定义如下SG(i) mex( next_SG_set )这个mex函数是关键。mex(S)表示“最小排除的非负整数”即不属于集合S的最小自然数。比如mex({0, 1, 3}) 2集合里缺2mex({1, 2}) 0集合里缺0mex({}) 0空集最小的自然数是0这个定义非常巧妙。我们来看几个例子假设S{2,5}SG(0)状态0没有后继状态无法操作所以next_SG_set {}。mex({}) 0。因此SG(0) 0。这符合直觉已经没石子了这个局面是必败态。SG(1)从1出发能取2或5吗不能因为都大于1。所以没有合法操作next_SG_set {}。mex({}) 0。SG(1) 0。注意虽然还有1个石子但因为规则限制你无法取走它所以你实际上处于和SG(0)一样的“无法操作”的必败态。SG(2)从2出发可以取2个石子到达状态0。所以next_SG_set {SG(0)} {0}。mex({0}) 1。因此**SG(2) 1**。这个1意味着什么意味着从这个状态出发先手可以走到一个SG值为0的状态即必败态从而把必败态丢给对手。所以SG(2)是一个必胜态。SG(3)从3出发可以取2个到达状态1。next_SG_set {SG(1)} {0}。mex({0}) 1。SG(3) 1。SG(4)从4出发可以取2个到达状态2。next_SG_set {SG(2)} {1}。mex({1}) 0。SG(4) 0。这是一个有趣的局面虽然石子更多但却是必败态。因为你能做的操作取2会把对手送入一个必胜态(SG(2)1)。通过这个过程我们可以递推地计算出所有状态的SG值。SG值揭示了局面的本质属性SG(i) 0无论先手怎么操作都会将局面引向一个SG ! 0的状态即把必胜态送给对手。所以这是一个必败态P-position。SG(i) 0先手至少存在一种操作可以将局面引向一个SG 0的状态即把必败态丢给对手。所以这是一个必胜态N-position。2.3 多堆游戏的组合SG定理单一堆的胜负我们已经能用SG值判断了。那多堆呢这就是SG定理强大之处。SG定理对于一个由多个相互独立的子游戏构成的游戏其整体局面的SG值等于所有子游戏当前局面SG值的异或XOR和。对于我们的“集合-Nim”游戏每一堆石子就是一个独立的子游戏。设我们有k堆石子每堆的初始石子数分别是a1, a2, ..., ak我们分别计算出每堆在给定取法集合S下的SG值SG(a1), SG(a2), ..., SG(ak)。那么整个游戏的胜负就由这个异或和决定如果SG(a1) ^ SG(a2) ^ ... ^ SG(ak) 0则先手必败。否则先手必胜。这个结论和经典Nim游戏S为任意正整数的结论完全一致。在经典Nim中可以证明SG(x) x。所以异或和就变成了a1 ^ a2 ^ ... ^ ak。集合-Nim只是把SG(x)的计算从简单的x变成了由集合S定义的、更复杂的递推关系。但最终的胜负判定公式依然是那个简洁的异或运算。理解了这个整个问题的解决框架就清晰了根据给定的取法集合S预处理计算出足够大范围内比如题目中每堆石子最大数量所有x对应的SG(x)值。这是一个动态规划/记忆化搜索的过程。对于每一堆石子a_i查找其对应的SG(a_i)。计算所有SG(a_i)的异或和根据结果输出胜负。3. 算法实现详解记忆化搜索与状态缓存理论通了代码实现的关键就在于高效、正确地计算每个x的SG(x)。由于SG(x)的计算依赖于它的后继状态且可能被多次查询我们很自然地会想到使用记忆化搜索Memoization。3.1 数据结构与全局定义首先我们需要定义存储取法集合S和SG值缓存的数据结构。#include iostream #include cstring #include unordered_set using namespace std; const int N 110, M 10010; // N: 集合S最大大小 M: 石子数最大范围根据题目调整 int s[N]; // 存储取法集合S int sg[M]; // 记忆化数组sg[x] 表示石子数为x时的SG函数值 int k, n; // k: 集合S的大小 n: 石子的堆数这里有几个细节数组大小M它需要至少覆盖题目中可能出现的最大石子数。在AcWing 893题中每堆石子最多10000颗所以M10010是安全的。设置稍大一点是好习惯。sg数组的初始化我们将其初始化为-1表示该状态的SG值尚未计算。memset(sg, -1, sizeof sg);使用unordered_set在计算mex时我们需要临时存储后继状态的SG值集合。使用C STL中的unordered_set比set更快因为我们只关心插入和查找不需要有序。3.2 记忆化搜索函数getSG(int x)这是整个算法的核心函数用于计算石子数为x时的SG值。int getSG(int x) { // 记忆化如果已经计算过直接返回 if (sg[x] ! -1) return sg[x]; // 哈希表用于存储当前状态x的所有后继状态的SG值 unordered_setint S; // 枚举所有可能的操作取走 s[i] 个石子 for (int i 0; i k; i) { int take s[i]; if (x take) { // 确保操作合法 S.insert(getSG(x - take)); // 递归计算后继状态的SG值并插入集合 } } // 计算 mex(S) for (int i 0; ; i) { // 从0开始枚举自然数 if (!S.count(i)) { // 如果i不在集合S中 sg[x] i; // 找到mex赋值并返回 return i; } } }逐行解析与注意事项递归基与记忆化if (sg[x] ! -1) return sg[x];这是记忆化搜索的标准开头避免重复计算将指数级复杂度降为O(M * k)。后继状态枚举for (int i 0; i k; i)遍历取法集合S。这里有一个关键优化点如果集合S是无序的且可能包含重复值可以在读入后对其进行排序去重确保k是有效操作数。不过本题通常保证输入合法但养成好习惯很重要。操作合法性判断if (x take)必须检查不能从一个只有3个石子的堆里取走5个。递归计算getSG(x - take)计算后继状态的SG值。这里体现了动态规划“自顶向下”的思路。mex的计算for (int i 0; ; i)是一个从0开始的无限循环直到找到第一个不在集合S中的i。由于SG值不会太大理论上不超过操作集合大小k这个循环很快。!S.count(i)是unordered_set的查找操作平均O(1)复杂度。一个重要的边界情况如果x小于S中的最小值那么S集合将为空因为没有任何合法操作。循环for (int i 0; i k; i)不会执行任何插入操作unordered_setint S保持为空。接下来的mex计算循环会找到i0因为S.count(0)为false。所以sg[x] 0。这正对应了我们之前分析的SG(1)的情况是必败态。3.3 主函数逻辑与流程主函数负责组织整个计算流程并应用SG定理进行胜负判断。int main() { // 1. 读入取法集合S cin k; for (int i 0; i k; i) cin s[i]; // 2. 初始化SG记忆化数组 memset(sg, -1, sizeof sg); // 3. 读入石子堆信息并计算每堆的SG值 cin n; int res 0; // 用于计算异或和 for (int i 0; i n; i) { int x; cin x; res ^ getSG(x); // 计算并累加异或 } // 4. 根据SG定理判断胜负并输出 if (res) puts(Yes); // 异或和非零先手必胜 else puts(No); // 异或和为零先手必败 return 0; }流程梳理与思考输入与初始化先读k和集合s然后立即初始化sg数组。这个顺序不能乱因为getSG函数依赖全局的s数组。逐堆处理对于每一堆石子x调用getSG(x)获取其SG值并立刻与当前结果res进行异或。这样做的好处是只需要遍历石子堆一次无需额外数组存储所有SG(a_i)。胜负判定res最终保存了所有子游戏SG值的异或和。if (res)利用了C中非零即真的特性。res ! 0等价于res ! 0。4. 复杂度分析与边界情况处理一个健壮的算法实现必须清楚其性能边界和可能遇到的坑。4.1 时间复杂度分析设最大石子数为MaxX对应数组大小M取法集合大小为k石子堆数为n。getSG函数对于每个状态x最多会计算一次。计算它需要遍历k种操作常数时间并对每个合法操作递归计算后继状态已记忆化可视为O(1)。然后计算mex由于SG值范围有限这个循环可视为常数时间通常远小于k。所以计算单个SG(x)的摊还代价是O(k)。总体复杂度我们需要计算从0到MaxX实际上只需要计算输入中出现的x但最坏情况是n堆都不同且都接近MaxX所有可能状态的SG值。因此总时间复杂度为O(MaxX * k n)。在本题限制下MaxX约1e4k约100这个复杂度是完全可接受的。4.2 空间复杂度分析sg数组O(MaxX)。s数组O(k)。递归调用栈最坏深度为MaxX但实际由于记忆化不会出现很深的重复递归。空间复杂度为O(MaxX)递归栈O(MaxX)sg数组 ≈O(MaxX)。4.3 常见边界与陷阱取法集合S包含0或负数题目通常保证s[i]是正整数。如果包含0会导致无限递归x-0x。如果包含负数逻辑上无意义。防御性编程可以在读入后对s数组进行排序和去重并检查元素是否为正整数。石子数x为0我们的getSG(0)会正确返回0。在主循环中res ^ getSG(0)等同于res ^ 0不影响结果。这是符合定义的一堆0个石子的游戏SG值为0必败态。sg数组未初始化务必用-1或其他不可能出现的值初始化sg数组这是记忆化搜索正确工作的前提。我见过有人用0初始化然后误判很多状态已经计算因为SG值可能就是0导致错误。unordered_set的作用域unordered_setint S必须定义在getSG函数内部。每次调用getSG(x)都需要一个新的集合来存储当前x的后继SG值。如果定义为全局变量需要在每次调用前后清理非常容易出错。异或运算的优先级res ^ getSG(x)是安全的。但如果你写成res res ^ getSG(x)也没问题。注意^的优先级低于和!但在赋值表达式中通常没问题。5. 从模板到理解调试与验证策略能写出代码只是第一步能验证其正确性并理解其过程更重要。下面提供几种方法。5.1 小规模数据手动模拟选择一组很小的数据在纸上或心里模拟程序运行。示例设S {2, 3}, 计算SG(0)到SG(5)。SG(0) mex({}) 0SG(1) mex({}) 0(无法取2或3)SG(2) mex({SG(0)}) mex({0}) 1SG(3) mex({SG(0), SG(1)})?等等从3可以取2到1取3到0。所以是mex({SG(1), SG(0)}) mex({0, 0}) mex({0}) 1。SG(4) mex({SG(2), SG(1)}) mex({1, 0}) 2(因为0和1都在集合里最小不在的是2)SG(5) mex({SG(3), SG(2)}) mex({1, 1}) mex({1}) 0然后你可以设计一个两堆的游戏比如两堆分别是(2, 3)。SG(2)^SG(3) 1^1 0先手必败。你可以手动推演一下确实无论先手在第一堆怎么动只能取2变成(0,3)或者第二堆怎么动取2变(2,1)取3变(2,0)后手都能应对并最终获胜。5.2 添加调试输出在getSG函数中加入打印语句观察计算过程。int getSG(int x) { if (sg[x] ! -1) { // cout Memory hit: sg[ x ] sg[x] endl; return sg[x]; } unordered_setint S; for (int i 0; i k; i) { int take s[i]; if (x take) { int next_sg getSG(x - take); // cout From x , take take - x-take (SG next_sg ) endl; S.insert(next_sg); } } // 计算mex for (int i 0; ; i) { if (!S.count(i)) { sg[x] i; // cout Computed: sg[ x ] mex{...} i endl; return i; } } }通过这种输出你可以清晰地看到递归调用的路径、后继状态的SG值以及最终mex的计算结果。这对于理解算法和排查错误非常有帮助。5.3 测试用例设计设计涵盖各种情况的测试用例基础验证S{1}, 任何一堆石子数xSG(x)x。这就是经典Nim。测试(1,2,3)异或和1^2^30应输出No。必败态测试S{2,5}, 单堆x1或x4SG值应为0。多堆时全部选这种SG0的堆异或和为0应输出No。边界测试x0的情况。S中包含大于最大石子数的值的情况。性能测试用最大数据量测试如k100,S中元素随机n100,x接近10000确保不超时。6. 举一反三SG函数应用的扩展场景掌握了集合-Nim这个模板你就拥有了解决一大类公平组合游戏Impartial Combinatorial Games的能力。这类游戏的特点是两人轮流操作操作集合只依赖于当前状态而与玩家无关即“公平”且无法操作者判负。以下是一些变种和扩展思路6.1 操作集合动态变化在集合-Nim中取法集合S是全局固定的。但有些题目中S可能依赖于当前石子数x。例如每次可以取1到floor(x/2)个石子。这时你只需要修改getSG函数中枚举后继状态的部分for (int take 1; take x / 2; take) { // 操作集合变为1到x/2 S.insert(getSG(x - take)); }算法的核心框架记忆化搜索 mex计算完全不变。6.2 多维度状态与拆分游戏有些游戏的状态不是单一数字。例如有一个n*m的棋盘每次可以拿走一个格子及其右方和下方的所有格子。这个游戏可以看作是多个独立的“行”游戏和“列”游戏的组合吗不一定。但更通用的方法是将整个棋盘状态(i,j)作为一个节点计算其SG值。这可能需要二维甚至更高维度的记忆化数组。更常见的一种强大技巧是游戏拆分。如果一个大游戏可以看成是几个完全独立的子游戏同时进行那么整个游戏的SG值就是各子游戏SG值的异或和。这就是SG定理的直接应用。很多看似复杂的游戏经过巧妙分析可以被拆分成独立的Nim堆。6.3 非DAG的博弈无限递归SG函数和记忆化搜索的前提是游戏图是一个有向无环图DAG即游戏总能在有限步内结束。如果游戏有可能陷入循环例如某些棋类游戏标准的SG函数方法就失效了需要更复杂的分析如和棋规则、无限循环判负等。在算法竞赛中题目通常会保证局面是DAG。6.4 从“胜负”到“方案”SG函数通常只告诉我们当前局面是必胜还是必败。但有时题目还要求如果必胜请输出一种必胜操作。这该如何做在计算出整体异或和res后如果res ! 0我们知道先手必胜。要找到一种操作其实就是找到一堆石子a_i对其进行一次合法操作后使得新的异或和变为0。假设我们对第i堆操作取走t个石子t属于S且t a_i。操作后该堆石子数变为a_i - t其SG值变为SG(a_i - t)。我们希望操作后所有堆的SG值异或和为0即(res ^ SG(a_i) ^ SG(a_i - t)) 0这等价于SG(a_i - t) res ^ SG(a_i)所以寻找必胜操作的算法是遍历每一堆石子i。计算target res ^ SG(a_i)。target的含义是为了使得总异或和为0操作后第i堆的SG值需要等于target。遍历所有合法操作t属于S且t a_i计算new_sg SG(a_i - t)。如果存在某个t使得new_sg target那么这就是一个必胜操作。输出i和t即可。这个思路完美体现了SG函数的威力它不仅判断胜负还能指导我们如何行动。7. 总结与个人心得回顾整个“集合-Nim游戏”的解题过程其核心脉络非常清晰定义状态 - 计算单状态SG值记忆化搜索mex - 多状态组合求异或和 - 根据异或和判断胜负。这几乎是一个可以解决所有公平组合游戏问题的标准框架。我在最初学习时曾纠结于mex函数为什么这样定义。后来想明白了它本质上是一种递归的、逆向的必胜/必败态分析。SG(x)0意味着所有后继都是“非零”必胜态所以当前是必败态。SG(x)0意味着存在一个后继是“零”必败态所以当前是必胜态。mex操作是保证这种0/非0性质递推下去的最简洁数学表达。在实现上最大的坑就是记忆化数组的初始化和**unordered_set的局部作用域**。我强烈建议在开始写记忆化搜索时就把if (sg[x] ! -1) return sg[x];和unordered_setint S;作为固定模板写下来。最后不要满足于套模板AC题目。多用手算小数据理解SG值是如何一步步产生的。尝试修改题目条件比如改变操作集合S的规则自己设计测试用例验证。当你能够不假思索地写出getSG函数并且能向别人解释清楚为什么异或和能决定胜负时你才算真正掌握了这把博弈论的利器。这道题在AcWing上标为“简单”但它的思想一点也不简单。吃透它很多复杂的博弈题在你眼里都会变成纸老虎。
博弈论SG函数：从Nim游戏到集合-Nim的算法解析与实现
1. 从“石头游戏”到SG函数理解博弈论问题的通用解法如果你刷过一些算法题尤其是涉及到两人轮流操作、无法操作者判负的题目你大概率听说过“博弈论”。但很多人一看到“博弈论”、“SG函数”这些词就头大觉得是数学竞赛的专属离日常编程很远。其实不然这类问题在游戏AI、资源分配、甚至一些系统调度策略中都有应用。今天我们就以AcWing上这道经典的“集合-Nim游戏”为引子彻底搞懂SG函数这个博弈论问题的“万能钥匙”。这道题的本质是经典Nim游戏的变种。普通的Nim游戏里你可以从一堆石子中取走任意正整数个。而“集合-Nim”给它加了个限制你每次能取的石子数量必须属于一个预先给定的集合S。比如S{2, 5}那你一次只能取2个或5个。题目会给你多堆石子以及这个取法集合S问先手是否必胜。为什么SG函数能成为这类问题的通解简单来说它把每一个独立的游戏局面比如一堆有x个石子的石堆映射成一个非负整数值SG值。然后一个复杂游戏多堆石子的胜负就神奇地转化为了这些独立SG值之间的异或XOR运算。如果总异或值为0先手必败否则先手必胜。这个结论和普通Nim游戏的结论形式一模一样但SG函数让它的适用范围从“任意取”扩展到了“按规则取”威力巨大。所以学习这道题你收获的不仅仅是一个模板更是一种将复杂、不规则的博弈游戏转化为标准Nim模型进行快速判定的系统性思维。接下来我会带你从零推导这个思维过程并用C实现一个清晰高效的解法。2. SG函数的核心思想把“局面”变成“数字”要理解SG函数我们必须先忘掉那些复杂的数学定义从最直观的“状态图”开始想。2.1 游戏的有向图模型假设我们现在只有一堆石子数量是x允许取的石子数集合是S {2, 5}。我们可以把这个游戏看作一个有向图节点状态当前石堆中剩余的石子数i(0 i x)。i0是终止状态无法操作。边操作如果从状态i通过一次合法的操作取走s个石子其中s属于集合S且s i能够到达状态j i - s那么就存在一条从i指向j的有向边。例如对于x10从状态10可以走到8取2或5取5。从状态3只能走到1取2因为取5不合法从状态1则无法走到任何其他状态因为最小的可取数2 1。我们的目标是判断在初始状态x下先手是必胜还是必败。这是一个典型的“有向无环图DAG上的博弈”问题。2.2 最小非负整数SG值的朴素定义SG函数为每个状态i分配一个值SG(i)。它的定义基于一个核心概念“后继状态的SG值集合”。对于状态i考虑所有从i出发通过一次合法操作能到达的状态j。这些j就是i的“后继状态”。我们把这些后继状态的SG值收集起来形成一个集合记作next_SG_set。那么状态i的SG值定义如下SG(i) mex( next_SG_set )这个mex函数是关键。mex(S)表示“最小排除的非负整数”即不属于集合S的最小自然数。比如mex({0, 1, 3}) 2集合里缺2mex({1, 2}) 0集合里缺0mex({}) 0空集最小的自然数是0这个定义非常巧妙。我们来看几个例子假设S{2,5}SG(0)状态0没有后继状态无法操作所以next_SG_set {}。mex({}) 0。因此SG(0) 0。这符合直觉已经没石子了这个局面是必败态。SG(1)从1出发能取2或5吗不能因为都大于1。所以没有合法操作next_SG_set {}。mex({}) 0。SG(1) 0。注意虽然还有1个石子但因为规则限制你无法取走它所以你实际上处于和SG(0)一样的“无法操作”的必败态。SG(2)从2出发可以取2个石子到达状态0。所以next_SG_set {SG(0)} {0}。mex({0}) 1。因此**SG(2) 1**。这个1意味着什么意味着从这个状态出发先手可以走到一个SG值为0的状态即必败态从而把必败态丢给对手。所以SG(2)是一个必胜态。SG(3)从3出发可以取2个到达状态1。next_SG_set {SG(1)} {0}。mex({0}) 1。SG(3) 1。SG(4)从4出发可以取2个到达状态2。next_SG_set {SG(2)} {1}。mex({1}) 0。SG(4) 0。这是一个有趣的局面虽然石子更多但却是必败态。因为你能做的操作取2会把对手送入一个必胜态(SG(2)1)。通过这个过程我们可以递推地计算出所有状态的SG值。SG值揭示了局面的本质属性SG(i) 0无论先手怎么操作都会将局面引向一个SG ! 0的状态即把必胜态送给对手。所以这是一个必败态P-position。SG(i) 0先手至少存在一种操作可以将局面引向一个SG 0的状态即把必败态丢给对手。所以这是一个必胜态N-position。2.3 多堆游戏的组合SG定理单一堆的胜负我们已经能用SG值判断了。那多堆呢这就是SG定理强大之处。SG定理对于一个由多个相互独立的子游戏构成的游戏其整体局面的SG值等于所有子游戏当前局面SG值的异或XOR和。对于我们的“集合-Nim”游戏每一堆石子就是一个独立的子游戏。设我们有k堆石子每堆的初始石子数分别是a1, a2, ..., ak我们分别计算出每堆在给定取法集合S下的SG值SG(a1), SG(a2), ..., SG(ak)。那么整个游戏的胜负就由这个异或和决定如果SG(a1) ^ SG(a2) ^ ... ^ SG(ak) 0则先手必败。否则先手必胜。这个结论和经典Nim游戏S为任意正整数的结论完全一致。在经典Nim中可以证明SG(x) x。所以异或和就变成了a1 ^ a2 ^ ... ^ ak。集合-Nim只是把SG(x)的计算从简单的x变成了由集合S定义的、更复杂的递推关系。但最终的胜负判定公式依然是那个简洁的异或运算。理解了这个整个问题的解决框架就清晰了根据给定的取法集合S预处理计算出足够大范围内比如题目中每堆石子最大数量所有x对应的SG(x)值。这是一个动态规划/记忆化搜索的过程。对于每一堆石子a_i查找其对应的SG(a_i)。计算所有SG(a_i)的异或和根据结果输出胜负。3. 算法实现详解记忆化搜索与状态缓存理论通了代码实现的关键就在于高效、正确地计算每个x的SG(x)。由于SG(x)的计算依赖于它的后继状态且可能被多次查询我们很自然地会想到使用记忆化搜索Memoization。3.1 数据结构与全局定义首先我们需要定义存储取法集合S和SG值缓存的数据结构。#include iostream #include cstring #include unordered_set using namespace std; const int N 110, M 10010; // N: 集合S最大大小 M: 石子数最大范围根据题目调整 int s[N]; // 存储取法集合S int sg[M]; // 记忆化数组sg[x] 表示石子数为x时的SG函数值 int k, n; // k: 集合S的大小 n: 石子的堆数这里有几个细节数组大小M它需要至少覆盖题目中可能出现的最大石子数。在AcWing 893题中每堆石子最多10000颗所以M10010是安全的。设置稍大一点是好习惯。sg数组的初始化我们将其初始化为-1表示该状态的SG值尚未计算。memset(sg, -1, sizeof sg);使用unordered_set在计算mex时我们需要临时存储后继状态的SG值集合。使用C STL中的unordered_set比set更快因为我们只关心插入和查找不需要有序。3.2 记忆化搜索函数getSG(int x)这是整个算法的核心函数用于计算石子数为x时的SG值。int getSG(int x) { // 记忆化如果已经计算过直接返回 if (sg[x] ! -1) return sg[x]; // 哈希表用于存储当前状态x的所有后继状态的SG值 unordered_setint S; // 枚举所有可能的操作取走 s[i] 个石子 for (int i 0; i k; i) { int take s[i]; if (x take) { // 确保操作合法 S.insert(getSG(x - take)); // 递归计算后继状态的SG值并插入集合 } } // 计算 mex(S) for (int i 0; ; i) { // 从0开始枚举自然数 if (!S.count(i)) { // 如果i不在集合S中 sg[x] i; // 找到mex赋值并返回 return i; } } }逐行解析与注意事项递归基与记忆化if (sg[x] ! -1) return sg[x];这是记忆化搜索的标准开头避免重复计算将指数级复杂度降为O(M * k)。后继状态枚举for (int i 0; i k; i)遍历取法集合S。这里有一个关键优化点如果集合S是无序的且可能包含重复值可以在读入后对其进行排序去重确保k是有效操作数。不过本题通常保证输入合法但养成好习惯很重要。操作合法性判断if (x take)必须检查不能从一个只有3个石子的堆里取走5个。递归计算getSG(x - take)计算后继状态的SG值。这里体现了动态规划“自顶向下”的思路。mex的计算for (int i 0; ; i)是一个从0开始的无限循环直到找到第一个不在集合S中的i。由于SG值不会太大理论上不超过操作集合大小k这个循环很快。!S.count(i)是unordered_set的查找操作平均O(1)复杂度。一个重要的边界情况如果x小于S中的最小值那么S集合将为空因为没有任何合法操作。循环for (int i 0; i k; i)不会执行任何插入操作unordered_setint S保持为空。接下来的mex计算循环会找到i0因为S.count(0)为false。所以sg[x] 0。这正对应了我们之前分析的SG(1)的情况是必败态。3.3 主函数逻辑与流程主函数负责组织整个计算流程并应用SG定理进行胜负判断。int main() { // 1. 读入取法集合S cin k; for (int i 0; i k; i) cin s[i]; // 2. 初始化SG记忆化数组 memset(sg, -1, sizeof sg); // 3. 读入石子堆信息并计算每堆的SG值 cin n; int res 0; // 用于计算异或和 for (int i 0; i n; i) { int x; cin x; res ^ getSG(x); // 计算并累加异或 } // 4. 根据SG定理判断胜负并输出 if (res) puts(Yes); // 异或和非零先手必胜 else puts(No); // 异或和为零先手必败 return 0; }流程梳理与思考输入与初始化先读k和集合s然后立即初始化sg数组。这个顺序不能乱因为getSG函数依赖全局的s数组。逐堆处理对于每一堆石子x调用getSG(x)获取其SG值并立刻与当前结果res进行异或。这样做的好处是只需要遍历石子堆一次无需额外数组存储所有SG(a_i)。胜负判定res最终保存了所有子游戏SG值的异或和。if (res)利用了C中非零即真的特性。res ! 0等价于res ! 0。4. 复杂度分析与边界情况处理一个健壮的算法实现必须清楚其性能边界和可能遇到的坑。4.1 时间复杂度分析设最大石子数为MaxX对应数组大小M取法集合大小为k石子堆数为n。getSG函数对于每个状态x最多会计算一次。计算它需要遍历k种操作常数时间并对每个合法操作递归计算后继状态已记忆化可视为O(1)。然后计算mex由于SG值范围有限这个循环可视为常数时间通常远小于k。所以计算单个SG(x)的摊还代价是O(k)。总体复杂度我们需要计算从0到MaxX实际上只需要计算输入中出现的x但最坏情况是n堆都不同且都接近MaxX所有可能状态的SG值。因此总时间复杂度为O(MaxX * k n)。在本题限制下MaxX约1e4k约100这个复杂度是完全可接受的。4.2 空间复杂度分析sg数组O(MaxX)。s数组O(k)。递归调用栈最坏深度为MaxX但实际由于记忆化不会出现很深的重复递归。空间复杂度为O(MaxX)递归栈O(MaxX)sg数组 ≈O(MaxX)。4.3 常见边界与陷阱取法集合S包含0或负数题目通常保证s[i]是正整数。如果包含0会导致无限递归x-0x。如果包含负数逻辑上无意义。防御性编程可以在读入后对s数组进行排序和去重并检查元素是否为正整数。石子数x为0我们的getSG(0)会正确返回0。在主循环中res ^ getSG(0)等同于res ^ 0不影响结果。这是符合定义的一堆0个石子的游戏SG值为0必败态。sg数组未初始化务必用-1或其他不可能出现的值初始化sg数组这是记忆化搜索正确工作的前提。我见过有人用0初始化然后误判很多状态已经计算因为SG值可能就是0导致错误。unordered_set的作用域unordered_setint S必须定义在getSG函数内部。每次调用getSG(x)都需要一个新的集合来存储当前x的后继SG值。如果定义为全局变量需要在每次调用前后清理非常容易出错。异或运算的优先级res ^ getSG(x)是安全的。但如果你写成res res ^ getSG(x)也没问题。注意^的优先级低于和!但在赋值表达式中通常没问题。5. 从模板到理解调试与验证策略能写出代码只是第一步能验证其正确性并理解其过程更重要。下面提供几种方法。5.1 小规模数据手动模拟选择一组很小的数据在纸上或心里模拟程序运行。示例设S {2, 3}, 计算SG(0)到SG(5)。SG(0) mex({}) 0SG(1) mex({}) 0(无法取2或3)SG(2) mex({SG(0)}) mex({0}) 1SG(3) mex({SG(0), SG(1)})?等等从3可以取2到1取3到0。所以是mex({SG(1), SG(0)}) mex({0, 0}) mex({0}) 1。SG(4) mex({SG(2), SG(1)}) mex({1, 0}) 2(因为0和1都在集合里最小不在的是2)SG(5) mex({SG(3), SG(2)}) mex({1, 1}) mex({1}) 0然后你可以设计一个两堆的游戏比如两堆分别是(2, 3)。SG(2)^SG(3) 1^1 0先手必败。你可以手动推演一下确实无论先手在第一堆怎么动只能取2变成(0,3)或者第二堆怎么动取2变(2,1)取3变(2,0)后手都能应对并最终获胜。5.2 添加调试输出在getSG函数中加入打印语句观察计算过程。int getSG(int x) { if (sg[x] ! -1) { // cout Memory hit: sg[ x ] sg[x] endl; return sg[x]; } unordered_setint S; for (int i 0; i k; i) { int take s[i]; if (x take) { int next_sg getSG(x - take); // cout From x , take take - x-take (SG next_sg ) endl; S.insert(next_sg); } } // 计算mex for (int i 0; ; i) { if (!S.count(i)) { sg[x] i; // cout Computed: sg[ x ] mex{...} i endl; return i; } } }通过这种输出你可以清晰地看到递归调用的路径、后继状态的SG值以及最终mex的计算结果。这对于理解算法和排查错误非常有帮助。5.3 测试用例设计设计涵盖各种情况的测试用例基础验证S{1}, 任何一堆石子数xSG(x)x。这就是经典Nim。测试(1,2,3)异或和1^2^30应输出No。必败态测试S{2,5}, 单堆x1或x4SG值应为0。多堆时全部选这种SG0的堆异或和为0应输出No。边界测试x0的情况。S中包含大于最大石子数的值的情况。性能测试用最大数据量测试如k100,S中元素随机n100,x接近10000确保不超时。6. 举一反三SG函数应用的扩展场景掌握了集合-Nim这个模板你就拥有了解决一大类公平组合游戏Impartial Combinatorial Games的能力。这类游戏的特点是两人轮流操作操作集合只依赖于当前状态而与玩家无关即“公平”且无法操作者判负。以下是一些变种和扩展思路6.1 操作集合动态变化在集合-Nim中取法集合S是全局固定的。但有些题目中S可能依赖于当前石子数x。例如每次可以取1到floor(x/2)个石子。这时你只需要修改getSG函数中枚举后继状态的部分for (int take 1; take x / 2; take) { // 操作集合变为1到x/2 S.insert(getSG(x - take)); }算法的核心框架记忆化搜索 mex计算完全不变。6.2 多维度状态与拆分游戏有些游戏的状态不是单一数字。例如有一个n*m的棋盘每次可以拿走一个格子及其右方和下方的所有格子。这个游戏可以看作是多个独立的“行”游戏和“列”游戏的组合吗不一定。但更通用的方法是将整个棋盘状态(i,j)作为一个节点计算其SG值。这可能需要二维甚至更高维度的记忆化数组。更常见的一种强大技巧是游戏拆分。如果一个大游戏可以看成是几个完全独立的子游戏同时进行那么整个游戏的SG值就是各子游戏SG值的异或和。这就是SG定理的直接应用。很多看似复杂的游戏经过巧妙分析可以被拆分成独立的Nim堆。6.3 非DAG的博弈无限递归SG函数和记忆化搜索的前提是游戏图是一个有向无环图DAG即游戏总能在有限步内结束。如果游戏有可能陷入循环例如某些棋类游戏标准的SG函数方法就失效了需要更复杂的分析如和棋规则、无限循环判负等。在算法竞赛中题目通常会保证局面是DAG。6.4 从“胜负”到“方案”SG函数通常只告诉我们当前局面是必胜还是必败。但有时题目还要求如果必胜请输出一种必胜操作。这该如何做在计算出整体异或和res后如果res ! 0我们知道先手必胜。要找到一种操作其实就是找到一堆石子a_i对其进行一次合法操作后使得新的异或和变为0。假设我们对第i堆操作取走t个石子t属于S且t a_i。操作后该堆石子数变为a_i - t其SG值变为SG(a_i - t)。我们希望操作后所有堆的SG值异或和为0即(res ^ SG(a_i) ^ SG(a_i - t)) 0这等价于SG(a_i - t) res ^ SG(a_i)所以寻找必胜操作的算法是遍历每一堆石子i。计算target res ^ SG(a_i)。target的含义是为了使得总异或和为0操作后第i堆的SG值需要等于target。遍历所有合法操作t属于S且t a_i计算new_sg SG(a_i - t)。如果存在某个t使得new_sg target那么这就是一个必胜操作。输出i和t即可。这个思路完美体现了SG函数的威力它不仅判断胜负还能指导我们如何行动。7. 总结与个人心得回顾整个“集合-Nim游戏”的解题过程其核心脉络非常清晰定义状态 - 计算单状态SG值记忆化搜索mex - 多状态组合求异或和 - 根据异或和判断胜负。这几乎是一个可以解决所有公平组合游戏问题的标准框架。我在最初学习时曾纠结于mex函数为什么这样定义。后来想明白了它本质上是一种递归的、逆向的必胜/必败态分析。SG(x)0意味着所有后继都是“非零”必胜态所以当前是必败态。SG(x)0意味着存在一个后继是“零”必败态所以当前是必胜态。mex操作是保证这种0/非0性质递推下去的最简洁数学表达。在实现上最大的坑就是记忆化数组的初始化和**unordered_set的局部作用域**。我强烈建议在开始写记忆化搜索时就把if (sg[x] ! -1) return sg[x];和unordered_setint S;作为固定模板写下来。最后不要满足于套模板AC题目。多用手算小数据理解SG值是如何一步步产生的。尝试修改题目条件比如改变操作集合S的规则自己设计测试用例验证。当你能够不假思索地写出getSG函数并且能向别人解释清楚为什么异或和能决定胜负时你才算真正掌握了这把博弈论的利器。这道题在AcWing上标为“简单”但它的思想一点也不简单。吃透它很多复杂的博弈题在你眼里都会变成纸老虎。
![2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符]](http://pic.xiahunao.cn/yaotu/2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符])
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
