题解 P3516 【[POI2011]PRZ-Shift】

· · 题解

简单构造题

这个写法和标程输出的并不一致，所以需要spj

另外这道题尽管嘤文题面上是puts"NIE DA SIE",但是由于一些历史原因,你需要puts"NIE"才能AC本题

本题题解

那么我们来看看我们到底可以干什么操作

操作1的本质是你可以在一个操作块的时间内将这个排列轮换一下

而操作3的本质是你可以在一个操作块的时间内将这个排列的前3位变成3,1,2或者2,3,1这两种排列

那么如果我们将操作1和操作3同时使用(也就是每次操作完毕之后我们都让这个排列轮换回来)我们就可以实现这样一个操作

将这个排列中任意一个长度为3的区间变成3,1,2或者2,3,1这个操作

先来说一下我们怎么实现这个操作

比如说我要操作(3,5)这个区间,我们先执行a操作n-2次这样我们就将(3,5)这个区间轮换到了最前面，然后执行1~2次b操作之后再执行2次a操作使得排列恢复成从1开始的轮换

当然我们发现一次操作需要3个操作块，不过我们如果我们连续的使用这个操作的话我们会发现我们的操作序列是ka,kb,ka,ka,kb,ka..的形式，我们可以将相邻的两个a操作合并起来，这样的话一次操作平摊下来仅仅需要两个操作块了

那么我们有了这个操作之后我们会发现可以实现这两个操作,并且这些操作仅仅改变后面元素的排布情况

1.将任意一个元素(除非他是前两个元素)的位置向前挪两个格子

2.将任意一个元素(除非他是第一个或者最后一个元素)的位置向前挪一个格子

实现方式也十分简单，就是轮换过去做1~2次b接着轮换回来就行了

那么我们就可以借助这个东西实现一个相当无脑的排序方式了

就是我们先把1放在第1位，然后把2放在第2位，然后把3放在第3位……以此类推

假如说我们要将这个元素挪动偶数格的话，我们不停的调用操作1即可

假如说要将这个元素挪动奇数格的话，我们不停的调用操作1，然后最后一下调用操作2即可

然后你发现这个策略在我们让n-1和n-2归位的时候会失效

具体来讲我们可能需要应付这样一个排列

1 2 3 4 5 6 8 7

这种情况是有解的但是无法用我们刚才那种方式构造出来

怎么办呢……？

其实这种情况还是可以抢救一下的，让我们来不断的对8调用1操作试试看

1 2 3 4 8 5 6 7

1 2 8 3 4 5 6 7

8 1 2 3 4 5 6 7

然后我们再做n-1次a操作排列就成了12345678了

当然是奇数的时候就gg了,put"NIE"即可

然后特判一下n=0和2的情况就行了

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=2010;
int n;int a[N];int op[N*N][2];int tp;int pi;
inline void mov(int tw)
{if(tw==pi)return;op[++tp][0]=(pi-tw+n)%n;op[tp][1]=0;pi=tw;}
inline void stp1(int pos)
{mov(pos-1);op[++tp][0]=2;op[tp][1]=1;swap(a[pos],a[pos-1]);swap(a[pos],a[pos+1]);}
inline void stp2(int pos)
{mov(pos-2);op[++tp][0]=1;op[tp][1]=1;swap(a[pos],a[pos-1]);swap(a[pos-1],a[pos-2]);}
int main()
{
    scanf("%d",&n);pi=1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    if(n==1){printf("0\n");return 0;}//特判 
    if(n==2)
    {
        if(a[1]<a[2])printf("0\n");
        else printf("1\n1a");return 0;
    }
    for(int i=1;i<=n-2;i++)//挪动元素 
    {
        int pos;
        for(int j=i;j<=n;j++)
            if(a[j]==i){pos=j;break;}
        if(pos==i)continue;
        while(pos-i>1)stp2(pos),pos-=2;
        if((pos-i)&1)stp1(pos),pos--;
    }
    if(a[n-1]==n)//处理特殊情况 
    {
        if(n&1){printf("NIE\n");return 0;}
        int pos=n-1;
        while(pos!=1)stp2(pos),pos-=2;
    }int pos;
    for(int i=1;i<=n;i++)//调整回1开头的排列 
        if(a[i]==1){pos=i;break;}mov(pos);
    printf("%d\n",tp);
    for(int i=1;i<=tp;i++)printf("%d%c ",op[i][0],(op[i][1])?'b':'a');
    return 0;//拜拜程序~ 
}