企业官网建设流程全解析

如果你刚接触博弈论，大概见过这种场面：某篇题解甩出三行代码，说“把所有堆的火柴数异或一下，结果是 0 先手必败，否则先手必胜”，然后就没有然后了。洛谷 P1247：取火柴游戏正好卡在这个位置的后一格——它不仅要你判断先手能不能赢，还要求先手必胜时输出“第一步究竟怎么取”。很多初学者第一反应是“这有什么难的”，真到自己动手构造方案时才发现，找那一堆火柴、算那一个数字，远比想象中容易翻车。

这篇博文就围绕这道题的完整链路来讲：Nim 博弈的胜负判定原理、必胜第一步的推导构造、P1247 的 C++ 实现，以及我在提交过程中实际踩过的几个坑。适合刚接触博弈论、想搞懂“为什么异或”而不是背结论的读者，也适合准备竞赛的选手拿来做模板题复盘。我尽量把每一步的“为什么”都讲透，不给你留那种“代码过了但心里发虚”的感觉。

1. P1247 题目速读：规则、输入输出和那道隐藏的附加题

1.1 游戏规则与输入输出格式

取火柴游戏的规则其实很简单：有 n 堆火柴，每堆有若干根。两名玩家轮流行动，每次必须选择其中一堆，从这一堆里取走至少一根火柴，可以取到整堆拿光。谁取走最后一根火柴，谁就获胜；换句话说，轮到谁走但无火柴可取，谁就输了。

P1247 的输入格式是第一行一个整数 n，第二行 n 个整数，表示每堆火柴的数量。输出分两种情况：

• 如果先手必败，输出一行lose。
• 如果先手必胜，输出两行：第一行是两个整数a b，表示在第 a 堆取走 b 根火柴；第二行输出取完这一步之后，n 堆火柴各自的剩余数量。

我举个例子方便后面验证。假设输入是：

3 3 5 7

三堆分别是 3、5、7。这个局面先手必胜，第一步可以有很多种合法走法，比如在第 1 堆取走 1 根，局面变成 2、5、7。那么输出就是：

1 1 2 5 7

这里第一行的1 1表示“在第 1 堆取走 1 根”，第二行是对应取完后的局面。需要注意，第二行输出的是完整局面，不是取走的数目。

1.2 这道题真正的考点：把必胜态变成具体走法

如果你去搜各种题解，会发现纯 Nim 博弈的判定题到处都是：给你一个局面，问先手胜还是负，解法就是求一次异或。P1247 比这类题多走了一步：它要求你构造出必胜局面下的“第一步走法”。

这一步看着不难，实际上卡住过很多人。原因在于，异或判定的结论只告诉你能不能赢，没有告诉你怎么赢。很多人背熟了“异或为 0 必败”，遇到输出方案就不知道怎么办，只能随便拿一堆，或者干脆拿最大的一堆碰运气，结果交上去就 WA。

这道题的完整做题思路其实分两部分：先用异或判断方向，再用异或反向构造方案。判断方向是定理，构造方案是定理的推论，两者用的是同一个数学结构，只是你会不会把式子反过来算的问题。接下来的两章，我把这两部分分开讲。

2. Nim 胜负判定定理：为什么“异或为 0”代表先手必败

2.1 从终局状态往前看：异或像是局面的“指纹”

先给结论：设所有堆的火柴数为 a1, a2, ..., an，求它们的按位异或

s = a1 ^ a2 ^ ... ^ an

如果 s = 0，则先手必败；如果 s ≠ 0，则先手必胜。这个结论适用于“取完最后一根的人赢”的正常规则。

我第一次看到这个结论时，觉得“异或为 0”和“游戏胜负”这两件事好像八竿子打不着，凭什么用按位异或？后来换个角度才顺过来：异或不是用来算一堆火柴的，而是用来描述整个局面的状态。

先看终局：所有堆都是 0，异或自然是 0。但“异或为 0”不等于终局，比如两堆都是 7，7 ^ 7 = 0，可是这个局面还有很多火柴可以拿。所以异或为 0 是一个比“终局”更广的概念。要让“异或为 0 必败”成立，必须证明两条关键性质：

1. 异或为 0 的局面，无论你怎么走一步，走完后的异或一定不为 0。
2. 异或不为 0 的局面，一定存在至少一种走法，走完后的异或变回 0。

这两条性质合在一起，就把所有局面分成了两类：一类是“谁走到这个状态，谁就能把 0 交给对方”，另一类是“谁走到这个状态，谁就只能把非 0 还给对方”。胜负就藏在这两类状态的交替里。

