2015年2月28日 星期六

[HOJ 398] Foreign eXchange

我覺得我的作法亂七八糟的QQ,建議先看看比賽的詳解,再回來看這個我自己也覺得莫名其妙的解比較好XD

作法:

第一步當然也是轉換成差分約束系統,按照詳解理的方法建邊之後,會變成現在在數線上有 n+1 個點 S0 ~ Sn ,並且 S_i 可以跳到 S_(i-x) ,S_(i-y) 可以跳到 S_i 。先看如何決定最大的 n ,因為我之前在 ZJ 就遇過幾乎一樣的東西了( ZJ d287 ),那題其實要問的是「會造成有環的最小 n 」,和這題答案剛好差 1。

所以這題裡 n+1 的最大值是 x+y-gcd(x,y) ,也就是 最大的 n = x+y-gcd(x,y)-1,以下給一個大致上的證法。

首先當 n = x+y-gcd(x,y) 時,我們要證明這張圖裡面有個環,不妨設 gcd(x,y) = 1 ,考慮以下的跳法:從 0 開始一直往右跳 y ,跳到不能再跳為止就往左眺 x ,繼續跳到不能跳為止再往右一直跳 y ,一直跳下去。而至於為什麼這個過程不會停,因為當往右跳 y 跳到最後時,他和 n 的距離就是 < y ,也就是他和 0 的距離 >= x ,所以這時候可以往回跳 x 。而注意到每次減了 y 之後就會從 x 的一個剩餘系的數跳到另一個數,又因為 x,y 互質,所以他會遍歷 x 的完全剩餘系,也就是總有一天會跳到模 x 和 n 同餘的數,也就是他有辦法跳到 n ,再由 x,y 的對稱性可知 n 也可以跳回 0 ,所以這張圖裡面有環。

再來要證小於 x+y-gcd(x,y) 的話沒有環,一樣設 gcd(x,y) = 1 ,因為有環代表從 0 開始經過幾次 +y 和幾次 -x 會回到自己,設往右跳了 a 次,往左跳了 b 次,所以有 ay = bx -> a>=x 且 b>=y ( 因為 gcd(x,y)=1 )。但因為每次到一個點的時候一定只有 +y 和 -x 的其中一種選擇(因為 n 太小),所以這張圖裡面只有 n+1 條邊,所以形成的環的大小會 <= n+1 <= x+y-1 ,矛盾。

再來是構造,拓樸排序應該比我寫的奇怪的東西簡潔好多.......

一樣是構造前綴和,最後再用相鄰兩項相減得到答案。我是先把 gcd(x,y) 的倍數們構好,其他的就可以從 gcd(x,y) 的倍數們複製過去了。構法就類似上面的證明,從一個點開始往右跳 y 跳到底再往左眺 x ,跳到不能跳為止,那麼每跳到一個數他的答案就是前一個數的答案 +1 ,或是反過來跳 ( 向右跳 x 向左眺 y ),每跳到的數的答案就是前一個數的答案 -1 ,跳完之後再換另一個起點跳,一直重複到沒有數為止,而這個過程用 linked list 維護還剩哪些數字。


code :

#include<bits/stdc++.h>
#define INF 50000000
using namespace std;
const int maxn=400000+10 ;
 
int x,y ;
int ans[maxn] ;
 
int nex[maxn],las[maxn] ;
int size,head ;
void erase(int x)
{
    size-- ;
    if(x==head) head=nex[x] ;
    else nex[las[x]]=nex[x] , las[nex[x]]=las[x] ;
}
 
main()
{
    int n ; scanf("%d%d%d",&n,&x,&y) ;
    int g=__gcd(x,y) ;
    if(n!=-1 && n>x+y-g-1)
        { printf("Impossible\n") ; return 0 ; }
    else
    {
        n=x+y-g-1 ;
        if(n<x || n<y) { printf("Impossible\n") ; return 0 ; }
    }
 
    size=0 ; head=0 ;
    for(int i=0;i*g<=n;i++)
    {
        size++ ;
        if((i+1)*g>n) nex[i*g]=0 ;
        else nex[i*g]=(i+1)*g , las[(i+1)*g]=i*g ;
    }
 
    while(size>0)
    {
        int tmp=head , now=head ;
        ans[now]=0 ; erase(now) ;
        for(int type=0;;type^=1)
        {
            if(now+x > n && now-y < 0) break ;
            if(type==0) while(now+x<=n)
                ans[now+x]=ans[now]+1 , now+=x , erase(now) ;
            else while(now-y>=0)
                ans[now-y]=ans[now]+1 , now-=y , erase(now) ;
        }
        now=tmp ;
        for(int type=0;;type^=1)
        {
            if(now-x < 0 && now+y > n) break ;
            if(type==0) while(now-x>=0)
                ans[now-x]=ans[now]-1 , now-=x , erase(now) ;
            else while(now+y<=n)
                ans[now+y]=ans[now]-1 , now+=y , erase(now) ;
        }
    }
 
    for(int i=1;i<=n;i++) if(i%g) ans[i]=ans[i/g*g] ;
 
    printf("%d\n",n) ;
    for(int i=1;i<=n;i++) printf("%d%c",ans[i]-ans[i-1],i==n?'\n':' ') ;
}
 

沒有留言:

張貼留言