2015年2月28日 星期六

[TIOJ 1243] 感染 Infection

第一次寫這種比較難轉移的樹上的DP,但這題的測資爛了,最後一筆測資和範測一模一樣,輸出 4 卻是錯的,沒辦法AC QQ
測資修正之後AC了!總共獲得了24個AC XD

作法:

因為其實是「把邊砍掉」之後才會有「哪些點被感染哪些點沒被感染」,所以可以反過來作砍掉 m 條邊之後最多有幾個點沒被感染。把沒被感染的叫白點,剩下的叫黑點,記 dp[ b ][ x ][ m ] 代表在以 x 為根的子樹中,當 x 的顏色是 b ,且砍掉 m 個邊的時候,白點的最大值。所以這樣可以寫出很大一坨的轉移式:

dp[ b ][ x ][ m ] = ( b==white ) + MAX{ sigma dp[ bi ][ vi ][ mi ] } ,其中 bi 和 mi 們滿足
sigma( mi + ( bi != b ) ) = m 。 vi 代表的是 x 的子結點們,而其實這句話的意思就是將可以砍的 m 條邊分配給 x 的子結點,並且當 x 的子結點和 x 不同色的時候必須要再多加一條邊分隔他們。

所以這個的意思就是我們必須從好幾個 DP 陣列 ( 也就是 dp[ bi ][ vi ] 們 ) 合併成一個新的陣列 dp[ b ][ x ] ,但當然不可能枚舉所有的 mi ,所以在這裡我們還需要另一個DP,設 dp2[ i ][ m ]代表目前已經考慮了 i 顆子樹了,那麼砍掉 m 條邊至多可以有幾個白點。每次多考慮一個子樹就會把那個子樹的DP陣列和現在的dp2 陣列跑過一次。

這樣看起來每個節點都會花掉 O( n^2 ) 的時間轉移,但其實只要注意到對於一個子樹 x ,他的邊數只有 x 的 size -1 ,也就是 dp[ b ][ x ][ m ] 的 m 其實只要作 0 ~ x 的 size -1 就夠了。所以設 x 的子樹的 size 分別為 n1 , n2 , ... , nt ,當在作 dp[ i+1 ] 的時候其實要跑過的陣列只有 n(i+1) * ( n1+n2+...+ni ) ,把他們 sum 起來會得到總合併時間 = sigma ni * nj ,其中 i , j 跑遍 1~t 且 i < j 。所以如果用數歸,假設 x 的子樹們都能在 O( size ^2 ) 的時間內完成,那麼完成 x 的時間就是 (sigma ni^2) + (sigma ni * nj) <= ( sigma ni ) ^2 < size[x]^2 ,得證。

code :

#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
const int maxn=1000+50 ;
 
int sz[maxn],dp[2][maxn][maxn] ;
int dp2[maxn][maxn] ;
vector<int> v[maxn] ;
bool G[maxn] ;
 
void dfs(int x,int fa)
{
    sz[x]=1 ;
    if(x && (int)v[x].size()==1)
    {
        if(!G[x]) dp[0][x][0]=1 , dp[1][x][0]=0 ;
        else dp[0][x][0]=-INF , dp[1][x][0]=0 ;
        return ;
    }
    for(auto i : v[x]) if(i!=fa)
        dfs(i,x) , sz[x]+=sz[i] ;
    for(int b=0;b<2;b++)
    {
        if(b==0 && G[x])
        {
            for(int i=0;i<sz[x];i++) dp[b][x][i]=-INF ;
            continue ;
        }
        for(int i=0;i<sz[x];i++) dp2[0][i]=-INF ;
        dp2[0][0]=0 ;
        int tot=0,cnt=0 ;
        for(int i=0;i<v[x].size();i++) if(v[x][i]!=fa)
        {
            int y=v[x][i] ;
            tot+=sz[y] ;
            for(int j=0;j<sz[x];j++) dp2[cnt+1][j]=-INF ;
 
            for(int j=(b!=0);j<=tot;j++)
                for(int k=0;k<sz[y] && j-k-(b!=0)>=0;k++)
                dp2[cnt+1][j]=max(dp2[cnt+1][j],
                        dp2[cnt][j-k-(b!=0)]+dp[0][y][k]) ;
 
            for(int j=(b!=1);j<=tot;j++)
                for(int k=0;k<sz[y] && j-k-(b!=1)>=0;k++)
                dp2[cnt+1][j]=max(dp2[cnt+1][j],
                        dp2[cnt][j-k-(b!=1)]+dp[1][y][k]) ;
            cnt++ ;
        }
        for(int i=0;i<sz[x];i++)
            dp[b][x][i]= (b==0) + dp2[cnt][i] ;
    }
}
 
