2014 Super Training #6 A Alice and Bob --SG函数

原题： ZOJ 3666 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3666

博弈问题。

题意：给你1~N个位置，N是最终点，1~N-1中某些格子能够移石头到另外一些指定的格子，1~N-1上有M个石头，位置不定，现在Alice和Bob要把这些石头全部移到N点,谁不能移则输，问先手必胜还是后手必胜。

做法：求出每个位置的SG函数值，然后将放石头的M个位置的SG函数值做异或，异或为0则Alice赢。这里讲坐标反转，1~N换成N-1~0,0点作为终点，更加直观。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

#define N 10007

int flag[N],step[N];

int sg[N];

vector<int> v[];

int mex(int x)

{

    int i,ans = ;

    memset(flag,,sizeof(flag));

    for(i=;i<v[x].size();i++)

        flag[sg[v[x][i]]] = ;

    for(i=;;i++)

        if(!flag[i])

            return i;

}

void setSG()

{

    int i;

    sg[] = ;

    for(i=;i<=;i++)

        sg[i] = mex(i);

}

int main()

{

    int n,i,j,m,q,c,x,k;

    int cs = ;

    while(scanf("%d",&n)!=EOF)

    {

        printf("Case %d:\n",cs++);

        for(i=;i<;i++)

            v[i].clear();

        for(i=;i<n-;i++)

        {

            scanf("%d",&c);

            for(j=;j<c;j++)

            {

                scanf("%d",&x);

                v[n-i-].push_back(n-x);

            }

        }

        setSG();

        int res;

        scanf("%d",&q);

        while(q--)

        {

            scanf("%d",&m);

            res = ;

            while(m--)

            {

                scanf("%d",&k);

                res ^= sg[n-k];

            }

            if(res)

                puts("Alice");

            else

                puts("Bob");

        }

    }

    return ;

}

巴特西

2014 Super Training #6 A Alice and Bob --SG函数

最新文章

热门文章