AcWing 893. 集合-Nim游戏(内附详细解析)
原题链接
简单
作者:
Cold
,
2021-07-18 16:37:33
,
所有人可见
,
阅读 227
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 110;
const int M = 1e5+10;
int s[N],f[M];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x)
{
if(f[x]!=-1) return f[x];//保证每个状态只被算过一次
unordered_set<int> S;//存下的是一个集合,下一次递归中的S不与本次相同 每次递归产生的是S1,S2....Sn
//对于每一个状态,存储它所能到的下一个状态的sg函数值,S是不断更新的,因为在不停的定义新的S;
for (int i = 0; i < m; i ++ )
{
int sum=s[i];
if(x>=sum)
{
//使用哈希表存放所有可以到达的状态,使用sum存放集合的点个数,
//如果当前的数 x 大于可以拿的个数,记录状态 x - sum(sg(x - sum))
//递归 生成树
S.insert(sg(x-sum));
}
}
for (int i = 0; ; i ++ )//选出最小的没有出现的自然数
{
if(!S.count(i))//count()返回集合中某个值元素的个数
return f[x]=i;
}
}
int main()
{
cin>>m;
for(int i=0;i<m;i++)
cin>>s[i];
cin>>n;
memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过
int res=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
res^=sg(x);
//观察异或值的变化,基本原理与Nim游戏相同
}
if(res) printf("Yes");
else printf("No");
return 0;
}