2015年4月7日 星期二

[USACO 2013 Gold] The Bessie Shuffle

作法:

這題的關鍵就是發現到,原題的操作其實就等價於:從最頂層的 m 個數開始,每次對這 m 個數做一次排列,然後把當前窗口往下移一格。也就等價於做的排列操作是 p[ i ] - 1 ,其中 p 代表原始的排列。發現這件事之後就不難想到會用到倍增法了。但原題要問的是最後落在第 x 個位置的卡片是誰,首先把他改成從上面數下來第 n+1-x 張(以後就改把這個數叫 x ),並且考慮把整個排列的操作反過來,也就是如果設 q 是 p 的反函數,那麼我們現在要求的東西就會變成「從下到上進行 q 排列並把視窗往上滑動」之後, x 會落到哪個位置。所以我們要倍增的排列其實會是 q[ i ] - 1 。並且注意到,如果 x 在經過了 k 次轉換之後變成 0 了,那麼這時候 x 的位置就確定了(之後的排列不會再動到他),或是當這個視窗跑到最頂端,無法再進行排列的時候, x 的位置也確定了。所以在倍增求答案的時候,首先要求出第一次會影響的 x 的位置的排列是在哪個視窗,並且得到 x 關於這個視窗的相對位置(從下面數上來第幾個),叫他 now 好了,所以接下來,就是對 now 進行倍增的排列。而倍增的過程中我們只要紀錄兩個數字 num 和 k ,前者代表現在還能再做幾次排列操作,後者代表已經做幾次操作了,那麼由第一次操作的位置和 k ,還有最後 now 到達的位置,就可以算出 x 最後的位置了。

和這題類似的還有 CodeForces 484-C Strange Sorting,一樣是作進行某個排列之後滑動視窗的操作。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
int per[31][maxn] ;
main()
{
    freopen("shufflegold.in","r",stdin) ;
    freopen("shufflegold.out","w",stdout) ;
    int m,n,Q ; scanf("%d%d%d",&m,&n,&Q) ;
    for(int i=1;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        per[0][n+1-x]=(n+1-i)-1 ;
    }
    for(int i=1;i<31;i++) for(int j=1;j<=n;j++)
        per[i][j]=per[i-1][per[i-1][j]] ;
 
    while(Q--)
    {
        int x ; scanf("%d",&x) ;
        x=m+1-x ;
        int bot=min(m,x+n-1) , k=0 ;
        int now=bot-x+1 ;
 
        for(int i=30 , num=bot-n;i>=0;i--)
            if(num>=(1<<i) && per[i][now])
        {
            now=per[i][now] ;
            k^=(1<<i) ;
            num-=(1<<i) ;
        }
        k++ ; now=per[0][now] ;
        printf("%d\n",bot-k+1-now) ;
    }
}
 

沒有留言:

張貼留言