首页 > 代码库 > 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 ;}
View Code

 

HDU 1848