自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:55:47，当前版本为作者最后更新于2024-03-06 12:22:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

通过跑暴力发现，我们总是可以构造一个排列，让每步的距离 $\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