main()
{
    int n,k,num ;
    scanf("%d%d%d",&n,&k,&num) ;
    if(k+num>n) { printf("ACM rules!\n") ; return 0 ; }
    while(num--)
    {
        int x ; scanf("%d",&x) ;
        G[x]=1 ;
    }
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    dfs(0,-1) ;
 
    int ans1=n-1,ans2=n-1 ;
    for(int i=0;i<n;i++) if(dp[0][0][i]>=k)
        { ans1=i ; break ; }
    for(int i=0;i<n;i++) if(dp[1][0][i]>=k)
        { ans2=i ; break ; }
    printf("%d\n",min(ans1,ans2)) ;
}
 

[TIOJ 1242] 午餐大反攻 Lunch Reloaded

作法:

大概可以馬上想到二分答案所在的 x,y 坐標,並且建二維的前綴和陣列可以 O(1) 查詢一個長方形裡面的數字總和,但要計算答案的時候沒有那麼單純(?),必須還要多記錄 i * a_ij 的前綴和陣列和 j * a_ij 的前綴和陣列才能在O(1)內算出來。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000+10 ;
 
LL a[maxn][maxn],s[3][maxn][maxn] ;
 
inline LL cal(int t,int x1,int y1,int x2,int y2)
{
    return s[t][x2][y2]-s[t][x1-1][y2]-s[t][x2][y1-1]+s[t][x1-1][y1-1] ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        scanf("%lld",&a[i][j]) ;
        s[0][i][j]=s[0][i-1][j]+s[0][i][j-1]-s[0][i-1][j-1]+a[i][j] ;
        s[1][i][j]=s[1][i-1][j]+s[1][i][j-1]-s[1][i-1][j-1]+j*a[i][j] ;
        s[2][i][j]=s[2][i-1][j]+s[2][i][j-1]-s[2][i-1][j-1]+i*a[i][j] ;
    }
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int x1,y1,x2,y2 ; scanf("%d%d%d%d",&x1,&x2,&y1,&y2) ;
        LL tot=cal(0,x1,y1,x2,y2) ;
        if(!tot) { printf("0\n") ; continue ; }
 
        int x,y ;
        int l=x1-1 , r=x2 ;
        while(r-l>1)
        {
            int mid=(r+l)/2 ;
            if(cal(0,x1,y1,mid,y2) >= (tot+1)/2) r=mid ;
            else l=mid ;
        }
        x=r ;
 
        l=y1-1 , r=y2 ;
        while(r-l>1)
        {
            int mid=(r+l)/2 ;
            if(cal(0,x1,y1,x2,mid) >= (tot+1)/2) r=mid ;
            else l=mid ;
        }
        y=r ;
 
        LL ans=0LL ;
        ans+=y*cal(0,x1,y1,x2,y)-cal(1,x1,y1,x2,y) ;
        ans+=cal(1,x1,y,x2,y2)-y*cal(0,x1,y,x2,y2) ;
        ans+=x*cal(0,x1,y1,x,y2)-cal(2,x1,y1,x,y2) ;
        ans+=cal(2,x,y1,x2,y2)-x*cal(0,x,y1,x2,y2) ;
        printf("%lld\n",ans) ;
    }
}
 

[TIOJ 1241] 倍因道 Factor and Points

