自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 22:29:29，当前版本为作者最后更新于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 之间的距离的奇偶，还要找到必不胜家的安全区。

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