AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
c0marde
,
2021-02-04 00:46:55
,
所有人可见
,
阅读 345
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N=110,M=10010;
int s[N],f[M]; //s[]存每一次可以搬运的石头数量,f[]存有向图中每个点对应的sg的值
int k;
//时间复杂度;最多有100张有向图,每张图最多有10000扩展的点(状态),所以为1e6
int sg(int x)
{
//每调用一次sg函数都可以生成一个有向图,并求出其中每个点sg的值
unordered_set<int> S;
if(f[x]!=-1) return f[x]; //保证每个状态值只求一次
for(int i=0;i<k;i++)
if(x>=s[i]) S.insert(sg(x-s[i])); //这次遍历等价于将图从起点开始扩展
for(int i=0;;i++)
if(!S.count(i)) return f[x]=i;
}
int main()
{
cin>>k;
for(int i=0;i<k;i++) cin>>s[i];
memset(f,-1,sizeof f);
int n;
cin>>n;
int res=0;
while(n--)
{
int x;
cin>>x;
res^=sg(x);
}
if(res) puts("Yes");
else puts("No");
return 0;
}