AcWing 1319. 移棋子游戏
原题链接
中等
作者:
acw_weian
,
2020-07-19 18:21:03
,
所有人可见
,
阅读 790
/**
* 该题目就是标准的SG函数的定义
* SG(X) = MEX( SG(a1) ^ SG(a2) ^ ... ^ SG(an) )
*/
import java.io.*;
import java.util.*;
class Main{
//N 表示图中节点总数,M 表示图中边的条数,K 表示棋子的个数
static int N = 2010, M = 6010, K = N;
static int[] cache = new int[N];
static Map<Integer, Set<Integer>> graph = new HashMap(N);
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static int sg(int x){
if(cache[x] != -1) return cache[x];
if(graph.get(x) == null ) return 0;
Set<Integer> set = new HashSet();
for(Integer next: graph.get(x)){
set.add(sg(next));
}
for(int i = 0; ; i ++){
if(!set.contains(i)){
cache[x] = i;
return i;
}
}
}
public static void add(int a, int b){
graph.putIfAbsent(a, new HashSet());
graph.get(a).add(b);
}
public static void main(String[] args) throws Exception{
String[] ss = read.readLine().split(" ");
Arrays.fill(cache, -1);
int n = Integer.valueOf(ss[0]), m = Integer.valueOf(ss[1]), k = Integer.valueOf(ss[2]);
for(int i = 0; i < m; i++){
ss = read.readLine().split(" ");
int a = Integer.valueOf(ss[0]);
int b = Integer.valueOf(ss[1]);
add(a, b);
}
ss = read.readLine().split(" ");
int res = 0;
for(int i = 0; i < k; i++){
res ^= sg(Integer.valueOf(ss[i]) );
}
if(res == 0) System.out.println("lose");
else System.out.println("win");
}
}