2.2 性质 A：异或 0 走一步，必成异或非 0

假设当前局面异或 s = 0。某位玩家选择第 i 堆，把这堆火柴数从 x 变成 y，规则要求 0 ≤ y < x（必须至少取走一根）。走完之后，全局异或变成多少？

原来所有堆的异或是 s，现在只有第 i 堆从 x 变成了 y，所以新的异或 s' 等于原来的 s 去掉 x 的影响、再加上 y 的影响，即：

s' = s ^ x ^ y

因为 s = 0，所以 s' = x ^ y。这里有个关键点：x 和 y 是两个不同的数，因为 y < x 是规则强制要求的，不可能等于 x。两个不同的数异或，结果不可能为 0。可以这样理解：按位异或只有在两个数每一位都相同时才等于 0，而两个不同的数不可能每一位都相同。

所以结论就出来了：从异或为 0 的局面出发，无论怎么走，新局面的异或一定非 0。这个性质很“坏”——你没办法在一步之内从 0 走到 0，等于说“保持平衡”这件事在一步之内是做不到的。

2.3 性质 B：异或非 0 一定存在一步走到异或 0

假设当前局面异或 s ≠ 0。要证明存在一个合法走法能把局面异或变成 0。

设 s 的最高位是第 k 位，也就是二进制中最高位的那个 1。因为 s 的第 k 位是 1，说明所有堆在该位的异或结果为 1，参与异或的数在第 k 位上有奇数个 1。至少存在一堆火柴数 x，它在第 k 位也是 1。这一步存在的关键是找到这一堆。

令 y = x ^ s。我们来比较 x 和 y 的大小。y 在第 k 位的值：x 的第 k 位是 1，s 的第 k 位是 1，异或后第 k 位变成 0。而 s 在第 k 位以上的所有位都是 0，所以 y 在第 k 位以上的位和 x 完全相同。也就是说，y 在最高位以上的部分没变，但第 k 位从 1 变成了 0，所以 y 的数值一定小于 x。

既然 y < x，那“把第 i 堆从 x 变成 y”就是一个合法走法（取走 x - y 根）。走完之后的全局异或是多少？

s' = s ^ x ^ y = s ^ x ^ (x ^ s) = 0

刚刚好归零。而且我再强调一句：满足这个条件的堆不一定只有一堆，但至少存在一堆，定理保证了这一点。找的时候逐个枚举就行。

2.4 把两条性质拼起来：为什么必败态是 0

把 A、B 两条性质合起来看，胜负逻辑就完整了：

• 面对异或为 0 的局面，你不得不把它走成非 0。
• 面对非 0 的局面，你的对手一定能找到一种走法，把它走回 0。

于是整个游戏就像一场“谁先破坏平衡”的游戏。先手若遇到 s = 0，无论走哪一步，都会把一个非 0 局面交给对手；对手利用性质 B 一步归零，又还给先手一个 0。如此循环，每次轮到先手面对的都是 0，而火柴总数在减少，最终先手会面对全 0 的终局，无路可走，必败。

反过来，先手若遇到 s ≠ 0，第一步就能归零，把 0 交给对手，让对手陷入上面说的恶性循环。所以胜负判定结论可以收进一张表：

提示：这个推导适用于“取到最后一根者胜”的正常规则。如果规则改成“取到最后一根者输”，结论会有变化，后面扩展部分我会提一句。

3. 必胜第一步怎么构造：从“异或归零”反推出具体拿法

3.1 核心方程：第 i 堆要变成的值是多少

现在进入 P1247 真正要考的环节：已知 s ≠ 0，先手必胜，要求输出第一步怎么拿。

选一堆，把这堆从 x 变成 y，要满足两个条件：

• 新局面异或为 0，也就是 s ^ x ^ y = 0。
• 这是合法走法，也就是 y < x。

由第一个式子直接解出来：

y = s ^ x

这里我多说一句，为什么不是别的式子。因为全局异或的破坏只有这一堆引起，原异或是 s，新异或就是把 s 里的 x 置换为 y，所以新异或 = s ^ x ^ y。要让新异或为零，y 必须恰好等于 s ^ x。这个式子是从“归零”目标反推出来的，不是拍脑袋。

第二个条件更重要：y < x。如果算出来的 y 不小于 x，说明这个“归零方案”在该堆上不可执行。你不能把一堆从 3 根变成 5 根，那不符合游戏规则。所以判断条件是：

