这题运用博弈中的SG函数解决的,感觉初级博弈题用这个很好用但是难一些的还是不会求SG值,就是SG的模板题。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int k,fib[1000],f[10001]; int mex1(int p) { int i,t; bool g[101]= {0}; for(i=0; i<k; i++) { t=p-fib[i]; if(t<0) break; if(f[t]==-1) f[t]=mex1(t); g[f[t]]=1; } for(i=0;; i++) if(!g[i]) return i; } int main() { fib[0]=1,fib[1]=2; for(int i=2; i<19; i++) fib[i]=fib[i-1]+fib[i-2]; k=19; sort(fib,fib+k); memset(f,-1,sizeof(-1)); f[0]=0; for(int i=1; i<=1000; i++) f[i]=mex1(i); int a,b,c; while(~scanf("%d%d%d",&a,&b,&c),a+b+c) { int s=f[a]^f[b]^f[c]; if(s) puts("Fibo"); else puts("Nacci"); } return 0; }