企业官网建设流程全解析

1. 从两堆石子说起：这个博弈问题到底在考什么

第一次看到“取(2堆)石子游戏”这个标题，很多人会以为它只是普通的尼姆博弈换个皮。实际上，两堆石子的取子规则和标准尼姆博弈有本质区别，它更接近威佐夫博弈的变体，但又在取子方式上做了限制。我当初做这道题的时候，卡了很久才想明白状态转移的真正结构，这里把完整的分析思路和实现细节整理出来，希望能帮你少走弯路。

这个问题的核心是：有两堆石子，数量分别为a和b，两个玩家轮流取子。取子规则通常有两种：从其中一堆取走任意正数颗，或者从两堆中同时取走相同数量的石子。取走最后一颗石子的人获胜。给定初始状态，问先手是否必胜；如果必胜，输出所有能让先手一步走到必败态的取法。

它解决的是一个典型的组合博弈论问题，适合已经掌握基础博弈论（如巴什博弈、尼姆博弈）并想进一步理解“必败态构造”和“状态转移枚举”的读者。无论你是刚接触算法竞赛的新手，还是想复习博弈论的老手，这个问题的分析过程都很有参考价值，因为它把“找规律”和“严格证明”结合得非常紧密。

我个人的体会是，这道题最大的价值不在于结论本身，而在于它训练你如何从少量状态推出全局规律，再用数学工具验证规律，最后把规律转化成可枚举的代码。这套方法论在绝大多数博弈论题目里都通用。

2. 必败态的规律是怎么找出来的

2.1 先手写几组小数据观察

拿到这种题，最忌讳一上来就推公式。我的习惯是先把小规模的状态全部列出来，手动判断每个状态是必胜还是必败。设状态为(a, b)，且a ≤ b，我们从小到大枚举：

• (0, 0)：终局，轮到谁谁输，是必败态。
• (0, k) k>0：只能从第二堆取，取完就赢，必胜态。
• (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.618，k = b - a。验证一下：k=1时a = floor(1.618) = 1，b = 2，对应(1,2)；k=2时a = floor(3.236) = 3，b = 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 + k，k从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。比如k=1000时，理论值可能是1618.033，但浮点算出来是1617.999，floor后变成1617，少1。

解决办法：算完a = int(k * phi)后，检查a+1和a-1是否也满足条件，取真正满足的那个。或者直接用整数运算，用连分数逼近phi，但实现复杂。我一般用a = int(k * phi + 1e-9)，加一个小的epsilon修正。

5.3 输出格式不对

有些题目要求输出取法的数量，有些要求输出具体取法，有些要求按特定顺序。我遇到过一道题要求“如果有多种取法，按从第一堆取的数量从小到大输出，如果相同则按从第二堆取的数量从小到大”，结果我没排序直接输出，判错。

建议：写完代码后，先自己造几组数据，手动算一遍期望输出，再和程序输出对比。特别是输出顺序，一定要和题目要求一致。

5.4 边界情况处理

边界情况包括：a=0或b=0，a=b，a和b都很大。a=0时，如果b>0，先手直接从第二堆取完获胜，输出一种取法(0, b)。a=b时，如果a>0，先手两堆各取a直接获胜，输出一种取法(a, a)。这些情况容易被忽略，但测试数据里往往有。

还有一个隐藏边界：如果初始状态就是(0, 0)，那先手无子可取，必败，输出0。这个也要处理。

5.5 常见问题速查表

6. 从这道题能学到什么通用方法

这道题表面上是博弈论，实际上训练的是从数据中找规律、用数学证明规律、把规律转化成代码的完整链路。我做完之后最大的收获不是记住了威佐夫博弈的公式，而是学会了怎么系统地分析一个陌生博弈问题。

具体来说，遇到新的博弈题，我会按这个流程走：第一步，明确规则，特别是取子方式和胜负判定；第二步，手写小规模状态，标出必胜必败；第三步，观察必败态的分布规律，尝试用差值、最小值、划分性质等角度描述；第四步，用反证法或归纳法证明规律；第五步，设计枚举算法，注意边界和输出格式。

这套方法在尼姆博弈、巴什博弈、斐波那契博弈等经典问题里都适用。甚至在一些非博弈的动态规划问题里，找状态转移规律也是类似的思路。

另外，这道题还提醒我不要迷信公式。很多人一看到两堆石子就套威佐夫公式，但如果题目规则改了（比如只能从两堆取相同数量，不能从单堆取），公式就完全失效了。真正可靠的是自己推导一遍，理解必败态的本质结构。

最后分享一个小技巧：如果你在比赛里遇到这类题，时间紧张来不及严格证明，可以先写个暴力程序打表，把必败态序列打出来，然后观察规律。很多时候规律很明显，直接套用就能过。但赛后一定要补上证明，否则下次换个变体你又不会了。