题目解析

问题描述

给定 ( n ) 堆石子，两位玩家轮流操作。每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新增的石子总数可以大于取走的那堆石子数）。最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

输入格式

• 第一行包含整数 ( n )。
• 第二行包含 ( n ) 个整数，表示每堆石子的数量 ( a_i )。

输出格式

• 如果先手方必胜，则输出 “Yes”。
• 否则，输出 “No”。

解题思路

这个问题属于博弈论中的Nim游戏变种。我们可以使用Grundy数（或Nimber）来解决这个问题。Grundy数用于表示一个游戏状态的胜负情况。

Grundy数

• 对于每个游戏状态，Grundy数是所有可能的后继状态的Grundy数的mex（最小未被包含的非负整数）。
• 如果一堆石子的Grundy数为 0，表示当前玩家处于必败状态；否则，处于必胜状态。

拆分操作

• 每次操作可以将一堆石子拆分成两堆更小的石子堆。
• 对于一堆石子数为 ( x )，其Grundy数是所有可能的拆分方式对应的Grundy数的异或结果的mex。

数学推理

1. Grundy数计算:
2. 对于一堆石子数为 ( x )，其Grundy数 ( G(x) ) 是所有可能的拆分方式对应的Grundy数的异或结果的mex。

3. 即 ( G(x) = \text{mex}{G(i) \oplus G(j) \mid 0 \leq i, j < x} )。

4. 异或操作:

5. 将所有石子堆的Grundy数进行异或操作，得到最终结果。
6. 如果最终结果为非零，先手必胜；否则，先手必败。

复杂度分析

• 时间复杂度:
• 计算每个Grundy数的时间复杂度为 ( O(n^2) )，其中 ( n ) 是石子数的最大值（100）。

• 总时间复杂度为 ( O(n^3) )。

• 空间复杂度:

• 使用了一个大小为 ( O(n) ) 的数组来存储Grundy数。

C++ 代码实现

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

const int MAXN = 110;
int f[MAXN]; // 用于存储每个石子数的Grundy数

// 计算Grundy数的函数
int grundy(int x) {
    if (f[x] != -1) return f[x]; // 如果已经计算过，直接返回

    unordered_set<int> S;
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j <= i; ++j) {
            S.insert(grundy(i) ^ grundy(j)); // 所有可能的拆分方式
        }
    }

    // 计算mex
    int mex = 0;
    while (S.count(mex)) mex++;
    return f[x] = mex;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 初始化Grundy数数组
    fill(f, f + MAXN, -1);
    f[0] = 0; // 0个石子的Grundy数为0

    int res = 0;
    for (int i = 0; i < n; ++i) {
        res ^= grundy(a[i]); // 计算所有堆的Grundy数的异或
    }

    if (res != 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

代码解释

1. grundy函数:
2. 计算给定石子数 ( x ) 的Grundy数。
3. 使用一个集合 S 来存储所有可能的拆分方式对应的Grundy数的异或结果。

4. 计算 mex，即集合 S 中未出现的最小非负整数。

5. 主函数:

6. 读取输入的石子堆数和每堆的石子数。
7. 初始化Grundy数数组 f，并设置 f[0] = 0。
8. 计算所有石子堆的Grundy数的异或结果。
9. 根据异或结果输出 “Yes” 或 “No”。

这个算法在给定的数据范围内是高效的，能够正确判断先手是否必胜。