AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
我要出去乱说
,
2021-01-24 02:10:27
,
所有人可见
,
阅读 524
//关键在于理清程序中的n,m,s,x各代表什么,别搞糊涂了!
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int s[N], f[M]; //f[M]用于记忆搜索,f[x]表示有x个石子的石子堆的SG值
int sg(int x)
{
//若两个石子堆中石子数一样,则它们的SG值也相同,直接返回之间计算过的结果即可
if (f[x] != -1) return f[x];
unordered_set<int> S;
for (int i = 0; i < m; i ++ )
{
int sum = s[i];
if (x >= sum) S.insert(sg(x - sum)); //若石子数大于等于本次拿取的石子数,则递归,生成树
}
for (int i = 0; ; i ++ ) //实现mes()函数:取集合中不存在的最小自然数,结尾的点SG值为0...
if (!S.count(i))
return f[x] = i; //当递归回第一层时,返回SG(x1)的值,即要用来异或的值
}
int main()
{
cin >> m;
for (int i = 0; i < m; i ++ ) cin >> s[i]; //m表示集合S中数字个数,s[i]表示集合中的第i个数
cin >> n;
memset(f, -1, sizeof f);
int res = 0;
for (int i = 0; i < n; i ++) //n表示石子堆数量,x表示当前石子堆中石子数
{
int x;
cin >> x;
res ^= sg(x);
}
if (res) puts("Yes");
else puts("No");
return 0;
}
nb