AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
术
,
2021-03-24 13:09:12
,
所有人可见
,
阅读 237
#include <iostream>
#include <string.h>
#include <unordered_set>
using namespace std;
//SG=mex() 未出现的最小自然数
const int N=105;
const int M=100005;
int s[N],f[M];
int h[N];
int n,k;
//堆中剩余x个石子的 sg函数值
int sg(int x)
{
if(f[x]!=-1)
return f[x];//若计算过
unordered_set<int> us;
for(int i=0; i<k; i++)
{
int sum=s[i];
if(x>=sum)
us.insert(sg(x-sum));
}
//找mex
for(int i=0;; i++)
if(!us.count(i)){
//cout<<x<<" "<<i<<endl;
return f[x]=i;
}
}
int main()
{
cin>>k;
for(int i=0; i<k; i++)
cin>>s[i];
cin>>n;
memset(f,-1,sizeof f);
int res=0;
for(int i=0; i<n; i++)
{
cin>>h[i];
res^=sg(h[i]);
}
if(res)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
//cout << "Hello world!" << endl;
return 0;
}