P14972 『GTOI - 2C』Fliping题解

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的排列。

思路

直接每次行则立刻转，否则转最后再转即可，然后<=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;}