1. 从两堆石子说起这个博弈问题到底在考什么第一次看到“取(2堆)石子游戏”这个标题很多人会以为它只是普通的尼姆博弈换个皮。实际上两堆石子的取子规则和标准尼姆博弈有本质区别它更接近威佐夫博弈的变体但又在取子方式上做了限制。我当初做这道题的时候卡了很久才想明白状态转移的真正结构这里把完整的分析思路和实现细节整理出来希望能帮你少走弯路。这个问题的核心是有两堆石子数量分别为a和b两个玩家轮流取子。取子规则通常有两种从其中一堆取走任意正数颗或者从两堆中同时取走相同数量的石子。取走最后一颗石子的人获胜。给定初始状态问先手是否必胜如果必胜输出所有能让先手一步走到必败态的取法。它解决的是一个典型的组合博弈论问题适合已经掌握基础博弈论如巴什博弈、尼姆博弈并想进一步理解“必败态构造”和“状态转移枚举”的读者。无论你是刚接触算法竞赛的新手还是想复习博弈论的老手这个问题的分析过程都很有参考价值因为它把“找规律”和“严格证明”结合得非常紧密。我个人的体会是这道题最大的价值不在于结论本身而在于它训练你如何从少量状态推出全局规律再用数学工具验证规律最后把规律转化成可枚举的代码。这套方法论在绝大多数博弈论题目里都通用。2. 必败态的规律是怎么找出来的2.1 先手写几组小数据观察拿到这种题最忌讳一上来就推公式。我的习惯是先把小规模的状态全部列出来手动判断每个状态是必胜还是必败。设状态为(a, b)且a ≤ b我们从小到大枚举(0, 0)终局轮到谁谁输是必败态。(0, k) k0只能从第二堆取取完就赢必胜态。(1, 1)可以两堆各取1直接取完必胜态。(1, 2)试试所有取法。取第一堆1颗→(0,2)必胜态给对手取第二堆1颗→(1,1)必胜态取第二堆2颗→(1,0)必胜态两堆各取1→(0,1)必胜态。所有后继都是必胜态所以(1,2)是必败态。(1, 3)取第二堆1颗→(1,2)必败态给对手所以必胜。(2, 2)两堆各取2直接赢必胜。(3, 5)这个需要仔细验证它也是必败态。继续往下推必败态序列是(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), (11,18), (12,20)...2.2 必败态的三个关键性质观察这组数据能总结出必败态(a, b)满足的性质第一差值递增且不重复。每个必败态的b - a分别是0, 1, 2, 3, 4, 5, 6, 7, 8...恰好覆盖所有非负整数且每个差值只出现一次。第二每个正整数恰好出现在一个必败态中。0到20之间的每个整数要么作为某个必败态的a要么作为某个必败态的b不会重复也不会遗漏。这个性质叫“划分性质”。第三a的取值是前面所有必败态中未出现过的最小非负整数。比如(3,5)里的3是因为0,1,2已经被(0,0),(1,2)用掉了最小可用就是3。这三条性质合起来就是威佐夫博弈必败态的经典刻画。但要注意本题的取子规则如果和标准威佐夫博弈完全一致那结论就是现成的如果规则有差异比如只能从两堆取相同数量不能从单堆取必败态序列会完全不同。所以做题第一步永远是确认取子规则这是最容易翻车的地方。2.3 为什么这个规律成立光找到规律不够得能说清楚为什么。我用反证法梳理一遍假设必败态序列按上述规则构造。对于任意一个状态(a, b)如果它不在必败态序列里那么要么a是某个必败态的b要么b是某个必败态的b要么a和b分别是两个必败态的成员。无论哪种情况都能通过一次合法取子走到某个必败态所以它是必胜态。反过来如果(a, b)在必败态序列里它的任何后继状态都不可能还是必败态因为必败态之间不能互相到达否则先手可以一步走到必败态矛盾。所以必败态的所有后继都是必胜态它本身必败。这个证明的关键在于必败态集合的构造方式保证了“互不可达”和“全覆盖”。理解了这一点你就能自己推导变体规则的必败态而不是死记公式。3. 从规律到代码怎么枚举所有必胜取法3.1 判断先手胜负给定初始状态(a, b)先判断它是不是必败态。如果是先手必败直接输出0。如果不是先手必胜需要输出所有能走到必败态的取法。判断方法有两种。一种是直接生成必败态序列看(a, b)是否在其中。由于a和b的范围通常不大这类题一般a, b ≤ 1000或10000可以预处理出所有必败态存起来查询时O(1)判断。另一种是用公式。标准威佐夫博弈的必败态满足a floor(k × φ)b a k其中φ (1 √5) / 2 ≈ 1.618k b - a。验证一下k1时a floor(1.618) 1b 2对应(1,2)k2时a floor(3.236) 3b 5对应(3,5)。完全吻合。用公式判断的好处是不用预处理直接算。但要注意浮点精度问题k较大时floor可能算错稳妥做法是用整数运算或者加一个小的epsilon修正。我一般用(int)(k * phi)然后检查前后几个值确保不漏。3.2 枚举所有合法取法如果先手必胜需要找出所有一步能走到必败态的取法。取法分两类第一类从其中一堆取。假设从第一堆取取完后状态变成(a, b)其中0 ≤ a a。要求(a, b)是必败态。由于b固定我们只需要检查b是否等于某个必败态的b且那个必败态的a小于当前a。如果满足就记录一种取法从第一堆取a - a颗。同理从第二堆取时a固定检查a是否等于某个必败态的a且那个必败态的b小于当前b。第二类从两堆同时取相同数量。取完后状态变成(a - t, b - t)其中t 0且t ≤ a。要求(a - t, b - t)是必败态。由于两堆差值b - a不变我们只需要找差值为b - a的那个必败态看它的a是否小于当前a。如果满足t a - a记录取法。这里有个细节如果当前状态本身就是必败态那它没有后继必败态直接输出0。如果当前状态是必胜态它至少有一个后继必败态枚举时不会漏。3.3 输出格式与排序题目通常要求按某种顺序输出所有取法比如先输出从第一堆取的再输出从第二堆取的最后输出从两堆同时取的或者按取子数量排序。我踩过的坑是输出顺序不对导致判错虽然答案内容正确但格式不匹配。稳妥做法是把所有取法存成一个列表每个元素记录(取第一堆数量, 取第二堆数量)然后按题目要求的顺序排序输出。如果题目没明确要求一般按第一堆取的数量升序再按第二堆取的数量升序。另外注意如果某种取法取完后两堆都变成0那也是一种合法取法直接取完获胜不要漏掉。4. 完整实现与关键代码解析4.1 预处理必败态序列def generate_losing_states(max_val): losing [] used [False] * (max_val * 2 1) k 0 while True: # 找最小的未使用的非负整数作为a a 0 while used[a]: a 1 b a k if b max_val: break losing.append((a, b)) used[a] True used[b] True k 1 return losing这段代码的核心是used数组它标记了哪些整数已经被必败态占用。每次找最小的未使用整数作为a然后b a kk从0开始递增。这样生成的序列天然满足前面说的三条性质。注意max_val的选取如果题目给定a, b ≤ N那必败态的b最大不会超过N 某个值取2N足够安全。我一般直接开2N 10的数组避免越界。4.2 判断与枚举def solve(a, b): if a b: a, b b, a losing generate_losing_states(b) losing_set set(losing) if (a, b) in losing_set: return [] # 先手必败 results [] # 从第一堆取 for (x, y) in losing: if y b and x a: results.append((a - x, 0)) # 从第二堆取 for (x, y) in losing: if x a and y b: results.append((0, b - y)) # 从两堆同时取 diff b - a for (x, y) in losing: if y - x diff and x a: t a - x results.append((t, t)) # 去重并排序 results sorted(set(results)) return results这段代码逻辑清晰但有几个容易出错的地方。第一losing序列的生成范围要覆盖到b否则可能漏掉某些必败态。第二从两堆同时取时差值diff必须精确匹配因为两堆同时取不改变差值。第三结果要去重因为某些取法可能被多次记录虽然理论上不会但保险起见。4.3 复杂度分析预处理必败态的时间复杂度是O(N)其中N是b的最大值。枚举取法时最坏情况要遍历所有必败态也是O(N)。所以整体复杂度O(N)对于N ≤ 10000的题目完全够用。如果N很大比如10^9就不能预处理了必须用公式直接算。这时候判断必败态用a floor(k * phi)枚举取法时只需要检查少数几个候选必败态复杂度降到O(1)。但公式法有精度风险需要小心处理。5. 常见问题与排查技巧实录5.1 为什么我的答案总是少几种取法这是最常见的问题。原因通常有三个一是必败态序列生成不完整比如max_val开小了二是枚举时只考虑了从单堆取漏了两堆同时取三是判断条件写错比如把x a写成了x a导致把当前状态自己也算进去了。排查方法手动构造几个小状态比如(1, 2)是必败态直接输出0(1, 3)是必胜态应该输出从第二堆取1颗这一种取法。如果连这个小例子都过不了说明基础逻辑有问题。5.2 浮点精度导致的误判用公式法判断必败态时k * phi在k较大时可能因为浮点误差导致floor结果偏小1。比如k1000时理论值可能是1618.033但浮点算出来是1617.999floor后变成1617少1。解决办法算完a int(k * phi)后检查a1和a-1是否也满足条件取真正满足的那个。或者直接用整数运算用连分数逼近phi但实现复杂。我一般用a int(k * phi 1e-9)加一个小的epsilon修正。5.3 输出格式不对有些题目要求输出取法的数量有些要求输出具体取法有些要求按特定顺序。我遇到过一道题要求“如果有多种取法按从第一堆取的数量从小到大输出如果相同则按从第二堆取的数量从小到大”结果我没排序直接输出判错。建议写完代码后先自己造几组数据手动算一遍期望输出再和程序输出对比。特别是输出顺序一定要和题目要求一致。5.4 边界情况处理边界情况包括a0或b0aba和b都很大。a0时如果b0先手直接从第二堆取完获胜输出一种取法(0, b)。ab时如果a0先手两堆各取a直接获胜输出一种取法(a, a)。这些情况容易被忽略但测试数据里往往有。还有一个隐藏边界如果初始状态就是(0, 0)那先手无子可取必败输出0。这个也要处理。5.5 常见问题速查表问题现象可能原因排查方法答案少几种取法必败态序列不完整检查max_val是否够大答案多几种取法判断条件用了改为严格小于浮点判断出错精度不够加epsilon或改用整数输出顺序不对没排序按题目要求排序边界情况漏判没处理a0或ab单独处理这些情况运行超时预处理范围过大改用公式法或缩小范围6. 从这道题能学到什么通用方法这道题表面上是博弈论实际上训练的是从数据中找规律、用数学证明规律、把规律转化成代码的完整链路。我做完之后最大的收获不是记住了威佐夫博弈的公式而是学会了怎么系统地分析一个陌生博弈问题。具体来说遇到新的博弈题我会按这个流程走第一步明确规则特别是取子方式和胜负判定第二步手写小规模状态标出必胜必败第三步观察必败态的分布规律尝试用差值、最小值、划分性质等角度描述第四步用反证法或归纳法证明规律第五步设计枚举算法注意边界和输出格式。这套方法在尼姆博弈、巴什博弈、斐波那契博弈等经典问题里都适用。甚至在一些非博弈的动态规划问题里找状态转移规律也是类似的思路。另外这道题还提醒我不要迷信公式。很多人一看到两堆石子就套威佐夫公式但如果题目规则改了比如只能从两堆取相同数量不能从单堆取公式就完全失效了。真正可靠的是自己推导一遍理解必败态的本质结构。最后分享一个小技巧如果你在比赛里遇到这类题时间紧张来不及严格证明可以先写个暴力程序打表把必败态序列打出来然后观察规律。很多时候规律很明显直接套用就能过。但赛后一定要补上证明否则下次换个变体你又不会了。