排列置换环上构造：1025T3

http://cplusoj.com/d/senior/p/SS231025C

排列构造的新知识：上置换环！

我们发现朴素做法是 $n^2$ 级别的，但数据范围希望我们是 $\frac{n^2}{2}$ 级别的。我们发现我们暴力复制序列显得非常蠢，因为很多序列前后我们其实可以考虑合并。

至于怎么合并？我们直接维护指针。然后我们现在要“运”东西到相应位置。而“运”东西的期望步数是 $\frac{n}{2}$ 的。

然后这个证明直接上置换环。我们相当于一个个置换环来搞。而置换环个数的期望是 $\ln$ 个.

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 1010
//#define M
//#define mo
int n, m, i, j, k, T;
int a[N], b[N], p; 
vector<int>ans; 

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
		freopen("yacolorful.in", "r", stdin);
	freopen("yacolorful.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); 
	for(i=1; i<=n; ++i) a[i]=read(), ans.pb(i), b[i]=i; 
//	printf("%d\n", n); 
//	for(i=1; i<=n; ++i) printf("%d ", a[i]); printf("\n"); 
	for(p=2; ; ++p) {
		if(p==n+1) p=2; 
		if(b[1]!=a[1]) {
			if(a[p]==b[1]) swap(b[1], b[p]); 
		}
		else  {
			if(a[p]!=b[p]) k=0, swap(b[1], b[p]); 
			else ++k; 
		}
		ans.pb(b[p]); 
		if(k>n) break; 
	}
	while(p+1<=n) ans.pb(b[p+1]), ++p; 
	for(i=1; i<=n; ++i) ans.pb(a[i]); 
	printf("%d\n", ans.size()); 
	for(auto t : ans) printf("%d ", t); 
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52