首页 > 代码库 > hdu 1848 Fibonacci again and again （SG）
hdu 1848 Fibonacci again and again （SG）
题意：
3堆石头，个数分别是m,n,p。
两个轮流走，每走一步可以选择任意一堆石子，然后取走f个。f只能是菲波那契中的数（即1，2，3，5，8.....）
取光所有石子的人胜。
判断先手胜还是后手胜。
思路：
简单SG。看代码。
代码：
int sg[1005];int dfs(int x){ if(sg[x]!=-1) return sg[x]; bool vis[1005]={0}; int t1=1,t2=2; if(x>=t1) vis[dfs(x-t1)]=true; while(x>=t2){ vis[dfs(x-t2)]=true; t1=t1+t2; swap(t1,t2); } for(int i=0;;++i){ if(!vis[i]){ return sg[x]=i; } }}int m,n,p;int main(){ mem(sg,-1); while(scanf("%d%d%d",&m,&n,&p),m||n||p){ dfs(m); dfs(n); dfs(p); int ans=dfs(m)^dfs(n)^dfs(p); if(ans) puts("Fibo"); else puts("Nacci"); }}
hdu 1848 Fibonacci again and again （SG）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。