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

题目链接

【模板】Anti-Nim游戏

题目描述

给定 $n$ 堆石子，数量分别为 $a_1, a_2, \dots, a_n$ 。两位玩家轮流操作，Alice 先手。

操作规则如下：

每次任选一堆石子，取走正整数个。
拿到最后一个石子的一方判负。

如果双方均采用最优策略，判断先手是否必胜。

解题思路

本题是 Anti-Nim 游戏，也称为反 Nim 游戏或 Misere Play Nim。它的规则与标准 Nim 游戏几乎完全相同，唯一的区别在于胜负的判定：在 Anti-Nim 游戏中，取走最后一个石子的玩家失败，而不是胜利。

虽然规则只有微小差别，但其最优策略与标准 Nim 游戏有所不同，需要分情况讨论。标准 Nim 游戏的胜负手由所有石子堆数量的异或和（Nim-sum）决定。Anti-Nim 游戏的策略也基于 Nim-sum，但存在一个特殊情况。

设 Nim-sum 为 $X = a_1 \oplus a_2 \oplus \dots \oplus a_n$ 。

先手（Alice）必胜的条件，需要根据石子堆的状态分为两种情况：

情况一：所有石子堆的数量均为 1

在这种情况下，游戏变为一个简单的计数问题。总共有 $n$ 堆，每堆 1 个石子。

如果 $n$ 是偶数，Alice 取一堆后剩下奇数堆。Bob 再取一堆，又剩下偶数堆。如此交替，最后一定是 Bob 取走倒数第二堆，留给 Alice 最后一堆。Alice 被迫取走最后一堆而失败。因此，当 $n$ 为偶数时，Alice 必败。
如果 $n$ 是奇数，Alice 取一堆后剩下偶数堆。同理，最后一定是 Alice 取走倒数第二堆，留给 Bob 最后一堆，Bob 失败。因此，当 $n$ 为奇数时，Alice 必胜。

注意：此处的胜负结论与常规思维相反，因为拿走最后一个算输。如果 $n$ 是偶数，Alice 拿第 1, 3, 5, ..., (n-1) 个，Bob 拿第 2, 4, ..., n 个。Bob 拿最后一个，Bob 输，Alice 胜。如果 $n$ 是奇数，Alice 拿第 1, 3, ..., n 个。Alice 拿最后一个，Alice 输，Bob 胜。

修正后的结论:

若所有堆均为 1，当 $n$ 为偶数时，Alice 必胜。
若所有堆均为 1，当 $n$ 为奇数时，Alice 必败。

情况二：至少有一堆石子的数量大于 1

在这种情况下，游戏的终局离得还远，玩家有足够的策略空间。其胜负手与标准 Nim 游戏完全一致：

如果 Nim-sum $X \neq 0$ (非零)，则先手（Alice）必胜。
- 策略: Alice 总能找到一堆石子，取走一部分后使得新的 Nim-sum 变为 0。只要游戏没有进入“所有堆都为 1”的临界状态，Alice 就可以一直将 Nim-sum 为 0 的局面留给 Bob。Bob 无论如何操作，都会使得 Nim-sum 再次变为非零。最终 Alice 会将 Bob 引入一个必败局面。
如果 Nim-sum $X = 0$ (为零)，则先手（Alice）必败。
- 策略: 无论 Alice 如何操作，新的 Nim-sum 必定不为 0。接下来 Bob 总能通过一次操作，使得 Nim-sum 重新变为 0。Alice 始终面对 Nim-sum 为 0 的局面，而 Bob 始终面对 Nim-sum 非 0 的局面，因此 Bob 掌握了主动权，Alice 必败。

总结

综合以上两种情况，我们可以得出 Alice (先手) 的必胜条件：

所有堆石子数都大于 1：此时 Alice 必胜当且仅当 Nim-sum 不为 0。
所有堆石子数均为 1：此时 Alice 必胜当且仅当石子堆数 $n$ 为偶数。

代码

cpp
java
python

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

void solve() {
    using namespace std;
    int n;
    cin >> n;
    vector<int> a(n);
    int nim_sum = 0;
    bool all_ones = true;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] > 1) {
            all_ones = false;
        }
        nim_sum ^= a[i];
    }

    if (all_ones) {
        // 如果所有堆都是 1, 堆数为偶数则先手胜
        if (n % 2 == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    } else {
        // 如果至少有一堆大于 1, Nim-sum 不为 0 则先手胜
        if (nim_sum != 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    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) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] a = new int[n];
        int nim_sum = 0;
        boolean all_ones = true;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (a[i] > 1) {
                all_ones = false;
            }
            nim_sum ^= a[i];
        }

        if (all_ones) {
            // 如果所有堆都是 1, 堆数为偶数则先手胜
            if (n % 2 == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        } else {
            // 如果至少有一堆大于 1, Nim-sum 不为 0 则先手胜
            if (nim_sum != 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    nim_sum = 0
    all_ones = True
    for x in a:
        if x > 1:
            all_ones = False
        nim_sum ^= x
        
    if all_ones:
        # 如果所有堆都是 1, 堆数为偶数则先手胜
        if n % 2 == 0:
            print("YES")
        else:
            print("NO")
    else:
        # 如果至少有一堆大于 1, Nim-sum 不为 0 则先手胜
        if nim_sum != 0:
            print("YES")
        else:
            print("NO")

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法: 博弈论, Anti-Nim 游戏
时间复杂度: 每个测试用例需要遍历一次所有石子堆，计算 Nim-sum 和检查是否全为 1，因此时间复杂度为 $\mathcal{O}(n)$ 。总时间复杂度为 $\mathcal{O}(\sum n)$ 。
空间复杂度: 需要存储 $n$ 堆石子的数量，空间复杂度为 $\mathcal{O}(n)$ 。