给定一个长度为奇数的排列 ,你需要构造一组长度不超过的 的操作序列 ,使得:
- , 为奇数;
- 按从前往后的顺序,对于每个 ,反转排列的前 项,最后得到的排列中 。
,。
首先由于每次翻转的长度都是奇数,所以并不会改变奇偶性,那么若 和 奇偶性不相同就是无解。
否则假设有解,考虑让 和 在一起( 是奇数),然后丢到后面来不对别的数造成影响,最后再整体翻转一次。由于操作次数是 ,所以不难想到给每一对数 次操作来还原。
这里给出一种构造方案:
- 用一次操作把 换到第一位;
- 用一次操作把 换到和 相邻的位置;
- 把 换到第二个位置,这时 在第三个位置;
- 交换前三个位置,这样就可以让序列的前两个位置分别为 和 ;
- 把它们两个放到最后即可。
这样做每次只需要 次操作即可把 和 换好。
最后整体倒过来就行,总操作次数刚好是 。