CF1561E 题解

link

给定长度为奇数 $n$ 的 $1$ 到 $n$ 的排列 $a$，要求找出一种长度不超过 $\dfrac{5n}{2}$ 的操作序列，使 $a$ 变为升序，或判断无解。操作如下：

• 选择一个 $x \in [1,n]$，且 $x$ 为奇数，将 $a_1$ 到 $a_x$ 翻转。

$3 \le n \le 2021$ 且为奇数，$1 \le a_i \le n$。

首先怎么判断无解，因为 $x$ 是奇数，所以翻转操作不改变位置的奇偶性，所以有解的充要条件是 $i$ 和 $a_i$ 的奇偶性都相同。

考虑将两个数绑到一起且倒着操作，比如 $n$ 和 $n-1$ 一起操作，这样相当与每对数要在五次操作内移动到最后的位置。

我们假设现在考虑的数位置为 $x$ 和 $y$，$x$ 要移到位置 $m$，操作 $F(x)$ 表示前 $x$ 的翻转操作，以下给出方案：

1. $$x=1,y=2:F(m)$$
2. $$y + 1 = y:F(x), \rightarrow 1.$$
3. $$x + 1 = y:F(y+1), \ F(y + 2 - x),\rightarrow 1.$$
4. $$x + 1 < y:F(x),F(y - 1)\rightarrow 2.$$
5. $$y + 1 < x:F(x),F(x - y)\rightarrow 2.$$

很不优的构造 /kk，时间复杂度 $O(n^2)$。

CODE

#include <bits/stdc++.h>
using namespace std;
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define N 2040
 
int n, a[N];
vector<int> res;
 
int can(int n) {
    for (int i = 1; i <= n; i ++) {
        if ((i & 1) != (a[i] & 1)) return false;
    }
    return true;
}
 
int check(int x) {
    for (int i = 1; i <= x; i ++) {
        if (i != a[i]) return false;
    }
    return true;
}
 
void F(int x) {
    res.emplace_back(x);
    reverse(a + 1, a + x + 1);
}
 
signed main() {
    for (int T = read(); T --;) {
        res.clear();
        n = read();
        for (int i = 1; i <= n; i ++) a[i] = read();
        if (!can(n)) { puts("-1"); continue; }
        while (!check(n)) {
            int x, y;
            for (int i = 1; i <= n; i ++) {
                if (a[i] == n) x = i;
                if (a[i] == n - 1) y = i;
            }
            if (x == n && y == n - 1) { n -= 2; continue; }
            if (x + 1 < y) F(x), F(y - 1), x = y - 1;
            if (y + 1 < x) F(x), y = (x + 1 - y), F(y - 1), x = y - 1;
            if (x + 1 == y) F(y + 1), x = (y + 2 - x), F(x);
            else F(x);
            F(n), n -= 2;
        }
        printf("%d\n", res.size());
        for (auto x : res) printf("%d ", x);
        if (res.size()) puts("");
    }
    return 0;
}