if ((a[i] ^ s) < a[i]) 合法，输出方案

为什么一定存在至少一堆满足这个条件？这就是上一章性质 B 的内容：s ≠ 0 时，取 s 的最高位，一定存在某堆在这一位为 1，而这一堆算出来的 y 必然小于 x。所以遍历所有堆，一旦找到满足条件的堆，就可以直接停止。

3.2 手算一个例子：3、5、7

我们用前面那个例子演算一遍。三堆是 3、5、7：

3 的二进制是 011，5 是 101，7 是 111。异或：

s = 3 ^ 5 ^ 7 = 1

s 不为 0，先手必胜。现在逐个检查堆：

• 第 1 堆 x = 3，y = 3 ^ 1 = 2，2 < 3，合法。取走 3 - 2 = 1 根，新局面是 2、5、7。
• 第 2 堆 x = 5，y = 5 ^ 1 = 4，4 < 5，合法。取走 5 - 4 = 1 根，新局面是 3、4、7。
• 第 3 堆 x = 7，y = 7 ^ 1 = 6，6 < 7，合法。取走 7 - 6 = 1 根，新局面是 3、5、6。

三种都可以，随便选一种输出，判题都会接受。验证一下：2 ^ 5 ^ 7 = 0，3 ^ 4 ^ 7 = 0，3 ^ 5 ^ 6 = 0，全都归零。

我把三种方案列成表格：

从这个例子也能感受到，输出方案不唯一，判题只看你输出的走法是不是合法，以及走完之后的局面是否正确。

3.3 反直觉的地方：贪心拿最多不一定对

很多新手遇到“先手必胜输出方案”时，第一反应是“拿最多的一堆，或者把某一堆拿光”。这个直觉在不少游戏里成立，但在 Nim 博弈里非常危险。

看一个经典必败局面：1、2、3。异或 1 ^ 2 ^ 3 = 0，先手必败。如果你强行拿最大堆 3：拿 2 根变成 1，新局面 1、2、1 的异或是 1，对手可以一步归零；直接拿光 3，新局面 1、2、0 的异或是 3，对手同样可以一步归零。你会发现不管怎么拿，都会留一个非 0 局面给对手，对手永远有办法把 0 还给你。

再看一个必胜局面：4、6、8。异或 4 ^ 6 ^ 8 = 10，非 0。逐堆检查：

• 第 1 堆 4：y = 4 ^ 10 = 14，14 > 4，不合法。
• 第 2 堆 6：y = 6 ^ 10 = 12，12 > 6，不合法。
• 第 3 堆 8：y = 8 ^ 10 = 2，2 < 8，合法。

这个局面里，唯一的必胜走法是把第 3 堆从 8 根变成 2 根，取走 6 根。如果你觉得“拿最多那堆肯定没问题”，结果拿 8 里的任何其他数量，都会把非 0 局面留给对手。这说明 Nim 博弈的胜负不取决于“谁拿得多”，而取决于“谁走完之后让异或归零”。一个胜势局面里，合法的归零走法可能只有一种，蒙是蒙不中的。

注意：判断合法性的唯一标准就是(a[i] ^ s) < a[i]，不要掺杂任何“应该拿少的”“应该拿多的”之类的想法。这个条件能成立，本质上是性质 B 给的保证。

4. P1247 的 C++ 实现：核心循环只有四五行

4.1 读入、求异或、判断必败

代码结构不复杂，先读入所有堆，同时求出全局异或 s。如果 s == 0，直接输出lose并结束。很多人在这一步掉以轻心，其实这是最简单的一步。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n + 1); int s = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; s ^= a[i]; } if (s == 0) { cout << "lose\n"; return 0; } // 必胜局面的方案构造 for (int i = 1; i <= n; i++) { int t = a[i] ^ s; // 这堆应该变成的数量 if (t < a[i]) { // 只有变少了才是合法走法 cout << i << ' ' << a[i] - t << '\n'; // 第 i 堆取走 a[i]-t 根 a[i] = t; // 更新局面 break; } } for (int i = 1; i <= n; i++) { if (i > 1) cout << ' '; cout << a[i]; } cout << '\n'; return 0; }

4.2 核心循环的每行代码在干什么

我分开解释这个循环。t = a[i] ^ s是套用上一章的方程 y = x ^ s，它表示“如果我要在这一堆上实现归零，那么这一堆必须变成 t”。这个数字有可能是比原来大，也有可能比原来小。只有当 t < a[i] 时，才意味着操作是“取走若干根”而不是“凭空变多”，才符合游戏规则。

