SG函数（斐波那契博弈） Fibonacci again and again

https://zhuanlan.zhihu.com/p/53948422

HDU — 1848

将这篇文章认真的看了一遍，虽然不是很懂，但是脑子里有了一个模型，链接里的图（看的顺序是 0，1，2，3，4，5，g[i]]得出过程）换成这道题，完全OK

#include<stdio.h>

#include<string.h>

int f[20],sg[1005],book[20];

/*如果拿的数量不被限制的话 ，就是nim博弈 ，

当拿的数被限制以后 ，ai->ai’ 未必合法，

那就要找一个g[ai]->g[ai]’合法 （注意 g[ai]得出来的过程，ai由小到大推出 ）*/

void get_sg()

{

    memset(sg,0,sizeof(sg));

    for(int i=1; i<1005; i++)

    {

        memset(book,0,sizeof(book));

        for(int j=1; f[j]<=i; j++)

        {

            book[sg[i-f[j]]]=1;/*看成有向图之后，i->f[j]是直接到达   */

        }

        for(int j=0; j<20; j++)

            if(!book[j])

            {

                sg[i]=j;

                break;

            }

    }

}

int main()

{

    f[1]=1,f[2]=2;

    for(int i=3; i<19; i++)

        f[i]=f[i-1]+f[i-2];

    get_sg();

    int a,b,c;

    while(~scanf("%d%d%d",&a,&b,&c))

    {

        if(a==0&&b==0&&c==0)

            break;

        if((sg[a]^sg[b]^sg[c])==0)

            printf("Nacci\n");

        else printf("Fibo\n");

    }

    return 0;

}

巴特西

SG函数（斐波那契博弈） Fibonacci again and again

最新文章

热门文章