首页 > 代码库 > HDU 1848
HDU 1848
http://acm.hdu.edu.cn/showproblem.php?pid=1848
利用计算grundy数组,把一类博弈转化为nim博弈,最后x不为0为先手必胜态
#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <algorithm>using namespace std ;//N堆硬币,每堆Xi//每次从一堆中取a1 a2...ak,先取完胜 const int MAX_X=1005 ;const int MAX_K=25 ;const int MAX_N=5 ;int N,K,X[MAX_N],A[MAX_K] ;int grundy[MAX_X] ; void solveSG(){ grundy[0]=0 ; //int max_x=*max_element(X,X+N) ; for(int j=1 ;j<=1000 ;j++) { set <int> s ; for(int i=0 ;A[i]<=j ;i++)//A[i]<=j { if(A[i]<=j)s.insert(grundy[j-A[i]]) ; } int g=0 ; while(s.count(g)!=0)g++ ; grundy[j]=g ; } /* int x=0 ; for(int i=0 ;i<N ;i++)x^=grundy[X[i]] ; if(x)puts("Fibo") ;//先手胜 else puts("Nacci") ;//后手胜 */} int main(){ A[0]=A[1]=1 ; for(int i=2 ;i<20 ;i++) A[i]=A[i-1]+A[i-2] ; solveSG() ; while(~scanf("%d%d%d",&X[0],&X[1],&X[2])) { if(!X[0] && !X[1] && !X[2])break ; int x=0 ; for(int i=0 ;i<3 ;i++)x^=grundy[X[i]] ; if(x)puts("Fibo") ;//先手胜 else puts("Nacci") ;//后手胜 } return 0 ;}
HDU 1848
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。