AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
时间轴
,
2023-03-23 20:04:19
,
所有人可见
,
阅读 99
#include <bits/stdc++.h>
using namespace std;
const int N=110,M=1e5+10;
int s[N],f[M];//s[]代表取石子的方案(比如取1个,2个...),f[]代表有x个的石子的sg值
int n,m;
int sg(int x)
{
if(f[x]!=-1) return f[x];
//说明一下,因为当确定各个方案后,取石子的方式是唯一的,所有各个块当中相同数x的sg值是相同的
//这里用了记忆化搜索,如果x的sg值没有记录,则往下继续算
unordered_set<int>S;//用哈希表来存每个局面能到的所有情况,然后计算mex(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++)
if(!S.count(i)) return f[x]=i;//用mex运算求每个有向图游戏起点的sg值代表每个有向图游戏的sg值
}
int main()
{
cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(0);
cin>>m;
for(int i=0;i<m;i++) cin>>s[i];//读取每个取石子的方案
memset(f,-1,sizeof f);//记录sg函数中x的值是否被记录过
int res=0;
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;//读取每堆石子个数
res^=sg(x);
}
if(res) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}