P7400 题解

P7400，一个有趣的博弈论。
下面称 Paula 和 Marin 都执行一轮操作的“一整轮”为一个周期。

Sub 1：\(n\le 100\)

我们采用 \(O(n^2\times n)=O(n^3)\) 的 DP 即可。这里略去具体实现。

Sub 2：边的颜色均为洋红

这意味着两人都可以走过任意一条边。考虑两方如何对对方进行“围追堵截”，我们不难发现：若起初两者之间连边为奇数，则先手胜，否则后手胜。这可以用简单的搜索得到结果，时间复杂度 \(O(n)\)。

Sub 3：无特殊限制

Sub 3 与 Sub 2 的主要区别在于，既然有些边不能通过，那这意味着有可能存在这样一种情况，使得围追堵截的那个人（无论是 Paula 还是 Marin ）可能无法通过必经过的边，从而被迫陷入平局。

因为路径长度的奇偶性已经确认了某个玩家绝不会赢，因此我们直接考虑平局的情况，即存在某一条边，使得此玩家可以到达这条边的顶点，而且对方到达不了。如果对方本来是必胜的，那么由于边的限制，这种局面一定平局。

否则不存在这样的一条边，那么此玩家无论怎么走，都是一个对方能够到达的点，这样对方总能获胜。

这也可以用朴素的搜索来解决。时间复杂度 \(O(n)\)。

代码略了。