NYOJ 取石子（六）：奇偶性博弈

NYOJ 取石子（六）題解：Nim 遊戲變體

題目： m 堆石子，兩人輪流從任意一堆取任意多個（至少一個），取完最後一堆者勝。PIAOYI 先手，判斷勝負。

核心結論

這是標準 Nim 遊戲：先手勝 ⇔ 所有堆石子數異或和 ≠ 0。但本題數據範圍暗示更簡單規律：

• 統計奇數堆的個數 k。
• 若 k 為奇數，先手勝（PIAOYI）；否則後手勝（HRDV）。

理由：每堆石子數對 2 取模後，遊戲等價於每堆 0 或 1 顆石子的 Nim，異或和即為 1 的個數奇偶性。

參考代碼

#include <stdio.h>
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, i, k = 0, t;
        scanf("%d", &n);
        for (i = 0; i < n; ++i) {
            scanf("%d", &t);
            if (t & 1) k++;
        }
        if (k % 2) printf("PIAOYI\n");
        else printf("HRDV\n");
    }
    return 0;
}

複雜度

O(總石子堆數)，空間 O(1)。

擴展思考

若改為「每次只能取 1 或 2 個」，則為取石子遊戲，需用 SG 函數分析；本題無取數限制，故為標準 Nim。