人生中的第二道紫题。。。
解题思路
下文中的距离指的是
a
,
b
a,b
a,b 之间的边的数量。
Sub 2
即所有边 Paula 与 Marin 都可以行走。
根据题意 Paula 先手。因此，如果一开始 Paula 动不了，那么 Marin 胜。如果 Paula 动一次后 Marin 动不了，那么 Paula 胜。
除去这两种情况后，每当 Paula、Marin 分别动了一次，他们之间的距离要么不变，要么缩短
2
2
2 要么增长
2
2
2。
但是很明显，由于他们都会使用最优的走法，所以他们之间的距离不会增长（增长过后会变成平局，处于优势的人肯定不希望平局），所以他们之间的距离要么缩短
2
2
2 要么不变。
所以当 Paula 与 Marin 之间的距离为奇数时，最后，他们的距离会变成
1
1
1。接下来轮到 Paula，但由于对面有 Marin，所以他只能往后退，Marin 趁机逼近，最后 Marin 胜。
当距离为偶数时同理，Paula 胜。
Sub 3
在上面的基础上，我们不难发现 Sub 3 与 Sub 2 最大的不同就是可能存在安全区。
安全区就是只有 Paula 或者 Marin 能够到达的地方。
于是这个安全区至少由
3
3
3 个节点构成，假设
3
3
3 个节点的编号分别为
1
,
2
,
3
1, 2, 3
1,2,3 并且是 Paula 的安全区。那么不难发现
1
→
2
1 \to 2
1→2 这条边的颜色一定是蓝色。
2
→
3
2\to 3
2→3 这条边只要不是红色就行。
所以我们不光要判断 Marin 与 Paula 之间的距离的奇偶，还要找到必不胜家的安全区。
在查找安全区时需要注意找到安全区后，可以获胜的人可能可以先到达，所以这个安全区实际上是没有用的。