POJ 2425 A Chess Game#树形SG

http://poj.org/problem?id=2425

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; struct node
{
int to,next;
}e[10000010];
int head[1010],Ecou;
int sg[1010]; void add_edge(int u,int v)
{
e[Ecou].to=v;
e[Ecou].next=head[u];
head[u]=Ecou++;
} int getsg(int n)
{
if(sg[n]!=-1)
return sg[n]; bool vis[1010];
memset(vis,0,sizeof(vis));
for(int i=head[n];i>=0;i=e[i].next)
{
sg[e[i].to]=getsg(e[i].to);
vis[sg[e[i].to]]=1;
}
for(int i=0;;i++)
if(!vis[i])
return sg[n]=i;
} int main()
{
int n;
while(~scanf("%d",&n))
{
memset(head,-1,sizeof(head));
Ecou=0;
int num,a;
for(int i=0;i<n;i++)
{
scanf("%d",&num);
while(num--)
{
scanf("%d",&a);
add_edge(i,a);
}
}
memset(sg,-1,sizeof(sg));
while(1)
{
int m,x,ans=0;
scanf("%d",&m);
if(!m) break; while(m--)
{
scanf("%d",&x);
ans^=getsg(x);
}
if(ans) printf("WIN\n");
else printf("LOSE\n");
}
}
return 0;
}
上一篇:Vue 加载外部js文件


下一篇:阿里云部署安装redis无法访问