POJ 2425 A Chess Game(有向图SG函数)题解

题意:给一个有向图,然后个m颗石头放在图上的几个点上,每次只能移动一步,如果不能移动者败

思路:dfs打表sg函数,然后求异或和

代码:

#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define eps 1e-9
typedef long long ll;
const int maxn = + ;
const int seed = ;
const ll MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
using namespace std;
vector<int> G[maxn];
int in[maxn], n;
int s[maxn], sg[maxn];
void dfs(int u){
if(G[u].size() == ){
sg[u] = ;
return;
}
for(int i = ; i < G[u].size(); i++){
int v = G[u][i];
if(sg[v] == -)
dfs(v);
}
memset(s, , sizeof(s));
for(int i = ; i < G[u].size(); i++){
int v = G[u][i];
s[sg[v]] = ;
}
for(int i = ; i < maxn; i++){
if(!s[i]){
sg[u] = i;
return;
}
}
}
int main(){
while(~scanf("%d", &n)){
memset(in, , sizeof(in));
memset(sg, -, sizeof(sg));
for(int i = ; i <= n - ; i++){
int x, to;
G[i].clear();
scanf("%d", &x);
while(x--){
scanf("%d", &to);
G[i].push_back(to);
in[to]++;
}
}
for(int i = ; i <= n - ; i++){
if(!in[i]){
dfs(i);
}
}
int m;
while(scanf("%d", &m) && m){
int ans = , x;
while(m--){
scanf("%d", &x);
ans ^= sg[x];
}
if(ans == ) printf("LOSE\n");
else printf("WIN\n");
}
}
return ;
}
上一篇:bat安装python的msi包


下一篇:html5本地存储之localstorage 、本地数据库、sessionStorage简单使用示例