1561E - Bottom-Tier Reversals
题意
给定一个长度为n
(奇数)的排列a
,对a
进行若干以下操作,使得a
成一个递增数列。
操作描述:
- 选定一个值
p
(奇数),将子序列 [ a 1 , a 2 , . . , a p ] [a_1,a_2,..,a_p] [a1,a2,..,ap]反转,得到 a = [ a p , a p − 1 , . . . , a 2 , a 1 , a p + 1 , a p + 2 , . . , a n ] a=[a_p,a_{p-1},...,a_2,a_1,a_{p+1},a_{p+2},..,a_n] a=[ap,ap−1,...,a2,a1,ap+1,ap+2,..,an]。
将操作步骤输出(输出每次选定的p
),操作次数不能超过
5
n
2
\frac{5n}{2}
25n。
思路
因为 a . s i z e = n a.size=n a.size=n为奇数,并且反转的长度 p p p也是奇数,所以反转后奇偶性不变,如果 a [ i ] a[i] a[i]的奇偶性不等于 i i i的奇偶性,则一定无解(输出-1)。
将原数组还原:
如果 a n − 1 = n − 1 a_{n-1}=n-1 an−1=n−1并且 a n = n a_n=n an=n,则只需要考虑长度为 n − 2 n-2 n−2的排列如何反转。
我用图画了一下官方题解的描述,更容易理解一点。
红色框框表示需要反转的连续子序列
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3000;
int n, val[N];
int a, b, pos_a, pos_b;
vector<int> res;
void get_pos() { // 获取值a和b的下标
for (int i = 1; i <= n; i++) {
if (val[i] == a) pos_a = i;
if (val[i] == b) pos_b = i;
}
}
void solve(int v) { // 反转
res.push_back(v);
reverse(val + 1, val + 1 + v);
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
res.clear();
for (int i = 1; i <= n; i++) cin >> val[i];
bool k = true;
for (int i = 1; i <= n; i++)
if ((val[i] & 1) != (i & 1)) { // 奇偶性不同,-1
k = false;
break;
}
if (!k) {
cout << -1 << endl;
continue;
}
for (int i = n; i > 1; i -= 2) {
a = i, b = i - 1;
get_pos(); //反转之前要先拿到下标
solve(pos_a);
get_pos();
solve(pos_b - 1);
get_pos();
solve(pos_b + 1);
get_pos();
solve(3);
get_pos();
solve(a);
}
cout << res.size() << endl;
for (int x : res) {
cout << x << " ";
}
cout << endl;
}
return 0;
}