hdu 1524 A Chess Game 夜

http://acm.hdu.edu.cn/showproblem.php?pid=1524

博弈  用SG处理

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<algorithm>
#include<cmath>

using namespace std;
//#pragma comment(linker,"/STACK:1000000000,1000000000")

#define LL long long

const int N=1005;
const int M=100005;
int Nim[N];
int head[N];
int I,next[M],k[M];
void Add(int i,int j)
{
    k[I]=j;
    next[I]=head[i];
    head[i]=I++;
}
int dp(int x)//求x对应到Nim里的值
{
    if(Nim[x]!=-1)
    return Nim[x];
    bool had[N];
    memset(had,false,sizeof(had));
    for(int t=head[x];t!=-1;t=next[t])
    {
        had[ dp( k[t] ) ]=true;
    }
    for(int i=0;i<N;++i)
    {
        if(!had[i])//第一个到不了的值
        {Nim[x]=i;break;}
    }
    return Nim[x];
}
int main()
{
    //freopen("data.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(head,-1,sizeof(head));
        I=0;
        int m;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&m);
            while(m--)
            {
                int j;
                scanf("%d",&j);
                Add(i,j);
            }
        }
        memset(Nim,-1,sizeof(Nim));
        while(scanf("%d",&m),m)
        {
            int flag=0;
            while(m--)
            {
                int tmp;
                scanf("%d",&tmp);
                flag=(flag^dp(tmp));//S-Nim 异或
            }
            if(flag)
            printf("WIN\n");
            else
            printf("LOSE\n");
        }
    }
    return 0;
}