[HOJ 163][POI 18 Stage 1] 數列排序

作法：

首先因為有「把最後一個拿到最前面」的操作，所以可以把整個數列環起來，每次等於可以隨便選上面連續的三個，把他們都往右移一格(最右邊的跑到最左邊)，除了這三個以外的數都不動。而只要用一連串的這個操作，就可以硬把 2 換到 1 的後面， 3 換到 2 的後面，一直做下去。但在做完「把 n-2 換到 n-3 後面」之後，這時如果 n-1 和 n 的位子是對的，那就作完了，而如果是錯的，那這樣就沒辦法用剛剛的方法把他們兩個交換了。

這時來想想看可以換出來的充要條件，這種題目通常都根逆序數對數有關( 為什麼?我也不知道 =ㄦ= )，所以如果去看每次操作後的逆序數對數變化，會發現當 n 是奇數的時候每次都不會改變他的奇偶性，所以就可以得到：如果 n 是奇數而且他的逆序數對數是奇數的話則無解。

至於偶數的情形，我們可以把他換成只剩下 n-1 和 n 位置不對，所以問題剩下要怎麼交換相鄰的兩個數，而範測很貼心(?)的根你說 n=4 的時候辦的到了，所以用類似的規律一直換下去就可以得到：只要 n 是偶數就有辦法交換數列中的相鄰兩項，所以 n 是偶數時一定可以換出 1 ~ n。

對了，如果你根群論很熟的話，請先接受我的膜拜，再繼續往下看。 <(_ _)>

如果用排列群的語言來寫，那這題就變成用 (1 2 3) 和 (1 2 3 ... n ) 乘出來的群是甚麼，而 (1 2 3)是偶排列，所以如果 (1 2 3 ... n) 也是偶排列的話那麼奇排列就都沒辦法被乘出來了，而這等價於 n 是奇數。至於 n 是偶數時，因為 (1 2 3 ... n)(1 2 3)(1 2 3) = (3 4 ... n) ，所以可以得到 (1 2) 在這個群裡面。

code :

#include<bits/stdc++.h>
using namespace std;
struct P{int num ; char c;};
vector<P> ans ;
 
int n ;
inline int move(int x,int dis)
{
    return ((((x+dis-1)%n)+n)%n)+1 ;
}
 
inline int dis(int x,int y)
{
    return y>=x ? y-x : y-x+n ;
}
 
int a[3000],now ;
void f1(int num)
{
    if(!num) return ;
    now=move(now,num) ;
    ans.push_back((P){n-num,'a'}) ;
}
 
void f2(int num)
{
    int &x=a[now],&y=a[move(now,1)],&z=a[move(now,2)] ;
    if(num==1) swap(x,y) , swap(x,z) ;
    else swap(x,y) , swap(y,z) ;
    ans.push_back((P){num,'b'}) ;
}
 
bool check()
{
    if(n%2==0) return 1 ;
    int inv=0 ;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
        if(a[i]>a[j]) inv++ ;
    return (inv%2==0) ;
}
 
void swap_last_two()
{
    f2(2) ;
    for(int i=1;i<(n/2)-1;i++) f1(2) , f2(2) ;
    f1(1) ;
    f2(1) ;
    f1(2) ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    if(!check()) { printf("NIE DA SIE\n") ; return 0 ; }
 
    now=1 ;
    for(int i=1;i<=n-3;i++)
    {
        int x,y ;
        for(x=1;a[x]!=i;x++) ;
        for(y=1;a[y]!=i+1;y++) ;
        if(y==move(x,1)) continue ;
        while(dis(x,y)>2)
        {
            f1(dis(now,move(y,-2))) ;
            f2(1) ;
            y=move(y,-2) ;
        }
        if(y!=move(x,1))
        {
            f1(dis(now,move(y,-1))) ;
            f2(2) ;
        }
    }
 
    int x ;
    for(x=1;a[x]!=1;x++) ;
    f1(dis(now,x)) ;
    if(a[move(now,-1)]!=n) swap_last_two() ;
 
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++)
        printf("%d%c%c",ans[i].num,ans[i].c," \n"[i==ans.size()-1]) ;
}