POJ 1740 A New Stone Game：博弈論中的成對策略

題目大意

有 n 堆石子，兩人輪流操作：選一堆拿走至少一顆，並可將任意數量石子移至其他一堆或多堆。無石子可拿者負。判斷先手勝負。

核心洞察：成對即必敗

將每堆石子數量出現的次數統計。若所有堆的石子數均成對出現（即每種數量出現偶數次），則先手必敗（輸出 0）；否則先手必勝（輸出 1）。

理由：

• 成對局面：後手可採用「鏡像策略」——完全模仿先手的操作（拿同樣數量、移同樣數量到對稱堆），始終維持成對局面，最終先手無路可走。
• 非成對局面：先手總能利用最大的那堆，將所有落單的堆「補成對」，轉化為成對局面交給對手，從而獲勝。

代碼實現

#include <stdio.h>
#include <string.h>
const int N = 105;
int main() {
    int a, n, c[N];
    while (scanf("%d", &n) == 1 && n) {
        memset(c, 0, sizeof(c));
        for (int i = 0; i < n; i++) {
            scanf("%d", &a);
            c[a]++;
        }
        int ans = 0;
        for (int i = 0; i < N; i++) ans += (c[i] & 1);  // 統計出現奇數次的堆數量
        printf("%d\n", ans ? 1 : 0);  // 有落單則先手勝
    }
    return 0;
}

時間複雜度 O(n + V)，V 為石子數上限（此處 100），極其高效。