[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':' ') ;
}