CF1558C Bottom-Tier Reversals 做题记录

给定一个长度为奇数的排列 $a_1, a_2, \dots, a_n$，你需要构造一组长度不超过的 $\frac 52 n$ 的操作序列 $s_1, s_2, \dots, s_k$，使得：

• $1 \le s_i \le n$，$s_i$ 为奇数；
• 按从前往后的顺序，对于每个 $s_i$，反转排列的前 $s_i$ 项，最后得到的排列中 $a_i = i$。

$1\le n\le 2021$，$1\le a_i\le n$。

首先由于每次翻转的长度都是奇数，所以并不会改变奇偶性，那么若 $a_i$ 和 $i$ 奇偶性不相同就是无解。

否则假设有解，考虑让 $i$ 和 $i+1$ 在一起（$i$ 是奇数），然后丢到后面来不对别的数造成影响，最后再整体翻转一次。由于操作次数是 $\frac{5}{2}n$，所以不难想到给每一对数 $5$ 次操作来还原。

这里给出一种构造方案：

1. 用一次操作把 $i$ 换到第一位；
2. 用一次操作把 $i$ 换到和 $i+1$ 相邻的位置；
3. 把 $i+1$ 换到第二个位置，这时 $i$ 在第三个位置；
4. 交换前三个位置，这样就可以让序列的前两个位置分别为 $i$ 和 $i+1$；
5. 把它们两个放到最后即可。

这样做每次只需要 $5$ 次操作即可把 $i$ 和 $i+1$ 换好。

最后整体倒过来就行，总操作次数刚好是 $\dfrac{5}{2}n$。