首页 > 其他 > 详细

HDU 1848

时间:2014-09-01 02:43:52      阅读:264      评论:0      收藏:0      [点我收藏+]

http://acm.hdu.edu.cn/showproblem.php?pid=1848

利用计算grundy数组,把一类博弈转化为nim博弈,最后x不为0为先手必胜态

bubuko.com,布布扣
#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

原文:http://www.cnblogs.com/xiaohongmao/p/3948489.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!