不完全考虑构造+dp与构造：1107T2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134274865

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

发现reverse操作会对一堆数进行修改，但如果我们只关注其中一些数呢？

假设我们已经构造好 [1,i−1][1,i-1] ，我们现在尝试构造 [i,n][i,n] ，我们可操作的范围是在 [i−1,n][i-1,n]

假设 ii 在 posipos_i ，我们其实要在一个长为 n−i+1n-i+1 的序列上把位置 posi−i+2pos_i-i+2 移到位置2，这个东西很dp。于是我们就设 dp(x,y)dp(x,y) 表示长为 xx ，从 yy 移到2的最小步数。

注意这个dp不一定需要最优的策略，也就是说我们可以贪心决策。我们可以枚举最后一个格子是否被选，或者选多少。然后我们贪心希望 yy 每次往前移。（往后移可能也可行，但我们找的是范围内的最优解，所以不需要）

然后这样子还是会略超，所以我们可以考虑继续完善贪心。我们可以维护从前往后指针 xx 和从后往前指针 yy ，取最优的取移。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#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
#define fi first
#define se second
//srand(time(0));
#define N 3010
//#define M
//#define mo
int rev[13][100010]; 
void revese(int n, int l) {
	for(int i=0; i<n; ++i) rev[l][i]=((rev[l][i>>1]>>1)|((i&1)<<l-1)); 
}
void Min(int &a, int b)  {
	a=min(a, b); 
}
struct Fe {
	int x, lstx, lsty, opx, opy; 
	Fe operator = (const int a)  {
		x=a;  return (*this); 
	}
}f[N][N], g[N][N];
Fe Min(Fe a, Fe b) {
	return a.x<b.x ? a : b; 
}
int n, m, i, j, k, T;
int a[N], pos[N]; 
vector<pair<int, int> >G; 

void init() {
	int x, y, l, t; 
	for(x=0; x<N; ++x) for(y=0; y<N; ++y) f[x][y].x=g[x][y].x=1e9; 
	for(x=3; x<=n; ++x) {
		for(y=2; y<x; ++y) {
			f[x][y]=f[x-1][y]; 
			if(y==2) f[x][y]=0; 
			for(k=1; (1<<k)<=x; ++k) {
				l=x-(1<<k)+1; 
				if(l>=y) continue; 
				t=y-l; 
//				debug("[%d][%d] %d %d\n", x, y, k, t); 
				if(rev[k][t]<t && f[x][l+rev[k][t]].x+1<f[x][y].x) {
					f[x][y].x=f[x][l+rev[k][t]].x+1; 
					f[x][y].lstx=x; f[x][y].lsty=l+rev[k][t]; 
					f[x][y].opx=l; f[x][y].opy=k; 
				}
			}
//			debug("f[%d][%d]=%d\n", x, y, f[x][y].x); 
		}
	}
	for(x=3; x<=n; ++x) {
		for(y=x-1; y>=2; --y) {
			g[x][y]=g[x-1][y-1]; 
			if(y==x-1) g[x][y]=0; 
			for(k=1; (1<<k)<=x; ++k) {
				if((1<<k)<y) continue; 
				t=y-1; 
				if(rev[k][t]>t && g[x][rev[k][t]+1].x+1<g[x][y].x) {
				debug(">>> %d || %d %d 【】 %d\n", k, rev[k][t], t, g[x][rev[k][t]+1].x); 
					g[x][y].x=g[x][rev[k][t]+1].x+1; 
					g[x][y].lstx=x; g[x][y].lsty=rev[k][t]+1; 
					g[x][y].opx=x; g[x][y].opy=k; 
				}
			}
			debug("g[%d %d] = %d\n", x, y, g[x][y].x); 
		}
	}
}

void work(int l, int k) {
	for(int i=0; i<(1<<k); ++i) 
		if(i<rev[k][i]) swap(a[i+l], a[rev[k][i]+l]); 
}

void remake_pos() {
	for(int i=1; i<=n; ++i) pos[a[i]]=i; 
}

signed main()
{
	freopen("butterfly.in", "r", stdin);
	freopen("butterfly.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	
	n=read(); m=read(); 
	for(i=0; i<=12; ++i) revese(1<<i, i); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	remake_pos(); 
	init(); 
	int x, y; 
	x=2; y=n-1; 
	while(x<y) {
		if(pos[x]==x) { ++x; continue; }
		if(pos[y]==y) { --y; continue; }
		int len=y-x+1; 
		int s1=f[len+2][pos[x]-x+2].x; 
		int s2=g[len+2][pos[y]-x+2].x; 
		debug("=== %d %d\n", s1, s2); 
		if(s1<s2) {
			debug("oper 1\n"); 
			auto t=f[len+2][pos[x]-x+2]; 
			while(t.opx) {
				G.pb({t.opx+x-2, t.opy}); work(t.opx+x-2, t.opy); 
				t=f[t.lstx][t.lsty]; 
			}
			++x; 
		}
		else {
			debug("oper 2\n"); 
			auto t=g[len+2][pos[y]-x+2]; 
			while(t.opx) {
				G.pb({y+2-t.opx, t.opy}); work(y+2-t.opx, t.opy); 
				t=g[t.lstx][t.lsty]; 
			}
			--y; 
		}
		remake_pos(); 
		for(int i=1; i<=n; ++i) debug("%d ", a[i]); debug("\n"); 
	}
		for(int i=1; i<=n; ++i) debug("%d ", a[i]); debug("\n"); 
	printf("%d\n", G.size()); 
	for(auto t : G) printf("%d %d\n", t.fi, t.se); 
	return 0;
}