這題我是去查解才會的,但證不出來為什麼這樣是對的........
如果有一天證出來了會在這補上(?

作法:

把題目要分的組叫作A和B好了,這樣比較不會搞混。從 1 開始,每次看他放A比較好還是放B比較好,而判斷的條件是如果放 A 就假設他的倍數通通都被放到 B 了,這樣是他的最高得分,而如果放B那得分就是他的因數在A裡的個數,這可以用類似篩法的方法在每次把數字加進A的時候維護好。如果放A有機會比較好就放A,否則放B。

====================================

3/5 更新證明:

當有一個數 a 被丟進A的時候,代表我們認為之後的最好情形( 也就是 a 的倍數都在 B )的 a 造成的貢獻會比把 a 移到 B 還多 ( 這時的貢獻是 a 的因數個數 ),但如果在之後的決定裡面 2a , 3a , ... , ka 們也跳槽進入A了,那 a 的貢獻就有可能變得太少以至於把 a 丟進B會更好,以下要證明這件事情不可能。

(以下的中括號為高斯符號,d(x) 代表 x 的因數個數)
用反證法,因為 ka 被放入A,由我們的決策方法可以得到 [ n/ ( k a ) ] >= d( k a ),又因為 a 的貢獻為 [ n / a ] - k ,所以此時有 [ n / a ] - k < d( a ),而考慮 [ n/ ( k a ) ] 和 [ n / a ] - k 兩個數,前者是 1~n 裡面 ka 的倍數個數,另一個是 1~n 裡面大於 ka 的 a 的倍數個數,顯然一個數整除 ka 就會整除 a ,所以後者會大於等於前者,也就是 [ n / a ] - k >= [ n/ ( k a ) ],所以 d( a ) > [ n / a ] - k >= [ n/ ( k a ) ] >= d( k a ) ,得到了 a 的因數個數比 ka 的因數個數多,矛盾。

code :

#include<bits/stdc++.h>
using namespace std;
 
int num[3000] ;
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n ; scanf("%d",&n) ;
        memset(num,0,sizeof(num)) ;
        int ans=0 ;
        for(int i=1;i<=n;i++)
        {
            if(num[i] < n/i-1)
                for(int j=2*i;j<=n;j+=i) num[j]++ ;
            else ans+=num[i] ;
        }
        printf("%d\n",ans) ;
    }
}
 

[HOJ 396] Rabbit Rush

作法:

原題的敘述我看蠻久才看懂的......其實他要問的是「將原數列分成 k 陀,使得 sigma( 一坨內按某種順序取相鄰數的差的總和 ) 最小」,而可以看出其實那個值就等於一坨內的最大值減最小值,所以如果一坨內有 x 和 y ,那麼把 x , y 中間的數全部加進來不會更差,所以可以先把原數列排序,這 k 陀就對應到 k 條線段,並且他們兩兩不相交,復蓋了這 n 個點。如果把要求的東西用「原數列的最大值減最小值」扣掉,就會剩下 k-1 條連接相鄰點的線段,而我們要讓這些線段的長度總和最大,所以就取前 k-1 大的就好了。而因為要拔點,所以還要維護這些差值的資料結構,我自己是用 linked list 詢問每個要刪掉的點的左右是誰,還有用兩個 multiset 分別放目前取的前 k-1 大的差值和剩下的差值。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
map<int,int> mp ;
int a[maxn] ;
int nex[maxn],las[maxn],head,tail ;
int maxl,sum ;
 
multiset<int,greater<int> > st1 ;
multiset<int> st2 ;
 
void erase2(int val)
{
    auto it=st1.find(val) ;
    if(it!=st1.end()) st1.erase(it) ;
    else
    {
        st2.erase(st2.find(val)) ;
        sum-=val ;
        st2.insert(*st1.begin()) ;
        sum+=*st1.begin() ;
        st1.erase(st1.begin()) ;
    }
}
 
void insert(int val)
{
    st2.insert(val) ; sum+=val ;
    st1.insert(*st2.begin()) ; sum-=*st2.begin() ;
    st2.erase(st2.begin()) ;
}
 
void erase(int x)
{
    int id=mp[x] ;
    if(id==tail || id==head)
    {
        int val ;
        if(id==tail) val=a[id]-a[las[id]] , tail=las[id] ;
        else val=a[nex[id]]-a[id] , head=nex[id] ;
        maxl=a[tail]-a[head] ;
        erase2(val) ;
    }
    else
    {
        int val1=a[id]-a[las[id]] , val2=a[nex[id]]-a[id] ;
        las[nex[id]]=las[id] , nex[las[id]]=nex[id] ;
 
        insert(val1+val2) ;
        erase2(val1) ; erase2(val2) ;
    }
}
 
