题意：给出一个长为$N$的排列，有两种操作：$A$：将最后一个数字放到第一个；$B$：将第三个数字放到第一个。一次性使用某种操作$k$次写作$kA$或$kB$，其中在$kA$中$k < N$，在$kB$中$k < 3$。请给出一种方案使得序列变为$1,2,3...N$。$N \leq 2000$
一道比较难的构造题
我们考虑增量构造：假如我们已经将$1-i$排好了，如何将$i+1$排到它们后面。我们可以进行如下操作：
$1.$通过若干$A$操作将$i+1$放到序列开头的位置
$2.$重复$2A,1B$操作将$i$与$i+1$之间不必要的数字两两踢到$i+1$后面
$3.$如果序列最后还有一个多余的数字，使用$1A,2B$操作将它踢到$i+1$后面
这样$i$与$i+1$就能相连了。
但是当我们需要将$n-1$接上时，会有一些问题：
我们考虑这样的一个序列：$$n-1,1,2,3...n-2,n$$
如果我们使用$1A,2B$操作，$n$就会夹在$1$和$2$中间，打乱了我们之前排好的顺序。所以当我们需要排$n-1$和$n$时，这种方法是不可行的。不妨考虑另外一种构造方法。
我们将$n$移到第一个，也就是$$n,n-1,1,2,3...n-2$$
然后我们使用一次$2A,1B$操作，然后序列就变成了……
$$n,n-3,n-2,n-1,1,2,3...n-4$$
发现$n$的位置没有变，但是后面$n-1$个数在循环。那么我们不断重复该操作，直到序列变成$$n,1,2,3...n-2,n-1$$就行了。但实际上在当前情况下当$n$为奇数的时候是不可行的，因为在移动若干次之后，序列会变成$$n,2,3,4...n-1,1$$，再一次重复该操作又会把$n-1$踢到前面去了。
可以发现所有操作都是$O(n)$级别的，总操作次数是$O(n^2)$级别的，与题设刚好一致
稍微注意一下输出
关于序列移动的模拟操作建议使用链表。如果比较懒，可以使用STL中的deque，开O2的情况下效率还是比较优秀的（不开O2是最慢的）
下面的代码：O2 497ms，无O2 2146ms
#include<bits/stdc++.h>
#define MAXN 5000010
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
char done[MAXN] , allDone[MAXN];
int step[MAXN] , allStep[MAXN] , pot[MAXN] , N , cnt;
deque < int > now;
inline void moveA(int s){
if(done[cnt] != 'a')
done[++cnt] = 'a';
step[cnt] += s;
; i <= s ; i++){
now.push_front(now.back());
now.pop_back();
}
}
inline void moveB(int s){
if(done[cnt] != 'b')
done[++cnt] = 'b';
step[cnt] += s;
; i <= s ; i++){
];
now[] = now[];
now[] = now[];
now[] = p;
}
}
inline void output(){
;
; i <= cnt ; i++)
if(done[i] != allDone[i]){
)){
allDone[++calc] = done[i];
allStep[calc] = step[i];
}
}
else
))
allStep[i] = (allStep[i] + step[i]) % (done[i] == );
else
allDone[calc--] = ;
cout << calc << endl;
; i <= calc ; i++)
cout << allStep[i] << allDone[i] << ' ';
}
int main(){
N = read();
; i <= N ; i++)
now.push_back(read());
){
putchar(');
;
}
else
){
cout << (now[] == ? " : "1\n1a");
;
}
; i < N - ; i++){
; j < N ; j++)
if(now[j] == i){
if(j)
moveA(N - j);
break;
}
] != i - )
] != i - ){
moveA();
moveB();
}
else{
moveA();
moveB();
}
}
; i < N ; i++)
if(now[i] == N){
if(i)
moveA(N - i);
break;
}
] == N - ){
){
puts("NIE");
;
}
] != N - ){
moveA();
moveB();
}
}
moveA(N - );
output();
;
}