如何将Nim游戏策略应用于Acwing第894题？
摘要：80.Acwing基础课第894题-简单-拆分-Nim游戏 题目描述 (给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆**规模更小**的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子
80.Acwing基础课第894题-简单-拆分-Nim游戏
题目描述
\(给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆**规模更小**的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败\)。
\(问如果两人都采用最优策略，先手是否必胜\)。
输入格式
\(第一行包含整数 n\)。
\(第二行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 a_i\)。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
\(1≤a_i,n≤10^5\)
输入样例：
2
2 3
输出样例：
Yes
代码：
// 包含字符串操作、输入输出、算法、无序集合头文件（存储可达SG值）
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
// 常量定义：N=110，适配石子堆的最大规模（SG函数计算上限）
const int N = 110;
int n; // n：石子堆的数量
int f[N]; // f[x]（SG(x)）：记忆化存储x个石子的SG值，-1表示未计算
// 递归计算x个石子的SG值（规则：可将x拆分为i和x-i两堆，i≤x-i）
int sg(int x)
{
// 记忆化剪枝：若x的SG值已计算，直接返回（避免重复递归）
if (f[x] != -1) return f[x];
// S集合：存储x个石子能一步到达的所有状态的SG值
unordered_set<int> S;
// 遍历所有合法拆分方式：将x拆为i和x-i（i从0到x-1）
// j≤i 是为了避免重复拆分（如i=1,j=2和i=2,j=1是同一状态）
for (int i = 0; i < x; i ++ )
for (int j = 0; j <= i; j ++ )
// 拆分后的状态SG值 = SG(i) ^ SG(j)（Sprague-Grundy定理）
// 因为拆分后的两堆是独立游戏，总SG值为两堆SG值的异或
S.insert(sg(i) ^ sg(j));
// 求mex值：找到不在S中的最小非负整数，作为x的SG值
for (int i = 0;; i ++ )
if (!S.count(i))
return f[x] = i; // 记忆化存储并返回
}
int main()
{
// 输入石子堆的数量
cin >> n;
// 初始化SG数组：所有值设为-1（表示未计算）
memset(f, -1, sizeof f);
// 计算所有堆的SG值的异或和（核心胜负判断依据）
int res = 0;
while (n -- )
{
int x; // 当前堆的石子数
cin >> x;
res ^= sg(x); // 异或累积所有堆的SG值
}
// 胜负判断：
// res≠0 → 先手有必胜策略；res=0 → 先手必败
if (res) puts("Yes");
else puts("No");
return 0;
}