P7400 [COCI2020-2021#5] Magenta 题解

Little_x_starTYJ · 2024-09-28 15:57:14 · 题解

解题思路

下文中的距离指的是 a,b 之间的边的数量。

Sub 2

即所有边 Paula 与 Marin 都可以行走。

根据题意 Paula 先手。因此，如果一开始 Paula 动不了，那么 Marin 胜。如果 Paula 动一次后 Marin 动不了，那么 Paula 胜。

除去这两种情况后，每当 Paula、Marin 分别动了一次，他们之间的距离要么不变，要么缩短 2 要么增长 2。

但是很明显，由于他们都会使用最优的走法，所以他们之间的距离不会增长（增长过后会变成平局，处于优势的人肯定不希望平局），所以他们之间的距离要么缩短 2 要么不变。

所以当 Paula 与 Marin 之间的距离为奇数时，最后，他们的距离会变成 1。接下来轮到 Paula，但由于对面有 Marin，所以他只能往后退，Marin 趁机逼近，最后 Marin 胜。

当距离为偶数时同理，Paula 胜。

Sub 3

在上面的基础上，我们不难发现 Sub 3 与 Sub 2 最大的不同就是可能存在安全区。

安全区就是只有 Paula 或者 Marin 能够到达的地方。

于是这个安全区至少由 3 个节点构成，假设 3 个节点的编号分别为 1, 2, 3 并且是 Paula 的安全区。那么不难发现 1 \to 2 这条边的颜色一定是蓝色。2\to 3 这条边只要不是红色就行。

所以我们不光要判断 Marin 与 Paula 之间的距离的奇偶，还要找到必不胜家的安全区。

在查找安全区时需要注意找到安全区后，可以获胜的人可能可以先到达，所以这个安全区实际上是没有用的。