P14972 『GTOI - 2C』Fliping
题目描述
给出一个1 ∼ n 1\sim n1∼n的排列a aa，请问能否通过不超过3000 30003000次操作使数组a aa单调递增。
对于每次操作，你可以翻转一个长度至少为3 \bm33的区间。
其中，“翻转”指的是：例如数组a = { 5 , 4 , 3 , 2 , 1 } a = \{5,4,3,2,1\}a={5,4,3,2,1}，翻转区间是[ 2 , 4 ] [2,4][2,4]的话，结果是a = { 5 , 2 , 3 , 4 , 1 } a = \{5,2,3,4,1\}a={5,2,3,4,1}。
如果可以，输出一种构造方案，具体请参考【输出格式】。
如果不可以，输出-1。
输入格式
输入共两行。
第一行，一个正整数n nn。
第二行，一个1 ∼ n 1\sim n1∼n的排列a aa。
输出格式
如果存在构造方案：
- 输出一个非负整数m mm表示总共需要操作的次数。
- 然后输出m mm行，每行两个正整数l , r l,rl,r表示每次翻转的区间[ l , r ] [l,r][l,r]。
本题使用 Special Judge ，若有多组构造方案，任意输出一组即可。
如果不存在构造方案，输出-1即可。
输入输出样例 #1
输入 #1
5 2 5 4 3 1输出 #1
3 1 4 1 3 1 5说明/提示
【数据范围】
本题采用捆绑测试。
对于100 % 100\%100%的数据，保证1 ≤ n ≤ 2000 1\leq n\leq 20001≤n≤2000，{ a } \{a\}{a}为1 ∼ n 1\sim n1∼n的排列。
| Subtask \text{Subtask}Subtask | n ≤ n \leqn≤ | 特殊性质 | 分数 |
|---|---|---|---|
| 1 11 | 7 77 | 无 | 20 2020 |
| 2 22 | 50 5050 | ^ | 10 1010 |
| 3 33 | 1000 10001000 | ^ | 10 1010 |
| 4 44 | 1500 15001500 | ^ | 10 1010 |
| 5 55 | 2000 20002000 | 保证a i a_iai随机生成 | 10 1010 |
| 6 66 | ^ | 保证a i ≡ i ( m o d 2 ) a_i\equiv i\pmod 2ai≡i(mod2) | 20 2020 |
| 7 77 | ^ | 无 | 20 2020 |
思路
直接每次行则立刻转，否则转最后再转即可，然后<=5时特判一下。
代码见下
#include<bits/stdc++.h>usingnamespacestd;longlongn,a[2005];structone{longlongl,r;};vector<one>v;intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1,k;i<=n;i++){for(intj=i;j<=n;j++){if(a[j]==i){k=j;break;}}if(i==k){continue;}if(k-i>=2){v.push_back({i,k});for(intj=i;j<=(i+k)/2;j++){swap(a[j],a[i+k-j]);}}elseif(n-k>=2){v.push_back({k,n});for(intj=k;j<=(k+n)/2;j++){swap(a[j],a[k+n-j]);}v.push_back({i,n});for(intj=i;j<=(i+n)/2;j++){swap(a[j],a[i+n-j]);}}else{if(k==n){if(n<=4){cout<<-1<<endl;return0;}else{v.push_back({n-4,n-1});v.push_back({n-3,n-1});v.push_back({n-4,n});v.push_back({n-4,n-1});cout<<v.size()<<endl;for(intj=0;j<v.size();j++){cout<<v[j].l<<" "<<v[j].r<<endl;}return0;}}else{if(a[n]==n){if(n<=5){cout<<-1<<endl;return0;}else{n--;v.push_back({n-4,n-1});v.push_back({n-3,n-1});v.push_back({n-4,n});v.push_back({n-4,n-1});cout<<v.size()<<endl;for(intj=0;j<v.size();j++){cout<<v[j].l<<" "<<v[j].r<<endl;}return0;}}else{if(n<=5){cout<<-1<<endl;return0;}else{v.push_back({n-2,n});n--;v.push_back({n-4,n-1});v.push_back({n-3,n-1});v.push_back({n-4,n});v.push_back({n-4,n-1});cout<<v.size()<<endl;for(intj=0;j<v.size();j++){cout<<v[j].l<<" "<<v[j].r<<endl;}return0;}}}}}cout<<v.size()<<endl;for(intj=0;j<v.size();j++){cout<<v[j].l<<" "<<v[j].r<<endl;}return0;}
