CF1558C Bottom-Tier Reversals 做题记录

给定一个长度为奇数的排列 a1,a2,,ana_1, a_2, \dots, a_n,你需要构造一组长度不超过的 52n\frac 52 n 的操作序列 s1,s2,,sks_1, s_2, \dots, s_k,使得:

  • 1sin1 \le s_i \le nsis_i 为奇数;
  • 按从前往后的顺序,对于每个 sis_i,反转排列的前 sis_i 项,最后得到的排列中 ai=ia_i = i

1n20211\le n\le 20211ain1\le a_i\le n

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

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

这里给出一种构造方案:

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

这样做每次只需要 55 次操作即可把 iii+1i+1 换好。

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