AIOJ

给出一种可能并没有正确性的做法，但是的确可以通过。

我懒得想怎么 hack 了。

有会 hack 的可以尝试。

考虑先离散化，注意，相等的数可以随意钦定成不同的数，其实这一步和逆序对奇偶性有关。

这样离散化成一个排列。

对于一个数 $i$ 从 $1$ 到 $n$ ，如果它的位置不在 $n$ ，我就先操作 $i$ ，然后再操作 $i+1$ 。这样一直进行下去会在左边形成一个下降段。当碰到 $i$ 的位置在 $n$ 的时候，直接操作 $n$ ，现在的情况就相当于原来的 reverse，后面操作同理。

经过上述操作有可能变成递增或递减序列。

如果是递减序列，我们在开始时随机扰动一下然后在做即可。

上述操作直接做是平方的，但是注意到每次操作其实就是两个循环移位，而当前 $i$ 已经没用了可以抛弃，于是可以直接让最后一个数占据 $i$ 的位置，手画一下这个是正确的。容易 $O(n)$ 维护。

#include<bits/stdc++.h>
using namespace std;
int t;
const int nn=1e5+5;
int n,bf[nn],a[nn];
unsigned int mod=1e9;
mt19937 rnd(time(0));
int f(){
	unsigned int sb=rnd()%mod+1;
	return sb;
}
#define pb push_back
vector<int> res;
int p[nn],pos[nn];
bool cmp(int l1,int l2){
	return bf[l1]<bf[l2];
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>bf[i],p[i]=i;
		sort(p+1,p+n+1,cmp);
		int wz=0;
		for(int i=1;i<n;i++){
			if(bf[p[i]]==bf[p[i+1]]){
				wz=i;
				break;
			}
		}
		for(int tt=1;tt<=30;tt++){
			int x=f()%n+1;
			if(wz) swap(p[wz],p[wz+1]);
			for(int i=1;i<=n;i++) a[p[i]]=i;
			res.clear();
			if(tt>1){
				res.pb(x);
				if(x-1>=1) reverse(a+1,a+x);
				if(x+1<=n) reverse(a+x+1,a+n+1);
			}
			if(tt>20){
				x=f()%n+1;
				res.pb(x);
				if(x-1>=1) reverse(a+1,a+x);
				if(x+1<=n) reverse(a+x+1,a+n+1);
			}
			for(int i=1;i<=n;i++) pos[a[i]]=i;
			int fl=0;
			for(int i=1;i<=n;i++){
				int r=n-i+1;
				if(pos[i]==r){
					if(fl==0) res.pb(n);
					else res.pb(1);
					fl^=1;
				}
				else{
					if(fl==0) res.pb(pos[i]+i-1),res.pb(pos[i]+i);
					else res.pb(n-pos[i]-(i-1)+1),res.pb(n-pos[i]-(i-1));
					pos[a[r]]=pos[i];
					a[pos[i]]=a[r];
				}
			}
			if(fl){
				cout<<res.size()<<"\n";
				for(int v:res) cout<<v<<" ";
				cout<<"\n";
				break;
			}
			if(tt==30) cout<<-1<<"\n";
		}
	}
	return 0;
}

神秘随机化做法

评论