main()
{
    int n,k,Q ; scanf("%d%d%d",&n,&k,&Q) ;
    k-- ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]) ;
        nex[i]=i+1 ; las[i]=i-1 ;
    }
    head=1 ; tail=n ;
    sort(a+1,a+n+1) ;
    maxl=a[n]-a[1] ;
    for(int i=1;i<=n;i++)
    {
        mp[a[i]]=i ;
        if(i<n) st1.insert(a[i+1]-a[i]) ;
    }
 
    sum=0 ;
    for(int i=1;i<=k;i++)
    {
        sum+=*st1.begin() ;
        st2.insert(*st1.begin()) ;
        st1.erase(st1.begin()) ;
    }
    printf("%d\n",maxl-sum) ;
 
    while(Q--)
    {
        int x ; scanf("%d",&x) ;
        erase(x) ;
        printf("%d\n",maxl-sum) ;
    }
}
 

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

2015年2月27日 星期五

[HOJ 394] 壞掉的水表

作法:

考慮將所有點黑白塗色,相鄰的點不同色,那麼黑點的值總和就會等於白點的值總和,所以剩下的一個值只要直接相減就可以得到了。

code :

#include<bits/stdc++.h>
using namespace std;
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    int val=0 , type ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        int x ; scanf("%d",&x) ;
        if(x==-1) { type=(i+j)%2 ; continue ; }
        if((i+j)%2) val+=x ;
        else val-=x ;
    }
    printf("%d\n",type==1 ? -val : val) ;
}
 

[HOJ 397] 猜數列

作法:

基本的KMP,只要先把給的數列延長成長度為 n+m 再直接配對就好了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int fail[2*maxn] ;
int s[2*maxn],t[2*maxn] ;
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) scanf("%d",&s[i]) ;
    for(int i=1;i<=m;i++) scanf("%d",&t[i]) ;
    for(int i=n+1;i<=n+m;i++) s[i]=s[i-n] ;
    fail[1]=0 ;
    int j=0 ;
    for(int i=2;i<=m;i++)
    {
        while(j && t[j+1]!=t[i]) j=fail[j] ;
        if(t[j+1]==t[i]) j++ ;
        fail[i]=j ;
    }
    int num=0 ; j=0 ;
    for(int i=1;i<m+n;i++)
    {
        while(j && t[j+1]!=s[i]) j=fail[j] ;
        if(t[j+1]==s[i]) j++ ;
        if(j==m) { num++ ; j=fail[j] ; }
    }
    if(!num) printf("QAQ\n") ;
    else
    {
        int g=__gcd(num,n) ;
        printf("%d/%d\n",num/g,n/g) ;
    }
}
 

[HOJ 399] 訓練計畫

作法:

這次比賽的詳解 (懶 XD)。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
int w[maxn] ;
vector<int> v1[maxn],v2[maxn] ;
bool vis1[maxn],vis2[maxn] ;
LL dp[2][maxn] ;
 
void dp1(int x)
{
    if(vis1[x]) return ;
    vis1[x]=1 ;
    LL &ans=dp[0][x] ; ans=w[x] ;
    for(auto i : v1[x])
    {
        dp1(i) ;
        ans=max(ans,w[x]+dp[0][i]) ;
    }
}
 
void dp2(int x)
{
    if(vis2[x]) return ;
    vis2[x]=1 ;
    LL &ans=dp[1][x] ; ans=w[x] ;
    for(auto i : v2[x])
    {
        dp2(i) ;
        ans=max(ans,w[x]+dp[1][i]) ;
    }
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) scanf("%d",&w[i]) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v1[x].push_back(y) ;
        v2[y].push_back(x) ;
    }
 
    for(int i=1;i<=n;i++) dp1(i) ;
    for(int i=1;i<=n;i++) dp2(i) ;
    LL maxl=0LL ;
    for(int i=1;i<=n;i++) maxl=max(maxl,dp[0][i]) ;
    for(int i=1;i<=n;i++)
    {
        LL l=dp[0][i]+dp[1][i]-w[i] ;
        printf("%lld\n",maxl-l) ;
    }
}