题解：P7015 [CERC2013] Crane

Freezyfish · 2026-08-08 14:49:03 · 题解

考场神秘 T1。

思路

看到数据范围，猜测操作次数是 O(n\log n) 的。

考虑每次暴力取移动元素，操作次数 O(n^2) 级别。

考虑从大到小去移动每个元素到他该到的位置。

对于元素 i，假设她现在的位置是 x。

• 如果 x>\lfloor\frac{i}{2}\rfloor，那么他是可以以 i 为右区间右端点，x 为左区间右端点进行一次操作的。
• 如果 x\leq\lfloor\frac{i}{2}\rfloor，是无法像上面一样操作，因为她的左区间长度不够。此时你只需要想办法让他移到满足上一种情况就行。咋移？贪心的想肯定反转最长的，也就是以 1 为左区间左端点，x 为左区间操作。直到 x>\lfloor\frac{i}{2}\rfloor。复杂度是什么？每次操作相当于倍长长度，所以只会做 O(\log) 次。

另外每次操作完后，你要更新其他位置信息。

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int read()
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
} 
const int N=1e5+15;
int n;
int a[N];
int pos[N];
vector<pair<int,int> >ans;
signed main() 
{
    //freopen("Apocalypse.in","r",stdin);
    //freopen("Apocalypse.out","w",stdout);
    int t=read();
    while(t--)
    {
        ans.clear();
        n=read();
    for(int i=1;i<=n;i++)a[i]=read(),pos[a[i]]=i;
    for(int i=n;i>=1;i--)
    {
        int k=pos[i];
        int len=i;
        while(k<=len/2)
        {
            for(int j=1;j<=k;j++)
            {
                swap(a[j],a[j+k]);
                pos[a[j]]=j;
                pos[a[j+k]]=j+k;
            }
            //cout<<1<<"--\n";
            ans.push_back({1,k*2});
            k<<=1;
        }
        //cout<<pos[i]<<" "<<len<<"\n";
        if(k==len)continue;
        ans.push_back({k-(len-k)+1,len});
        for(int j=k-(len-k)+1;j<=k;j++)
        {
            swap(a[j],a[j+len-k]);
            pos[a[j]]=j;
            pos[a[j+len-k]]=j+len-k;
        }
    }
    printf("%d\n",(int)ans.size());
    for(auto tmp:ans)
    {
        printf("%d %d\n",tmp.first,tmp.second);
    }
    }

    return 0;
}