题解

涉及知识点

1. 博弈论中的Nim游戏

   • 本题是经典的Nim游戏变种，胜负规则与标准Nim游戏一致。
   • 关键定理：Nim游戏的先手必胜条件为所有堆火柴数的异或和（Nim和）不为零。即：
     [ \text{若} \quad \bigoplus_{i=1}^{M} a_i \neq 0 \quad \text{则先手必胜，否则必败。} ]

2. 异或性质

   • 异或（$\oplus$）满足交换律、结合律，且 $a \oplus a = 0$。
   • 通过计算所有堆火柴数的异或和，可以快速判断游戏结果。

3. 算法选择

   • 直接计算所有堆火柴数的异或和，根据结果输出答案。
   • 时间复杂度：$O(M)$，空间复杂度：$O(1)$。

代码

#include <iostream>
using namespace std;

int main() {
    int M;
    while (cin >> M) {
        int xor_sum = 0;
        for (int i = 0; i < M; ++i) {
            int a;
            cin >> a;
            xor_sum ^= a;
        }
        cout << (xor_sum != 0 ? "Yes" : "No") << endl;
    }
    return 0;
}

代码解释

• 输入处理：循环读取每个测试用例。
• 异或和计算：初始化 xor_sum 为0，逐堆异或火柴数。
• 胜负判断：若异或和不为零，先手必胜（Yes），否则必败（No）。

总结

本题是博弈论中Nim游戏的直接应用，通过异或和的性质快速判断先手胜负。核心在于理解Nim游戏的必胜条件，并高效实现异或计算。