拆分-Nim游戏
题目大意很好理解就是拿走一堆放回两堆但是两堆(任意一堆)的数量是不能大于拿走的那一堆的。
这导致题目很难模拟出来。
其实这样看的话很像深搜一样,因为可能性很多种所以就像是搜索一样。
而搜索是什么样的?不同的分支不同的选项达成不同的结果。
而这些分支是从一个状态到达另外一个状态,所以如果把这些状态画起来那是不是一张有向图了?
代码
代码的难度并不高,就只是把所有的状态的SG都算出来罢了。
#include<set>
#include<cstdio>
#include<cstring>
using namespace std;
int n,f[101];
int sg(int x)
{
if(f[x]!=-1)return f[x];
int i,j;set<int>s;
for(i=0;i<x;++i)for(j=0;j<=i;++j)s.insert(sg(i)^sg(j));
for(i=0;;++i)if(!s.count(i))return f[x]=i;
}
int main()
{
int i,x,s=0;memset(f,-1,sizeof f);
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",&x),s^=sg(x);
printf("%s",s?"Yes":"No");
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() 括号里面的值是分配之后堆的数还是要分配到这两个堆的石子数?
太久没写代码了可能回答不准确,i+j可以大于X是题目的要求然后sg括号的这个是因为需要去求出当前这个数通过sg函数来求出来可不可能是先手赢也就是返回的这个1或者是0,然后因为题目这个是只能分成两堆的但其中一堆最小可以是0或者是都是0这样的极端情况所以不是堆数是石子数
为什么你的代码,把set定义在外面也能AC!!!
可能是数据太水了吧