「Codeforces 786A」Berzerk

Description

题目链接:Codeforces 786A

Rick 和 Morty 在玩一个版本的 Berzerk 游戏。这个游戏需要很大的空间,所以他们使用电脑玩这个游戏。

游戏中有 $n​$ 个标号从 $1\sim n​$ 的物体围成一个圆圈(顺时针标号), 物体 $1​$ 表示黑洞,其它物体表示星球,且某一个星球上有一个怪物,Rick 和 Morty 不知道这个怪物在哪个星球上,只知道这个怪物在游戏开始时没有进入黑洞。但就目前而言,他们希望为每种可能的情况做好准备。

Rick 和 Monty 每人有一个数的集合,集合中的数在 $[1,n-1]$ 之间。Rick 的集合是 $s_1$,其中有 $k_1$ 个数,Morty 的集合是 $s_2$,其中有 $k_2$ 个数。 游戏开始后,两人轮流操作。在操作中,玩家必须从他的集合中选出一个数 $x$, 怪物将从当前位置顺时针移动 $x$ 个位置,如果怪物移动后进入了黑洞,则该玩家获胜。

你的任务是对于每一个怪物的位置以及玩家先后手顺序,判断游戏先手获胜、后手获胜、无限循环。(每个玩家都采取最优操作)

数据范围:$2\le n\le 7000$,$1\le k_1,k_2\le n-1$,$1\le s_{i,j}\le n-1$


Solution

博弈论有一个经典的结论:

能转移到必败态的状态就是必胜态,只能转移到必胜态的状态就是必败态。

现在我们知道 $1$ 是必败态,那么我们通过 $\text{DFS}$ 可以判断每个点的胜负情况、是否有解。

我们考虑逆向思维,对每个玩家在 $1$ 时的先手状态向前转移,具体过程如下:

  1. 定义 $\text{DFS}(v,now)$ 表示现在是 $now$ 的位置,玩家 $v$ 先手。
  2. 枚举上一次玩家 $u$ 的操作 $x$,那么可以从 $now-x$ 的位置转移到 $now$ 的位置(注意这里的 $now-x$ 不能等于 $1$)。
  3. 如果 $now$ 的位置是必败态,那么根据结论:能转移到必败态的状态就是必胜态,可以得到 $now-x$ 的位置是必胜态。
  4. 如果 $now$ 的位置是必胜态,那么根据结论:只能转移到必胜态的状态就是必败态。我们记 $cnt_{u,i}$ 表示在 $i$ 这个位置且 $u$ 先手可以转移到的必胜态数量。当 $cnt_{u,now-x}+1=k_u$ 时,意味着从 $(u,now-x)$ 转移到的所有状态都是必胜态,那么意味着从 $(u,now-x)$ 这个状态为必败态。
  5. 继续 $\text{DFS}(u,now-x)​$ 进行转移即可。

时间复杂度:$O(n^2)​$


Code

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
#include <cstdio>
#include <algorithm>

const int N=7e3+5;
int n,k[2],a[2][N],cnt[2][N];
bool vis[2][N],win[2][N];

void dfs(int v,int now) {
if(vis[v][now]) return;
vis[v][now]=1;
int u=v^1;
for(int i=1;i<=k[u];++i) {
int pre=(now-a[u][i]+n-1)%n+1;
if(pre==1) continue;
if(!win[v][now]) {
win[u][pre]=1;
dfs(u,pre);
} else if(++cnt[u][pre]==k[u]) {
win[u][pre]=0;
dfs(u,pre);
}
}
}
int main() {
scanf("%d",&n);
for(int o=0;o<=1;++o) {
scanf("%d",&k[o]);
for(int i=1;i<=k[o];++i) scanf("%d",&a[o][i]);
}
dfs(0,1),dfs(1,1);
for(int o=0;o<=1;++o) {
for(int i=2;i<=n;++i) {
printf("%s%c",vis[o][i]?win[o][i]?"Win":"Lose":"Loop"," \n"[i==n]);
}
}
return 0;
}
0%