输出行里的a[i] - t是取走的根数。比如原始 3 根，t 是 2，那么取走 1 根。更新a[i] = t是为了让第二行输出的是走完后的局面。break是为了只输出一个方案，找到第一个合法堆就可以停手。如果漏掉 break，后面的更新会一直跑下去，第二行输出就会错乱。

整个算法的时间复杂度是 O(n)，空间复杂度 O(n)。读入一次异或，遍历一次找方案，输出一次，常数非常小。比赛里这道题完全不需要担心性能，重点是把逻辑写对。

4.3 一个必须确认的细节：第一行输出“取走数”还是“剩余数”

P1247 的题面要求第一行输出的是“第 a 堆取走 b 根”，对应代码里的a[i] - t。但有些类似的题目，比如部分 OJ 上的改编题，会要求第一行输出“第 a 堆剩余多少根”，也就是直接输出 t。这两种写法很容易混淆，如果按记忆乱写，样例都过不了。

我通常在写这类题时先看输入输出样例：如果样例第二行的局面里，某一堆的数字减少了，第一行的数字正好等于减少量，那说明第一行是取走数；如果第一行的数字和某个堆变化后的数量一致，那第一行就是剩余数。养成这个习惯，可以规避很多“题面阅读”问题。

P1247 是取走数，所以上面代码里输出a[i] - t。你做题时见到其他类似题目，先按样例判断，不要想当然。

4.4 边界情况：只有一堆的时候也能正常跑吗

只有一个堆，比如 n = 1, a[1] = 5。此时 s = 5，遍历到第 1 堆：t = 5 ^ 5 = 0，0 < 5 合法。输出第一行“1 5”，表示取走 5 根；a[1] 更新为 0；第二行输出 0。这正好符合直觉：只有一堆肯定能一次拿光，拿光就赢了。所以代码不需要为 n = 1 做任何特殊处理，只要循环逻辑正确，边界情况自动覆盖。

还有一个容易忽略的边界：如果某堆本来就是 0，也就是输入里存在空堆。t = 0 ^ s = s，一般不会小于 0，所以空堆不会被选中，逻辑上也不用特判。不过实际题目数据里通常不会故意给空堆，这里提一句让你放心。

5. 我在这道题上翻过的车：三次 WA 的完整排查链路

5.1 第一次 WA：贪心拿最多，样例都过不了

我第一次做这道题时，还没完全理解构造原理，想着“先手必胜那不就是随便拿吗”，于是挑最大的一堆直接拿光。拿 3、5、7 举例，我把 7 全拿光，输出“3 7”，局面变成 3、5、0。结果自己验算：3 ^ 5 ^ 0 = 6，非 0，等于把一个必胜局面白白送给了对方。

这不是玄学，而是必败局面 1、2、3 里最典型的教训：拿光最大堆，往往会把一个非 0 局面交给对手，对手一步就能归零，然后反过来制你于死地。

排查思路：拿纸笔验算每个候选走法。你把所有合法走法枚举一遍，看新异或是否为 0，很快就明白“拿最多”的直觉在这里不适用。与其猜，不如老老实实套t = a[i] ^ s的公式。

5.2 第二次 WA：输出变成了负数，因为没有判断 t < a[i]

后来我知道了公式，但在代码里偷懒，找到第一堆就输出，没判断 t 是否小于 a[i]。在 4、6、8 这个例子上，第一堆 a[1] = 4，s = 10，t = 4 ^ 10 = 14，取走数为 4 - 14 = -10。输出一个负数，显然非法。

这类错误在编译器眼里是合法的，int 可以存负数，只有跑起来才露馅。如果你提交后 WA，可以自己造几个手工算过的数据，把中间变量全部打印出来，立刻就能看到 t 比 a[i] 大的情况。修复方法就是先判断后输出，这就是核心循环里那行if (t < a[i])的意义。

5.3 第三次 WA：C++ 运算符优先级悄悄坑人

我之前写过一个很隐蔽的 bug：

