Nim游戏集合问题怎么解决？
摘要：79.Acwing基础课第893题-简单-集合-Nim游戏 题目描述 (给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S)。 (现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集
79.Acwing基础课第893题-简单-集合-Nim游戏
题目描述
\(给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S\)。
\(现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败\)。
\(问如果两人都采用最优策略，先手是否必胜\)。
输入格式
\(第一行包含整数 k，表示数字集合 S 中数字的个数\)。
\(第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 s_i\)。
\(第三行包含整数 n\)。
\(第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 h_i\)。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
\(1≤n,k≤10^5\),
\(1≤a_i,h_i≤10^9\)
输入样例：
2
2 5
3
2 4 7
输出样例：
Yes
代码：
// 包含字符串操作、输入输出、算法、无序集合头文件（unordered_set用于存储可达SG值）
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
// 常量定义：
// N=110：适配输入的取石子规则数量/堆数
// M=10010：适配石子数的最大范围（SG函数的记忆化上限）
const int N = 110, M = 10010;
int n, m; // n：堆的数量；m：取石子的规则数（如可取1/2/3个，则m=3）
int s[N]; // s数组：存储取石子的规则（如s=[1,2,3]表示每次可取1、2或3个）
int f[M]; // f[x]（即SG(x)）：记忆化存储x个石子的SG值，-1表示未计算
// 递归计算x个石子的SG值（记忆化搜索）
int sg(int x)
{
// 记忆化剪枝：若x的SG值已计算过，直接返回（避免重复递归）
if (f[x] != -1) return f[x];
// S集合：存储x个石子能一步到达的所有状态的SG值
unordered_set<int> S;
// 遍历所有取石子规则
for (int i = 0; i < m; i ++ )
{
int sum = s[i]; // 当前规则：可取sum个石子
// 若剩余石子数≥sum（操作合法），递归计算x-sum的SG值并加入集合
if (x >= sum) S.insert(sg(x - sum));
}
// 求SG值的核心：找到最小的非负整数mex（最小排除值），即不在S中的最小非负整数
for (int i = 0; ; i ++ )
if (!S.count(i)) // 找到第一个不在S中的i
return f[x] = i; // 记忆化存储并返回SG(x)=i
}
int main()
{
// 第一步：输入取石子规则
cin >> m; // 输入规则数
for (int i = 0; i < m; i ++ ) cin >> s[i]; // 输入具体规则（如1 2 3）
// 第二步：输入堆的数量
cin >> n;
// 初始化SG函数数组：所有值设为-1（表示未计算）
memset(f, -1, sizeof f);
// 第三步：计算所有堆的SG值的异或和（尼姆游戏的扩展）
int res = 0; // 存储SG值的异或和
for (int i = 0; i < n; i ++ )
{
int x; // 当前堆的石子数
cin >> x;
res ^= sg(x); // 异或累积所有堆的SG值
}
// 第四步：胜负判断（同尼姆游戏）
// res≠0 → 先手有必胜策略；res=0 → 先手必败
if (res) puts("Yes");
else puts("No");
return 0;
}