首页 > 代码库 > hdu1848(sg函数打表)
hdu1848(sg函数打表)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1848
题意:中文题诶~
思路:直接sg函数打表就好了
代码:
1 #include <iostream> 2 #include <string.h> 3 #define MAXN 3010 4 using namespace std; 5 6 int f[MAXN], sg[MAXN]; 7 8 void init(){//得到1000以内的fibonacci数列 9 f[1]=1; 10 f[2]=2; 11 for(int i=3; ; i++){ 12 f[i]=f[i-1]+f[i-2]; 13 if(f[i]>1000){ 14 break; 15 } 16 } 17 } 18 19 void get_sg(){//sg函数打表 20 for(int i=1; i<=1000; i++){ 21 int vis[MAXN]; 22 memset(vis, 0, sizeof(vis)); 23 for(int j=1; f[j]<=i; j++){//找到当前节点能到达的点 24 vis[sg[i-f[j]]]=1; 25 } 26 for(int j=0; j<=1000; j++){//求mex函数 27 if(!vis[j]){ 28 sg[i]=j; 29 break; 30 } 31 } 32 } 33 } 34 35 int main(void){ 36 init(); 37 get_sg(); 38 int n, m, p; 39 while(cin >> n >> m >> p){ 40 if(n+m+p==0){ 41 break; 42 } 43 if(sg[n]^sg[m]^sg[p]){//sg函数性质 44 cout << "Fibo" << endl; 45 }else{ 46 cout << "Nacci" << endl; 47 } 48 } 49 return 0; 50 }
hdu1848(sg函数打表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。