if (a[i] ^ s < a[i]) { // 看起来没问题？ }

这个写法是有问题的。C++ 里^的优先级比<低，所以a[i] ^ s < a[i]会被解析成a[i] ^ (s < a[i])，先比较 s 和 a[i] 得到一个布尔值，再把这个布尔值拿来和 a[i] 异或。这种代码编译不会报错，行为却完全不是你想要的，debug 时非常痛苦。

排查思路：如果某一步的结果时好时坏，优先检查有没有依赖运算符优先级的表达式。建议把中间结果单独存变量，像我上面代码那样先写int t = a[i] ^ s;，再判断if (t < a[i])，既清晰又安全。这个习惯能帮你避开一整类 C++ 的隐蔽坑，不止这一道题。

5.4 提交前需要跑一遍的自测样例

这道题输出方案不唯一，自己验证起来反而简单：第一行走法必须合法，第二行局面和第一行对应，且新局面异或必为 0。我把常用的自测样例整理成表：

我每次写完这种博弈题，都会把这几个样例跑一遍再交。特别是 4、6、8 这一组，能有效区分“真的理解了构造”和“只会背异或结论”。

6. 从 NIm 继续往外走：SG 函数和几个常见变形

前面几章把 P1247 这题吃透了。但博弈论的世界不会停在 Nim 这一道题上，理解背后的原理才能让你触类旁通。

6.1 为什么 Nim 的异或恰好等价于 SG 函数

如果你接触过组合博弈论，一定听过 SG 函数（Sprague-Grundy 函数）。SG 函数的定义是：一个局面的 SG 值等于所有可达局面的 SG 值的 mex（最小未出现的非负整数）。对于单个堆来说，一堆有 k 根火柴，你可以一步走到 0 到 k-1 这 k 个状态，所以这 k 个状态的 SG 值正好是 0、1、2、...、k-1，它们的 mex 就是 k。

也就是说，单堆游戏的 SG 值就是它自己的火柴数。而多个独立子游戏组成的局面，总 SG 值等于各子游戏 SG 值的异或。这不就又回到了 Nim 的异或判定吗？所以 Nim 不是独立于 SG 理论之外的东西，而是 SG 理论最简单、最直接的一个实例。P1247 之所以可以直接异或判断，本质上是 SG 定理在单堆 SG = k 这个特例下的表现。

6.2 几个容易踩坑的经典变形

搞懂标准 Nim 后，我建议你去对比几个变种，它们能帮你检查自己是不是真的理解，而不是只会套异或：

• 反 Nim：规则改成取走最后一根火柴的人反而输。这时简单的异或判定就不完整了，因为终局的异或为 0，但终局本身变成了“走到这个局面的人赢”。通常需要额外讨论“全部堆都为 1”的特殊情况。
• 威佐夫博弈：两堆火柴，每次可以从一堆取任意数量，也可以从两堆取走相同数量的火柴。这个问题的判断和黄金分割比有关，不再是一句“异或为 0”能解决的。
• 每次可以操作多堆的 Nim 变体：比如一次最多能从 k 堆里取火柴，判定的阈值可能不再单纯是异或，而是二进制按位求和取模。

这些变形的共同点是，都在挑战“状态怎么编码”这个核心问题。标准 Nim 用异或，威佐夫用黄金分割比，反 Nim 用分类讨论——看起来五花八门，但背后的思路都是从终局往前推导，找到不变量，再证明一步转移的性质。

6.3 做题时如何识别“披着外衣的 Nim”

我自己刷题时总结过一个套壳识别法。如果题目描述里有这么几个特征：有若干堆东西；每步只能选一堆操作；操作是减少数量；不能操作的人输（或赢）。那这道题大概率可以往 Nim 的方向想，先用异或试试，再要求自己把必胜第一步构造出来。

为什么我强调“构造第一步”这么重要？因为只判断胜负，你其实只是在验证定理；能构造方案，才说明你真的理解了这个状态的转移逻辑。P1247 就是逼你走出这一步的题目。我后来做很多博弈题时，都会额外多问自己一句：如果这道题让我输出方案，我能不能写出来？这个习惯帮我避开过无数“看着懂了，一写就废”的尴尬。

提示：如果你刚开始学博弈论，建议把标准 Nim 的判断、证明、构造方案这三个环节当成一套组合拳来练。别急着背 SG 函数的模板，先把手算一个局面的完整过程写出来，比刷十道模板题都管用。

我个人做完 P1247 之后最大的感受是：异或这个东西，以前总觉得它只是位运算技巧，直到用在博弈论里才真正体会到它的“结构美感”。它恰好把“全局平衡”编码进了一个数字，而游戏过程变成了双方轮流尝试“破坏平衡”和“恢复平衡”的博弈。学会用t = a[i] ^ s反向构造走法之后，那些所谓的“随机拿”“凭感觉拿”的冲动就彻底消失了——因为每一步都可以被数学答案唯一锁定，你要做的只是找到它，而不是猜它。