1319. 移棋子游戏
摘要
Title: 1319. 移棋子游戏
Tag: 博弈论、sg函数
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1319. 移棋子游戏
-
题意
给定一个有 N个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。
玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。
对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。 -
思路
类似于集合-NIM游戏，只不过有向图游戏，换成了连边的有向图
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43'''
Author: NEFU AB-IN
Date: 2023-03-23 20:36:19
FilePath: \Acwing\1319\1319.py
LastEditTime: 2023-03-23 20:46:55
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations
N = int(2e3 + 10)
INF = int(2e9)
f = [-1] * N
def sg(u): # 依然记忆化搜索
if f[u] != -1:
return f[u]
d = Counter()
for v in g[u]:
d[sg(v)] = 1
for i in range(INF):
if d[i] == 0:
f[u] = i
return i
g = [[] for _ in range(N)]
n, m, k = read()
for i in range(m):
x, y = read()
g[x].append(y)
res = 0
lst = list(read())
for i in lst:
res ^= sg(i)
print("win" if res != 0 else "lose")