题解：CF1553E Permutation Shift

hh弟中弟 · 2024-11-12 19:22:10 · 题解

很久很久之前做的题，怀念一下那段美好时光顺带写个题解。\ 给了一个 m\le \frac{n}{3}，不觉得很神秘吗，来研究一下这里，首先有经典东西：每次交换最多可以改变两个数的位置。也就是说，有至多 2m 的数匹配不上移位，剩下至少 \frac{n}{3} 个数一定可以与移位匹配上，考虑找出这样的匹配位置来。\ 对于每一个位置都求出他需要的 k，只有个数大于等于 \frac{n}{3} 的 k 值才有可能是答案，换句话说，合法的 k 最多有 3 个，枚举并直接暴力检查交换次数是否不超过 m 就行了。\ 当然，最后的检验也可以不那么简单粗暴，一个排列到另一个排列的最小交换次数就等于 n 减去相应位置连边后的图的环数。证明就是最后一定全是自环，而每次交换可以把一个环变成两个，增加了一个环。