题解 | #【模板】Nim游戏#

题目链接

题目描述

有 $k$ 堆石子，第 $i$ 堆有 $a_i$ 个。Alice 和 Bob 两位玩家轮流行动，Alice 先手。每人每次可以从任意一堆中取走任意正整数个石子（也可以取完）。取走最后一颗石子的玩家获胜。假设双方都采取最优策略，判断先手能否必胜。

解题思路

本题是组合博弈论中最经典的模型——Nim 游戏。所有公平组合博弈（Impartial Games）的问题都可以通过 Sprague-Grundy 定理转化为 Nim 游戏。

对于 Nim 游戏本身，有一个简洁而优美的结论来判断胜负： 一个 Nim 游戏的局面是必败态，当且仅当所有石子堆数量的异或和 (XOR sum) 等于 0。

这个异或和在博弈论中被称为 Nim 和 (Nim-Sum)。

定理证明思路：

我们定义一个局面的 Nim 和为 $S = a_1 \oplus a_2 \oplus \dots \oplus a_k$ ，其中 $\oplus$ 是按位异或操作。

终局状态：游戏结束时，所有石子堆都为 0，此时 $S=0$ 。根据规则，轮到当前玩家时已无石子可取，因此该玩家判负。所以，Nim 和为 0 的终局是一个必败态，这与定理一致。
从任意 $S \neq 0$ 的局面，总能一步转移到 $S'=0$ 的局面：假设当前 Nim 和 $S \neq 0$ 。设 $S$ 的二进制表示中最高位的 1 在第 $d$ 位。那么，在所有石子堆中，必然存在至少一堆 $a_i$ ，其二进制表示的第 $d$ 位也为 1（否则 $S$ 的第 $d$ 位不可能是 1）。此时，玩家可以选择第 $i$ 堆，并从中取走一些石子，使其数量变为 $a_i' = a_i \oplus S$ 。
- 因为 $a_i$ 和 $S$ 的最高有效位相同，所以 $a_i \oplus S < a_i$ ，这意味着 $a_i'$ 是一个比 $a_i$ 更小的非负数。这是一个合法的操作（取走了 $a_i - a_i'$ 个石子）。
- 操作后，新的 Nim 和变为 $S' = a_1 \oplus \dots \oplus a_i' \oplus \dots \oplus a_k = a_1 \oplus \dots \oplus (a_i \oplus S) \oplus \dots \oplus a_k = (a_1 \oplus \dots \oplus a_k) \oplus S = S \oplus S = 0$ 。
- 这证明了，任何一个 Nim 和不为 0 的局面都是必胜态，因为玩家总能将一个 Nim 和为 0 的局面留给对手。
从任意 $S = 0$ 的局面，无论如何操作，都会转移到 $S' \neq 0$ 的局面：假设当前 Nim 和 $S = 0$ 。玩家必须选择一堆 $a_i$ 并将其变为 $a_i'$ （ $a_i' < a_i$ ）。
- 操作后，新的 Nim 和变为 $S' = 0 \oplus a_i \oplus a_i'$ 。
- 因为 $a_i' \neq a_i$ ，所以 $a_i \oplus a_i' \neq 0$ ，即 $S' \neq 0$ 。
- 这证明了，任何一个 Nim 和为 0 的局面都是必败态，因为玩家无论如何操作，都必然会将一个 Nim 和不为 0 的局面留给对手。

最终结论： Alice 作为先手，只需计算初始时所有石子堆的 Nim 和。

如果 Nim 和不等于 0，则为必胜态，Alice 胜。
如果 Nim 和等于 0，则为必败态，Bob 胜。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        int nim_sum = 0;
        for (int i = 0; i < k; ++i) {
            int a;
            cin >> a;
            nim_sum ^= a;
        }
        if (nim_sum == 0) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int k = sc.nextInt();
            int nimSum = 0;
            for (int i = 0; i < k; i++) {
                nimSum ^= sc.nextInt();
            }
            if (nimSum == 0) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}

import sys

def solve():
    t_str = sys.stdin.readline()
    if not t_str:
        return
    t = int(t_str)
    for _ in range(t):
        k_str = sys.stdin.readline()
        if not k_str: break
        
        line = sys.stdin.readline()
        if not line: break
        
        nums = map(int, line.split())
        nim_sum = 0
        for num in nums:
            nim_sum ^= num
            
        if nim_sum == 0:
            print("NO")
        else:
            print("YES")

solve()

算法及复杂度

算法: 博弈论 (Nim 游戏)
时间复杂度: 对于每组测试数据，我们需要读取 $k$ 个数字并计算它们的异或和，时间复杂度为 $\mathcal{O}(k)$ 。总的时间复杂度为 $\mathcal{O}(\sum k)$ 。
空间复杂度: 我们只需要一个变量来存储异或和，空间复杂度为 $\mathcal{O}(1)$ 。