第一次写sg函数的题,看起来并不容易的样子= =
直觉看起来,像是sg[x]==0的话,此时先手必败的说= =
显然看不懂证明,也不要在意细节啦。
坑就坑在这一行:if((sg[n]^sg[m]^sg[p])==0)
原来异或时候要打上括号= =,害的我WA了好多次。。
代码:
#include<cstdio> #include<cstring> using namespace std; int f[100],sg[1010],a[1010]; int main(){ f[1]=1; f[2]=2; for(int i=3;f[i-1]<=1000;i++){ f[i]=f[i-1]+f[i-2]; } sg[0]=0; for(int i=1;i<=1001;i++){ sg[i]=i; memset(a,0,sizeof(a)); for(int j=1;f[j]<=i;j++){ a[sg[i-f[j]]]=1; } for(int j=0;j<=1001;j++){ if(a[j]==0){ sg[i]=j; break; } } } int n,m,p; while(scanf("%d%d%d",&n,&m,&p),(n!=0||m!=0||p!=0)){ if((sg[n]^sg[m]^sg[p])==0){ printf("Nacci\n"); }else{ printf("Fibo\n"); } } return 0; }