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$ 时的先手状态向前转移,具体过程如下:
- 定义 $\text{DFS}(v,now)$ 表示现在是 $now$ 的位置,玩家 $v$ 先手。
- 枚举上一次玩家 $u$ 的操作 $x$,那么可以从 $now-x$ 的位置转移到 $now$ 的位置(注意这里的 $now-x$ 不能等于 $1$)。
- 如果 $now$ 的位置是必败态,那么根据结论:能转移到必败态的状态就是必胜态,可以得到 $now-x$ 的位置是必胜态。
- 如果 $now$ 的位置是必胜态,那么根据结论:只能转移到必胜态的状态就是必败态。我们记 $cnt_{u,i}$ 表示在 $i$ 这个位置且 $u$ 先手可以转移到的必胜态数量。当 $cnt_{u,now-x}+1=k_u$ 时,意味着从 $(u,now-x)$ 转移到的所有状态都是必胜态,那么意味着从 $(u,now-x)$ 这个状态为必败态。
- 继续 $\text{DFS}(u,now-x)$ 进行转移即可。
时间复杂度:$O(n^2)$
Code
1 |
|