题解 P7999 [WFOI - 01] 翻转序列（requese）

· · 题解

题意

你有一个长度为 n 的排列，现在你可以选择一个数 x，你每次可以翻转一段长为 x+1 或一段长为 x-1 的子串。

请在 20 \times n 次内还原成 1\sim n 的序列。

部分分

对于 n \le 100 的部分，注意到上界非常松，直接用 x=3 解决。

假设我们已经将 1 到 u-1 的数归位，现在要处理 u。

每次，我们可以翻转长 x+1=4 的区间使 u 前移 x=3 格，最后剩下的部分可以用 x-1=2 的 swap 补齐。

次数约为 2n+\lfloor \frac{n}{3} \rfloor \times n \times \frac{1}{2}，足以拿到 50 分。

正解

我们从 n \le 100 的部分推广，现在认为序列足够长。

处理 u 的时候，同样先用 x+1 的翻转操作不断将 u 左移 x 格。

假设最后 u 的位置是 v \in (u,u+x)，这时我们需要特殊处理。

如果 u 和 v 奇偶性不同，我们可以用一次 [l,r] ,l > u 的翻转操作将其放到 u+x 上。

否则，我们可以操作 [v,v+x] 将 u 移到 v+x 上，使奇偶性正确，然后进行上述操作。

但上述操作对剩余位置的长度有要求，注意到 2x 的长度一定是足够的。

因此，我们取 x 为 \le n/4 的最大奇数。

方便起见，我们先用类似的操作处理序列的后半部分，使 \lceil \frac{n}{2} \rceil 到 n 归位，这时位置是足够的。

然后处理前半部分，然而虽然序列长度足够，但是后半部分已经处理好，不能够随意翻转。

注意到我们倒着做操作可以复原序列，运用这个性质，我们尝试交换 u 上和 v 上的值。

一个至关重要的操作是同时使用 x+1 和 x-1 可以仅交换 i 与 i+x 上的值。因此，当 u 已经位于 u+x 上时，直接用该操作交换，然后复原序列。

由于我们的操作 [l,r] 均保证 l > u，因而该过程不会出现冲突。

复原一个数的次数上界是 \lfloor \frac{n}{x} \rfloor +2 +1 +2，总和会带上约 1/2 的常数，理论上界不超过 5.5n，非常优秀。

代码实现时对 n \le 4 的情况进行了特判。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,a[N],x,y;
vector<pair<int,int> > op;
inline void oper(int u,int v){
    reverse(a+u,a+v+1);
    op.push_back(make_pair(u,v));
}
inline void prt(){
    for(int i=1;i<=n;i++) if(a[i]!=i){
        puts("wrong operations !!");
        exit(-1);
    }
    printf("%d\n",(int)op.size());
    for(auto u:op) printf("%d %d\n",u.first,u.second);
}
inline void force(){
    puts("3");
    for(int u=1,v;u<n;u++){
        for(v=u;v<=n;v++) if(a[v]==u) break;
        while((v-u)%3) oper(v-1,v),v--;
        while(v>u) oper(v-3,v),v-=3;
    }
    prt();
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    if(n<=4) force(),exit(0);
    x=n>>2;
    if(!(x&1)) x--;
    printf("%d\n",x);
    y=(x+1)>>1;
    //后半部分 
    for(int u=n,v;u>(n/2);u--){
        for(v=u;v;v--) if(a[v]==u) break;
        while(v+x<=u) oper(v,v+x),v+=x;
        if(v==u) continue;
        int l=u,r=u-x;
        if((l-v)&1) oper(v-x,v),v-=x;//同下 
        oper((v+r)/2-y+1,(v+r)/2+y);
        oper(r,r+x);
    }
    //前半部分 
    for(int u=1,v,rv;u<=(n/2);u++){
        for(v=u;v<=n;v++) if(a[v]==u) break;
        while(v-x>=u) oper(v-x,v),v-=x;
        if(v==u) continue;
        int l=u,r=u+x;rv=0;
        if((l-v)&1) oper(v,v+x),v+=x,rv=1;//调整奇偶性 
        oper((v+r)/2-y+1,(v+r)/2+y);//将 u 放到位置 u+x 上 
        oper(l,l+x);oper(l+1,l+x-1);//交换 u 和 u+x 上的值 
        oper((v+r)/2-y+1,(v+r)/2+y);//复原序列 
        if(rv) oper(v-x,v);//复原序列 
    }
    prt();
}