ARC110F Esoswap 解题报告

ARC110F Esoswap 解题报告：

题意

给定一个位置与值域均为 \([0,n-1]\) 排列 \(p\)，可以多次操作，对 \(x\) 操作可以交换 \(p_x\) 与 \(p_{(x+p_x)\bmod n}\)，在 \(2\times 10^5\) 次操作内将排列排序。

\(1\leqslant n\leqslant 100\)。

分析

小清新（？）题。

考虑将序列转为降序排列，再转为升序排列。（我也不知道我咋想到的）

先考虑降序排列转为升序排列，可以增量法，每次维护一个升序后缀 \((i,n)\)，将 \(1\) 所在的位置放到序列的最后面，然后将 \(i\) 与 \(1\) swap（因为 \(i\) 的位置为 \(n-i-1\)），然后再把 \(1\) 和后面的 \(0\) swap 即可。

算一下操作次数，是 \(\sum (n-i-2+1+1)=\frac{n(n-1)}{2}\) 次。

然后是把普通排列转为降序排列。

考虑仍然维护一个降序后缀 \((i,n)\)，每次不断操作位置 \(i\) 直到其值为 \(n-i-1\)，由于一次操作一定不会跳到

由于一个位置上每种数字只会出现一次（在操作这个位置之前之后这个位置都不会被影响，而操作的时候每个数字都最多会被移动一次，不可能到能回来），而且合法的值 \(x\) 一定满足 \(n-x-1\) 小于等于位置，于是操作次数上界应该是 \(\frac{n(n+1)}{2}\)。

于是总操作次数是严格 \(n^2\) 的，时间复杂度与其同阶。

代码

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=105;
int n;
int a[maxn];
vector<int>ans;
void solve(int x){
	ans.push_back(x),swap(a[x],a[(x+a[x])%n]);
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=n-1;i>=0;i--)
		while(a[i]!=n-i-1)
			solve(i);
	for(int i=n-1;i>=0;i--){
		for(int j=i+1;j<n-1;j++)
			solve(j);//move 1
		solve(i);//swap i 0
		solve(i);//swap 1 0
	}
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++)
		printf("%d\n",ans[i]);
	return 0;
}