自动搬运

查看原文

来自洛谷，原作者为

	wlxhkk After all, tomorrow is another day

搬运于2025-08-24 22:35:03，当前版本为作者最后更新于2023-05-12 16:40:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

你有一个长度为 $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();
}