7
7
2015
0

hdu 1848: Fibonacci again and again

第一次写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;
}
Category: 博弈论 | Tags: HDU 博弈论 | Read Count: 306

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com