P3516 [POI2011]PRZ-Shift

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 即可。

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

8
1 2 3 4 5 6 8 7

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

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

Code

#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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