P3516 [POI2011]PRZ-Shift

(Updated: )
oi

Description

题目链接：P3516

给定一个长度为 $n$ 的排列，有两种操作：

  • (a) 将最后一个数移到最前面。
  • (b) 把第三个数移到最前面。

连续 $k$ 个操作可以合并成一块，表示为 $ka$ 或 $kb$，要求输出一个长度小于 $n^2$ 操作序列使得进行操作后排列变为 $1,2,3,\dots,n$。

无解输出 NIE。

$1\leq n \leq 2000$

Solution

这里提供一个船新做法，可能会跑得快点。

考虑在前 $i-1$ 个数字已经有序排列的情况下，如何把数 $i$ 移动到第 $i$ 个位置。

  • 第 $i$ 个数字已经在第 $i$ 个位置了，那么不需要动。
  • 第 $i$ 个数字必定在第 $j$ 个位置，其中 $j>i$，那么可以先把第 $i$ 个数字移动到位置 $1$，然后每次执行 $2$ 次 a，再做一次 b，这样不断往复就可以把前 $i-1$ 个数字移动到最末尾，此时再做 $i-1$ 次 a 即可。

然后最后可能会尴尬的剩下两个数，比如说下面的数据：

1
2
8
1 2 3 4 5 6 8 7

我们发现：可以做两次 a，然后再做一次 b，即可实现将一个数向左移动两个单位，那么针对上面的数据，如果 $n$ 是奇数，肯定无解，如果是偶数，可以用上面的规律移动即可。

然后细节可能有点多，需要细心点。

Code

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2010;
int n,a[N<<1],b[N],s[5],p[N<<1],h;
#define P pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<P> Ans,F;
I void Move(CI t,CI x){//模拟移动，把他拉成一个环，做到 O(1) 模拟。
    RI i;if(t==1) (h+=n-x)%=n;
    else{
        for(i=3-x+1;i<=3;i++) p[i-(3-x)]=a[h+i];for(i=1;i<=3-x;i++) p[x+i]=a[h+i];
        for(i=1;i<=3;i++) a[h+i]=p[i];for(i=1;i<=3;i++) a[(h+n+i)%(2*n)]=p[i];
    }
}
int main(){
    RI i,j,k,t;for(read(n),i=1;i<=n;i++) read(a[i]),b[i]=a[i];for(i=n+1;i<=2*n;i++) a[i]=a[i-n];
    for(i=1;i<=n-2;i++){
        for(j=1;j<=n;j++) if(a[h+j]==i) break ; 
        if(j==i) continue ;
        k=i-1,!k&&(k=n),t=0;if(j>1) Ans.push_back(MP(1,n-j+1)),k+=n-j+1,Move(1,n-j+1);
        k%=n,!k&&(k=n),swap(j,k);W(j+2<=n) Ans.push_back(MP(1,2)),Move(1,2),Ans.push_back(MP(2,1)),Move(2,1),j+=2,t++;
        if(j+1<=n) Ans.push_back(MP(1,1)),Move(1,1),Ans.push_back(MP(2,2)),Move(2,2),j++,t++;//注意判断边界
        Ans.push_back(MP(1,i-1)),Move(1,i-1);
    }for(i=n-1;i<=n;i++) s[i-(n-2)]=a[h+i]-(n-2);for(i=1;i<=2;i++) a[i]=s[i];if(a[1]==2&&a[2]==1){
        if(n&1) return puts("NIE"),0;
        for(Ans.push_back(MP(1,2)),i=n/2-1;i>=1;i--) Ans.push_back(MP(1,2)),Ans.push_back(MP(2,1));Ans.push_back(MP(1,n-1));//如果出现最后两个不符情况
    }for(i=0;i<Ans.size();){
        j=i+1;W(j<Ans.size()&&Ans[j].fi==Ans[i].fi) Ans[i].se+=Ans[j].se,j++;if(Ans[i].fi&1) Ans[i].se%=n;else Ans[i].se%=3;
        Ans[i].se&&(F.push_back(Ans[i]),0);i=j;//合并输出
    }writeln(F.size());for(auto i:F) write(i.se),pc(i.fi+'a'-1),pc(' ');
    return pc('\n'),0;
}