题解：P14972 『GTOI - 2C』Fliping

· · 题解

题目传送门

2026 年的第一篇题解。

题目大意

有一个长度为 n 的排列 a，每次可以翻转一个长度至少为 3 的区间，要经过不超过 3000 次操作使数组 a 单调递增。

思路

我们可以从头到尾依次判断是否正确，如果当前位不正确就要进行翻转，用一个队列存下答案。

这看似很容易解决，但是题目限制长度至少为 3，这就不太好解决了，我们先来思考一下如果不限制长度至少为 3 该如何解决。

我们先用一个数组 b 维护 a 的逆排列，由于当前扫到 i 时，一定 b_i\ge i，所以每一位只需要翻转 [i,b_i] 这个区间即可，我们轻松地写出代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[2010],b[2010],aa[2010];
queue<pair<int,int> >q;
void swp(int l,int r){
    q.push({l,r});
    for(int i=l;i<=r;i++)aa[i]=a[i];
    for(int i=l;i<=r;i++)a[i]=aa[r+l-i],b[a[i]]=i;
}
void A(int i){
    int p=b[i];
    swp(i,p);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==i)continue;
        else A(i);
    }
    cout<<q.size()<<"\n";
    while(q.size()){
        auto k=q.front();
        q.pop();
        cout<<k.first<<" "<<k.second<<"\n";
    }
    return 0;
}

这可以得到 20 分。

我们接下来思考如果长度至少为 3 如何解决。

  1. 如果当前位满足 b_i-i+1\ge 3，我们可以直接用上面讲的操作，直接翻转 [i,b_i]。
  2. 如果当前位满足 n-b_i+1\ge 3，我们可以先翻转 [b_i,n]，再翻转 [i,n]。
  3. 如果以上两点都不满足，这看起来有些难度，我们来举个例子试试看： 
    1 2 3 4 5 6 8 7 9

    我们先翻转 [4,7]，序列变为：

    1 2 3 8 6 5 4 7 9

    再翻转 [5,7]，序列变为：

    1 2 3 8 4 5 6 7 9

    然后翻转 [5,8]，序列变为：

    1 2 3 8 7 6 5 4 9

    最后翻转 [4,8]，序列变为：

    1 2 3 4 5 6 7 8 9

我们只需要依次翻转 [i-3,i],[i-2,i],[i-2,b_i],[i-3,b_i] 即可，如果当前 i\le3 无解，直接输出 -1 即可

现在，我们已经处理好了所有情况，操作次数自然不超过 3000。

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,a[2010],b[2010],aa[2010];
queue<pair<int,int> >q;
void swp(int l,int r){
    q.push({l,r});
    for(int i=l;i<=r;i++)aa[i]=a[i];
    for(int i=l;i<=r;i++)a[i]=aa[r+l-i],b[a[i]]=i;
}
void A(int i){
    int p=b[i];
    swp(i,p);
}
void B(int i){
    int p=b[i];
    swp(p,n);
    swp(i,n);
}
void C(int i){
    if(i<=3){
        cout<<-1;
        exit(0);
    }
    int j=i-3,p=b[i];
    swp(j,i);
    swp(j+1,i);
    swp(j+1,p);
    swp(j,p);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==i)continue;
        else if(b[i]-i+1>=3)A(i);
        else if(n-b[i]+1>=3)B(i);
        else C(i);
    }
    cout<<q.size()<<"\n";
    while(q.size()){
        auto k=q.front();
        q.pop();
        cout<<k.first<<" "<<k.second<<"\n";
    }
    return 0;
}