首页 > 其他 > 详细

HDU-1848 SG函数水题

时间:2017-01-27 12:57:18      阅读:276      评论:0      收藏:0      [点我收藏+]

HDU 1848

题意:3堆石子,数量分别为n,m,p,两个人轮流选一堆取f个,f只能是Fibonacci数列中的数,问先手胜负。

// HDU-1848
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define F(i,a,b)  for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 1e3+10;

int  f[17], sg[N], hashn[21];
int n, m, p;
void Getsg()
{
    int i, j;
    sg[0]=0, sg[1]=1;
    F(i,2,N) {
        mes(hashn, 0);
        for(j=1; f[j]<=i; j++) hashn[sg[i-f[j]]]=1;
        FF(j,0,20) if(hashn[j]==0) {      //求未出现过的最小非负整数
            sg[i]=j;
            break;
        }
    }
}
int main()
{
    f[0]=f[1]=1;
    F(i,2,17) f[i]=f[i-1]+f[i-2];
    Getsg();
    while(scanf("%d%d%d", &n, &m, &p) && n&&m&&p) {
        if(sg[n]^sg[m]^sg[p]) puts("Fibo");
        else puts("Nacci");
    }

    return 0;
}

HDU-1848 SG函数水题

原文:http://www.cnblogs.com/sbfhy/p/6353771.html

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