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

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這種題目很多都和逆序對數有關(我也不知道為甚麼XD)，可以發現，操作a可以視為將b操作的基準點往前移一格，那剩下的就是考慮要依序在哪幾點進行b操作了
首先，先決定一點(這點怎麼決定等一下再說www)，把1移到那個地方，接著會說明，如果有解，對剩下的2,3,...N存在一系列操作使得任意操作都不會動到1
接下來往逆序數對思考吧，可以發現，操作b在任何情況下都不改變逆序對數的奇偶性，操作a就只有N是偶數的情況下才會改變逆序對數的奇偶性
若數列已經排序好，逆序對數為零(偶數)，因此如果N是偶數，而逆序對數是奇數的話，無解
反之，如果N是奇數，逆序對數是奇數，則想成先把「排序好的序列做一次操作a」的情況弄出來(因為這時逆序對數是奇數)，再做N-1次操作a還原
這等價於先把1放在N這個位置
如果逆序對數是奇數，就把1放在1這個位置
然後就可以透過好多次「對不同位置進行操作b(多次操作a和一次操作b的組合)」依序把2,3,...N-2排好了(當然，1是不能動的，要永遠待在1或N這個位置)
咦?如果這時候N-1和N的位置反過來了怎麼辦?
這是不可能發生的，因為前面的預處理已經將逆序對數弄成偶數了，上述情況的逆序對數是奇數哦XD~
然後，就不小心做完了(?)
記錄下每一個操作，轉換成題目要求的格式輸出，就很開心的WA了(?)
哦，因為我把'a'打成'A'了XDD

code:

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
int N,S[2000],LOC[2000],CUR;
vector<int>ANS;
void Swap(int i,int j){swap(LOC[S[i]],LOC[S[j]]),swap(S[i],S[j]);}
void OperateA(){ANS.push_back(0);CUR--;if(CUR<0)CUR+=N;}
void OperateB(){ANS.push_back(1);Swap((CUR+1)%N,(CUR+2)%N),Swap(CUR,(CUR+1)%N);}
void MoveCUR(const int target){while(CUR!=target)OperateA();}
int InvPairs(){int ans=0;for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)if(S[i]>S[j])ans++;return ans;}
bool Solve()
{
    if((N-1)%2==0&&InvPairs()%2==1)return false;
    CUR=0,ANS.clear();
    int basis=0;
    if((N-1)%2==1&&InvPairs()%2==1){OperateA();basis=N-1;}
    for(int v=0;v+2<N;v++)
    {
        const int target=(basis+v)%N;
        while(LOC[v]!=target)
        {
            if((target+1)%N==LOC[v])MoveCUR(target),OperateB(),OperateB();
            else MoveCUR(((LOC[v]-2)%N+N)%N),OperateB();
        }
//        for(int i=0;i<N;i++)printf("%d ",S[i]);puts("");
//        for(int i=0;i<N;i++)printf("%d ",LOC[i]);puts("");puts("");
    }
    for(int v=0;v<N;v++)assert(LOC[v]==(LOC[0]+v)%N),assert(S[LOC[v]]==v);
    MoveCUR(LOC[0]);
    return true;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)scanf("%d",&S[i]),LOC[--S[i]]=i;
        if(!Solve())puts("NIE DA SIE");
        else
        {
            vector<int>ansa,ansb;
            for(int i=0;i<(int)ANS.size();)
            {
                int cnt=0;
                while(i+cnt<(int)ANS.size()&&ANS[i+cnt]==ANS[i])cnt++;
                ansa.push_back(cnt),ansb.push_back(ANS[i]);
                i+=cnt;
            }
            assert((int)ansa.size()<=N*N);
            printf("%d\n",(int)ansa.size());
            for(int i=0;i<(int)ansa.size();i++)
            {
                if(i)putchar(' ');
                printf("%d%c",ansa[i],'a'+ansb[i]);
            }
            puts("");
        }
        break;
    }
    return 0;
}