AcWing 894. 拆分-Nim游戏
原题链接
简单
作者:
术
,
2021-03-24 14:27:44
,
所有人可见
,
阅读 375
#include <iostream>
#include <string.h>
#include <unordered_set>
using namespace std;
const int N=105;
int f[N];
int sg(int x){
if(f[x]!=-1) return f[x];
unordered_set<int> us;
for(int i=0;i<x;i++){
for(int j=0;j<=i;j++)//防止i,j重复
{
us.insert(sg(i)^sg(j));
}
}
//mex
for(int i=0;;i++)
if(!us.count(i)) return f[x]=i;
}
int main()
{
int n;
int res=0;
cin>>n;
memset(f,-1,sizeof f);
for(int i=0;i<n;i++){
int x;
cin>>x;
res^=sg(x);
}
if(res) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
//cout << "Hello world!" << endl;
return 0;
}
for(int i=0;i<x;i)
for(int j=0;j<=i;j)
S.insert(sg(i)^sg(j));
为啥i+j的值可以大于x? sg()sg() 括号里面的值是分配之后堆的数还是要分配到这两个堆的石子数?
因为新的两个堆总数可以大于旧堆,sg的参数是旧堆石子数量
好的,昨天不太明白,现在看了差不多
hh加油