HDU 1848 SG函数

简介:

这题运用博弈中的SG函数解决的,感觉初级博弈题用这个很好用但是难一些的还是不会求SG值,就是SG的模板题。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int k,fib[1000],f[10001];
int mex1(int p)
{
    int i,t;
    bool g[101]= {0};
    for(i=0; i<k; i++)
    {
        t=p-fib[i];
        if(t<0)
            break;
        if(f[t]==-1)
            f[t]=mex1(t);
        g[f[t]]=1;
    }
    for(i=0;; i++)
        if(!g[i])
            return i;
}
int main()
{
    fib[0]=1,fib[1]=2;
    for(int i=2; i<19; i++)
        fib[i]=fib[i-1]+fib[i-2];
    k=19;
    sort(fib,fib+k);
    memset(f,-1,sizeof(-1));
    f[0]=0;
    for(int i=1; i<=1000; i++)
        f[i]=mex1(i);
    int a,b,c;
    while(~scanf("%d%d%d",&a,&b,&c),a+b+c)
    {
        int s=f[a]^f[b]^f[c];
        if(s)
            puts("Fibo");
        else
            puts("Nacci");
    }
    return 0;
}


目录
相关文章
hdu 1754 I Hate It
点击打开链接hdu 1754 思路: 线段树+单点更新 分析: 1 线段树的水题 代码: /************************************************ * By: chenguolin ...
789 0
hdu 3047 Zjnu Stadium
点击打开链接hdu 3047 思路: 带权并查集 分析: 1 题目要求的是错误的条件的个数,这一题还是比较简单的带权并查集 2 我们用rank[x]表示的x到跟节点的距离,那么对于x和y来说,如果x和y在不同集合那么把x和y合并,否则直接...
808 0
|
人工智能 BI Go
HDU 1087
Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 13479 Accepted ...
753 0
|
Java 机器学习/深度学习
HDU 1492
The number of divisors(约数) about Humble Numbers Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): ...
891 0

热门文章

最新文章