UVA 1566 John：反 Nim 遊戲的特殊情況處理

遊戲規則與標準 Nim 差異

UVA 1566《John》是反 Nim 遊戲：多堆石子，輪流任取一堆任意數量，取走最後一顆石子者輸（標準 Nim 取走最後者贏）。給定初始堆數與大小，判斷先手（John）是否必勝。

解法：全 1 堆特判 + 一般情況 Nim 和

1. 若所有堆大小均為 1：先手勝當且僅當堆數為偶數（因每次必取 1 顆，偶數堆先手取完倒數第二堆，迫使對手取最後一顆）。
2. 否則（存在 ≥2 的堆）：按標準 Nim 計算 xor_sum = a1 ^ a2 ^ ... ^ an，先手勝當且僅當 xor_sum != 0。

完整 AC 程式碼

#include <cstdio>
using namespace std;
const int MAXN = 50;

int main() {
    int cas; scanf("%d", &cas);
    while (cas--) {
        int n, x, xorsum = 0;
        bool has_gt1 = false;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &x);
            xorsum ^= x;
            if (x > 1) has_gt1 = true;
        }
        if (has_gt1)
            puts(xorsum ? "John" : "Brother");
        else
            puts((n & 1) ? "Brother" : "John");
    }
    return 0;
}

理論速記

• 反 Nim 的 P-position：全 1 且堆數為奇數、或非全 1 且 Nim 和為 0
• 證明核心：將 ≥2 的堆視為「控制權」，先手可將其減為 1 或 0 以調整全 1 堆的奇偶性