取石子游戏与SG函数

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

题意:有3堆石子,石子数量分别为a,b,c,有两个玩家,每次只能从任意一堆中取f个,这里的f只能为fibnacci数,问是先手胜

还是先手败.

分析:由于石子的数量都在1000以内,那么我们可以先预处理出1000以内的SG函数值,然后对于3堆石子,我们进行异或,如果为

0说明先手必败,否则必胜,当然求SG函数的值用深搜就行了.

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 1005;
const int M = 25;

int fib[25];
int SG[N];

int mex(int x)
{
    bool vis[M];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<M;i++)
    {
        int t = x - fib[i];
        if(t < 0) break;
        if(SG[t] == -1)
            SG[t] = mex(t);
        vis[SG[t]] = 1;
    }
    for(int i=0;;i++)
    if(!vis[i]) return i;
}

void Init()
{
    fib[0] = 1;
    fib[1] = 2;
    for(int i=2;i<M;i++)
        fib[i] = fib[i-1] + fib[i-2];
    memset(SG,-1,sizeof(SG));
    for(int i=0;i<N;i++)
        SG[i] = mex(i);
}

int main()
{
    Init();
    int a,b,c;
    while(~scanf("%d%d%d",&a,&b,&c))
    {
        if(a == 0 && b == 0 && c == 0) break;
        int ans = 0;
        ans ^= SG[a];
        ans ^= SG[b];
        ans ^= SG[c];
        if(ans) puts("Fibo");
        else    puts("Nacci");
    }
    return 0;
}

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1536

分析:本题基本上跟上体一样,只是把3堆改为x堆,把取fibnacci数列颗石子改为取指定输入的石子个数.那么做法实际上一

样,我们对输入的序列进行排序,然后求出它们的SG函数的值,然后直接用即可.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int N = 10005;
const int M = 105;

int a[M];
int SG[N];
int n;

int mex(int x)
{
    bool vis[M];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        int t = x - a[i];
        if(t < 0) break;
        if(SG[t] == -1)
            SG[t] = mex(t);
        vis[SG[t]] = 1;
    }
    for(int i=0;;i++)
    if(!vis[i]) return i;
}

int main()
{
    while(~scanf("%d",&n))
    {
        if(n == 0) break;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        memset(SG,-1,sizeof(SG));
        for(int i=0;i<N;i++)
            SG[i] = mex(i);
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int ans = 0;
            int len,t;
            scanf("%d",&len);
            for(int i=0;i<len;i++)
            {
                scanf("%d",&t);
                ans ^= SG[t];
            }
            if(ans) printf("W");
            else    printf("L");
        }
        puts("");
    }
    return 0;
}