poj 2425 A Chess Game 博弈论

思路:SG函数应用!!

代码如下:

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
int sg[],n;
vector<int>p[];
int dfs(int now)
{
if(sg[now]!=-) return sg[now];
bool vis[]={};
for(int i=;i<p[now].size();i++)
vis[dfs(p[now][i])]=;
int i=;
while(vis[i]) i++;
return sg[now]=i;
}
int main()
{
int a,b,q,k;
while(scanf("%d",&n)!=EOF){
memset(sg,-,sizeof(sg));
for(int i=;i<n;i++){
scanf("%d",&a);
p[i].clear();
for(int j=;j<a;j++){
scanf("%d",&b);
p[i].push_back(b);
}
}
while(scanf("%d",&q)&&q){
int ans=;
for(int i=;i<q;i++){
scanf("%d",&k);
ans^=dfs(k);
}
puts(ans?"WIN":"LOSE");
}
}
return ;
}
上一篇:poj 2425 A Chess Game_sg函数


下一篇:Java小坑