CTS2024 D1T3 众生之门

· · 题解

通过跑暴力发现，我们总是可以构造一个排列，让每步的距离 \le 3。于是答案应当 \le 3。

又因为答案的奇偶性被唯一确定，所以只需要判断答案是 0/1 还是 2/3。

使用一下 n\le 10 的大样例会发现答案大部分情况为 0/1？然后观察一些特殊情况：

发现树是菊花时，任意排列都不会改变结果。

而在 n 很小的情况下，比如 1-2-3-4 的链，从 2 走到 3，这时也无法做到答案为 0 或 1。

大胆猜测，判掉 n 小的情况和树为菊花的情况，剩余情况答案都为 0 或 1。（在 n=10 时就已经成立了，于是只需要在 n\le 9 时跑暴力）

如何构造呢？构造全错了，随机化全对了。

发现有 (n-2)! 种排列，而只有 O(n) 种结果，解集范围很大。

每次随机一个排列，可以看作以 \frac{1}{2^k} 的概率抽取 [0,2^k) 中的一个数，期望随机 O(n) 次就能抽到 \le 1。

于是先随机一个排列，然后每次随机交换两个数，直到答案 \le 1。

然后就可以过了！！1