题目链接
题意：给定一个有向无环图（DAG），上面放有一些旗子，旗子可以重合，两个人轮流操作，每次可以把一个旗子从一个位置移动到相邻的位置，无法移动时输，询问先手是否必胜。
这道题可以把每个旗子看作单独的一个游戏，那么所有这些旗子的状态SG值，就是这些旗子各自SG值的Xor和，可以记忆化搜索dfs，暴力算SG值判断即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
);
int n;
],X[],P[],tot;
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
];
int dfs(int x){
if(~sg[x]) return sg[x];
];
memset(nxt,,sizeof nxt);
for(int i=H[x];i;i=X[i]){
nxt[dfs(P[i])]=;
}
;;i++){
if(!nxt[i]){
return sg[x]=i;
}
}
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
while(~scanf("%d",&n)){
memset(H,,;
memset(sg,-,sizeof sg);
,x;i<n;i++){
scanf("%d",&x);
,y;j<x;j++){
scanf("%d",&y);
add(i,y);
}
}
int q;
while(scanf("%d",&q),q){
;
,x;i<q;i++){
scanf("%d",&x);
SG^=dfs(x);
}
if(SG) puts("WIN");
else puts("LOSE");
}
}
;
}