[HOJ 395] 搬磚塊

作法：

一直拿多的搬過去少的，就會是最少搬運次數了，證明也不難，因為至少就需要那麼多次。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100+10 ;
int a[maxn],b[maxn] ;
struct P{int x,y ;};
vector<P> v ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<=n;i++) scanf("%d",&b[i]) ;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==b[i]) continue ;
        if(a[i]>b[i])
        {
            for(int j=i+1;a[i]!=b[i];j++) while(a[j]<b[j] && a[i]!=b[i])
                a[j]++ , a[i]-- , v.push_back((P){i,j}) ;
        }
        else
        {
            for(int j=i+1;a[i]!=b[i];j++) while(a[j]>b[j] && a[i]!=b[i])
                a[j]-- , a[i]++ , v.push_back((P){j,i}) ;
        }
    }
    printf("%d\n",v.size()) ;
    for(auto i : v) printf("%d %d\n",i.x,i.y) ;
}
 

[TIOJ 1239] 致命武器 Lethal Weapon

作法：

由大到小 check 是否有辦法把這顆樹切成好幾條這個長度的鍊，而顯然練的長度必須整除 n-1 才有辦法。而在 check 的過程就類似 HOJ 135 - 縫紉課 ，兩題都是要處理把樹分成好幾條鍊的問題，都可以用DP作。而注意到在DP的時候，一顆子樹對應的子問題是「是否能夠把這顆子樹的所有邊分成幾條長度L的鍊，並且剩下一條長度<L的鍊以子樹的根為其中一個端點」，而因為其實一顆子樹裡面的邊數就是他的 size 再 -1，所以不用特別記錄邊數。而在轉移的時候就是拿 x 和 L-x 配對，如果有大於一條不能配對的話這顆子樹就是失敗的，反之就是可以的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10 ;
 
int size[maxn] ;
vector<int> v[maxn] ;
bool vis[maxn] ;
 
bool dfs(int x,int num)
{
    vis[x]=1 ; size[x]=1 ;
    multiset<int> st ;
    for(auto i : v[x]) if(!vis[i])
    {
        if(!dfs(i,num)) return 0 ;
        size[x]+=size[i] ;
        if(size[i]%num) st.insert(size[i]%num) ;
    }
    if(st.size()<=1) return 1 ;
    if(x==1)
    {
        if(st.size()%2) return 0 ;
        while(!st.empty())
        {
            int t=*st.begin() ; st.erase(st.begin()) ;
            if(!st.count(num-t)) return 0 ;
            st.erase(st.find(num-t)) ;
        }
        return 1 ;
    }
 
    int cnt=0 ;
    while(st.size()>1)
    {
        int t=*st.begin() ; st.erase(st.begin()) ;
        if(!st.count(num-t)) cnt++ ;
        else st.erase(st.find(num-t)) ;
        if(cnt>1) return 0 ;
    }
    if(!st.empty()) cnt++ ;
    return cnt<=1 ;
}
 
bool check(int x)
{
    if(x<=2) return 1 ;
    memset(vis,0,sizeof(vis)) ;
    return dfs(1,x) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    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) ;
    }
 
    for(int i=n-1;i>=1;i--) if(((n-1)%i==0) && check(i))
    {
        printf("%d\n",i) ;
        return 0 ;
    }
}
 

[TIOJ 1238] 萬磁王的遊戲 Magneto's Game

這題在我前年暑假參加 IMOCamp 的時候就看過了，竟然在這裡出現，真是太神奇了XD

作法：

可以把鐵塊全部塞成一格 <=> 全部鐵塊連通！！！

有了這個結論，剩下就簡單了，以下給一個大概的證明。

從左邊推到右邊是顯然的。如果全部的鐵塊連通，我們只要證明能夠把其中兩個鐵塊弄到同一個格子裡，就可以數歸下去了。

考慮任兩個鐵塊 A和B ，我們想要把 A和B 弄到同一個格子裡。因為A和B連通，所以存在一條路徑連接A和B，考慮A走到B的最短路，並且沿著最短路的方向移動鐵塊們( 例如第一步A要往下走 就作往下的操作 )，如果在動的過程中，某一步B被擋住了，這就代表A和B之間的最短路距離嚴格變小了，所以可以數歸下去。而如果B一直都沒有被擋住，那這時A移動到了B的位置，因為他們走的步都一樣，所以B到的位置是B + AB向量，一直重複這個過程，如果B永遠都沒有被擋住，就會得到這個網格是無限大的，矛盾，所以A總能嚴格減少和B之間的最短距離。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+10 ;
 
char G[maxn][maxn] ;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
int n ;
bool vis[maxn][maxn] ;
 
bool solve()
{
    int x0=-1,y0=-1 ;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        if(G[i][j]=='x') x0=i , y0=j ;
    if(x0==-1) return 1 ;
 
    queue<int> q ;
    q.push(x0) ; q.push(y0) ; vis[x0][y0]=1 ;
    while(!q.empty())
    {
        int x=q.front() ; q.pop() ;
        int y=q.front() ; q.pop() ;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i] , ny=y+dy[i] ;
            if(nx<0||nx>=n||ny<0||ny>=n) continue ;
            if(G[nx][ny]=='#' || vis[nx][ny]) continue ;
            vis[nx][ny]=1 ;
            q.push(nx) ; q.push(ny) ;
        }
    }
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        if(G[i][j]=='x' && !vis[i][j]) return 0 ;
    return 1 ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=0;i<n;i++) scanf("%s",G[i]) ;
    if(solve()) printf("Strong!\n") ;
    else printf("Weak!\n") ;
}
 

[TIOJ 1237] 砍了那些腳 Cut Many Legs

作法：

因為桌子平衡會等價於「圓心嚴格落在最長的桌腳們形成的多邊形內部」，所以只要二分「和地面接觸的桌腳長度(超過的就是被砍掉的)」，然後判斷有沒有相鄰的桌腳跨越了整個圓的一半就OK了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 2147483647
using namespace std;
const int maxn=2000000+10 ;
 
int n,a[maxn] ;
 
bool check(int x)
{
    int fir=-1,last=-1 ;
    for(int i=0;i<n;i++) if(a[i]>=x)
    {
        if(fir==-1) { fir=last=i ; continue ; }
        if(i-last >= (n+1)/2) return 0 ;
        last=i ;
    }
    if( fir-last+n >= (n+1)/2 ) return 0 ;
    return 1 ;
}
 
main()
{
    scanf("%d",&n) ;
    int l=INF , r=0 ;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]) ,
        l=min(l,a[i]) , r=max(r,a[i]) ;
    r++ ;
    while(r-l>1)
    {
        int mid=l+(r-l)/2 ;
        if(check(mid)) l=mid ;
        else r=mid ;
    }
    LL ans=0LL ;
    for(int i=0;i<n;i++) ans+=max(0LL,(LL)a[i]-l) ;
    printf("%lld\n",ans) ;
}
 

[TIOJ 1230] 尋寶問題

作法：

給的網格很小，而且要求的是兩條起點到終點的亂走的路徑，大概只能DFS暴搜( 插頭DP不知道有沒有辦法作，沒學過OAO 不過就算可以的話應該也比這作法麻煩 )，所以很開心的寫了暴搜傳上去，就有一筆測資TLE了。TLE的測資也不難想像，只要 n,m 取最大然後完全沒有障礙物就夠他跑了。

所以必須要加一些剪枝，因為這個問題類似之前在作書上習題(算法競賽入門經典 第二版)作到的UVa 11882，所以剪枝方法也類似。第一個方法就是如果現在是第二個人在走，而且他走到這步之後會讓之後沒辦法再走到終點了(也就是和終點不連通)，則剪枝。所以會在每次DFS到一個點的時候另外做一次DFS。但這樣還不夠，那筆測資一樣會TLE。下一個方法則是如果把和當前格子連通的所有寶物都吃到了，還會比當前最佳解差，則也剪枝。用這兩個方法就能過這題了。

UVa那題的剪枝方法也類似，就是考慮當前格子所在的連通塊，如果全部數字都能吃到，而且假設有辦法排成一個最大的數字，這樣也比最佳解差則剪枝。

code :

#include<bits/stdc++.h>
using namespace std;
 
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
int n,m ;
int G[10][10],ans,num=0 ;
bool vis[2][7][7],vis2[2][7][7] ;
 
int num2 ;
void dfs2(int x,int y,int t)
{
    vis2[t][x][y]=1 ; num2+=G[x][y] ;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i] , ny=y+dy[i] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(G[nx][ny]==-1 || vis[t][nx][ny]) continue ;
        if(vis2[t][nx][ny]) continue ;
        dfs2(nx,ny,t) ;
    }
}
 
bool check(int x,int y,int t)
{
    memset(vis2[t],0,sizeof(vis2[t])) ;
    num2=0 ;
    dfs2(x,y,t) ;
    return vis2[t][n-1][m-1] && (t==0 || num2+num > ans) ;
}
 
void dfs(int x,int y,int t)
{
    if(!check(x,y,t)) return ;
    if(t==1 && x==n-1 && y==m-1) { ans=max(ans,num) ; return ; }
    if(x==n-1 && y==m-1) { dfs(0,0,1) ; return ; }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i] , ny=y+dy[i] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(G[nx][ny]==-1 || vis[t][nx][ny]) continue ;
        int tmp=G[nx][ny] ;
        G[nx][ny]=0 ; vis[t][nx][ny]=1 ; num+=tmp ;
        dfs(nx,ny,t) ;
        G[nx][ny]=tmp ; vis[t][nx][ny]=0 ; num-=tmp ;
    }
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    {
        char s[5] ; scanf("%s",s) ;
        if(s[0]=='x') G[i][j]=-1 ;
        else G[i][j]=s[0]-'0' ;
    }
    ans=0 ;
    vis[0][0][0]=1 ;
    num=G[0][0] ; G[0][0]=0 ;
    dfs(0,0,0) ;
    printf("%d\n",ans) ;
}
 

[TIOJ 1226] H遊戲

作法：

一開始又理解錯題目意思了......總之這題要求的就是「從 0 到某些點的所有走法的路徑長度總和」，而很明顯如果圖裡有環就噴射了，但題目沒有講OAO ( 當然測資是沒有環的 )。

所以就可以簡單對每個終點DP了，只要記錄每個點到特定一個終點有幾種走法，和所有走法的路徑總和就好了。但我第一次傳上去 WA 了，後來發現原因竟然是「終點可能有連出一些邊」！！！ 這不合理阿，為什麼到了一個女主角的結局之後經過一些事件還能再到另一個女主角的結局，不是應該就結束了嗎=口=

code :

#include<bits/stdc++.h>
#define MOD 32768
using namespace std;
const int maxn=2000+10 ;
struct P{int to,dis;};
 
int num[maxn][200+10] ;
int d[maxn][200+10],m,n ;
bool vis[maxn] ;
vector<P> v[maxn] ;
char name[200+10][200] ;
 
void dp(int x)
{
    if(vis[x]) return ;
    vis[x]=1 ;
    for(auto j : v[x])
    {
        dp(j.to) ;
        for(int i=1;i<=m;i++)
        {
            num[x][i]=(num[x][i]+num[j.to][i])%MOD ;
            d[x][i]=(d[x][i]+num[j.to][i]*j.dis+d[j.to][i])%MOD ;
        }
    }
    if(x>=1 && x<=m) num[x][x]++ ;
}
 
main()
{
    int T,tc=0 ; scanf("%d",&T) ;
    while(T--)
    {
        int x ; scanf("%d%d%d",&m,&n,&x) ;
        for(int i=0;i<maxn;i++) v[i].clear() ;
        for(int i=1;i<=m;i++) scanf("%s",name[i]) ;
        while(x--)
        {
            int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
            dis%=MOD ;
            v[x].push_back((P){y,dis}) ;
        }
        memset(vis,0,sizeof(vis)) ;
        memset(d,0,sizeof(d)) ;
        memset(num,0,sizeof(num)) ;
        dp(0) ;
 
        printf("Game #%d\n",++tc) ;
        for(int i=1;i<=m;i++) printf("%s: %d\n",name[i],d[0][i]) ;
    }
}
 

[TIOJ 1225] 數字合併

作法：

greedy，考慮最小的那個數，看看他的左右，會發現這兩個數一定大於等於他(廢話)(當然如果在邊界那就只有一個)，直覺會認為選其中一個比較小的然後用他把這個數砍掉是最好的。主要是因為，假設砍掉 ai 的數在他右邊但不和他相鄰好了，那他必須能夠砍掉 ai 右邊的那個數，才有機會來到 ai 的旁邊，也就是他 >= ai 右邊的數，這樣花費會變高，所以不如早點用 ai 右邊的把他砍掉還要好。

而實作上需要「砍掉一個數」和「詢問一個數的左右是誰」，所以用 linked list 。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
struct P
{
    int id,val ;
    bool operator < (const P &rhs) const
    {
        return val>rhs.val ;
    }
};
 
int a[maxn],ri[maxn],le[maxn] ;
priority_queue<P> pq ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]) ,
        le[i]=i-1 , ri[i]=i+1 ,
        pq.push((P){i,a[i]}) ;
    LL ans=0LL ;
    while(pq.size()>1)
    {
        P u=pq.top() ; pq.pop() ;
        if(!le[u.id]) { ans+=a[ri[u.id]] ; le[ri[u.id]]=0 ; continue ; }
        if(ri[u.id]==n+1) { ans+=a[le[u.id]] ; ri[le[u.id]]=n+1 ; continue ; }
        ans+=min(a[le[u.id]],a[ri[u.id]]) ;
        le[ri[u.id]]=le[u.id] ;
        ri[le[u.id]]=ri[u.id] ;
    }
    printf("%lld\n",ans) ;
}
 

[TIOJ 1224][HOJ 12] 矩形覆蓋面積計算 / 矩形面積覆蓋

作法：

原本以為會蠻好寫的就一直沒來寫這個，想說反正就掃描線+線段樹嘛~應該沒甚麼困難的，結果真正要寫的時後發現線段樹的部分好難想OAO 參考了這篇然後想了很久之後才知道線段樹怎麼作的。

掃描線的部分就不再多講，可以參考上面的網站XD，重點是線段樹的地方，這會等價於我們需要對一個陣列作「區間加(減)一個值」和「區間查詢有幾個值非0」，並且初使時整個陣列都是0。

用到區間加值當然可以想到懶人標記，但這時候會發現如果 ST[id] 直接存這個區間的答案的話會杯具，例如在對這個區間減值的時候，減完就不知道這個區間到底剩幾個非0的數了，必須遞回下去把左子樹根右子樹重算一遍，這樣如果考慮一直對同一個線段 +1 -1 +1 -1 ...... 的話，會讓單次修改的時間高達O(n)。

所以線段樹上不能直接存這個區間的答案。根據我對上面那篇連結裡的 code 的理解，想像現在有個線段樹，有好幾個區間有 tag ，把ST[ id ] 代表的區間叫作 [ L,R ] 好了，那麼 ST[ id ] 存的就是「考慮 id 的子孫們(不含 id 本身)的所有 tag 值，想像有另一個陣列 b[ L ] ~ b[ R ]，他們只有被剛才那些 tag 作用過，那麼  b[ L ] ~ b[ R ] 之間有幾個數非0」。這樣就能成功對區間加減值並且維護好線段樹上的值了，真是太神奇了OAO，然後每次修改之後 ST[ 1 ] 就是所求的答案了。詳細維護 ST[ id ] 作法就看 code 吧。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
struct P
{
    int x,d,u,val ;
    bool operator < (const P &rhs) const
    {
        return x<rhs.x ;
    }
}a[200000+10];
 
int ST[5*maxn],tag[5*maxn] ;
 
void modify(int l,int r,int L,int R,int id,int val)
{
    if(l==L && r==R) { tag[id]+=val ; return ; }
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,2*id,val) ;
    else if(l>mid) modify(l,r,mid+1,R,2*id+1,val) ;
    else
        modify(l,mid,L,mid,2*id,val) ,
        modify(mid+1,r,mid+1,R,2*id+1,val) ;
    ST[id]= (tag[2*id] ? mid-L+1 : ST[2*id]) +
            (tag[2*id+1] ? R-mid : ST[2*id+1]) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2 ;
        scanf("%d%d%d%d",&x1,&x2,&y1,&y2) ;
        a[2*i]=(P){x1,y1,y2-1,1} ;
        a[2*i+1]=(P){x2,y1,y2-1,-1} ;
    }
    sort(a,a+2*n) ;
 
    int x=0 , val=0 ;
    LL ans=0LL ;
    for(int i=0;i<2*n;i++)
    {
        ans+= (LL) (a[i].x-x)*val ;
        modify(a[i].d,a[i].u,0,maxn-1,1,a[i].val) ;
        x=a[i].x ;
        val=ST[1] ;
    }
    printf("%lld\n",ans) ;
}
 

[TIOJ 1223] 好想睡覺 之 好累的大頭蕃

作法：

如果考慮 n 條線段 [ 0,t ] ，分別代表 n 個房間，並且把題目給的限制的區間通通挖掉，這樣可以得到 <= m+n 個區間，題目就是要問給定一個點，哪個區間是包含他的而且右端點最右邊的。第一步當然是先把題目給的區間在同一個房間裡先合併好，然後求出「挖掉限制區間後的線段們」。再來對他們依左端點從小到大排序，一樣時依右端點從大到小排序(等一下處理會比較方便)，如果再一樣那就按照房間編號從小到大排序(因為題目要的是「如果有多個右端點都符合條件，那麼取房間編號最小的」)。並且可以知道如果區間A包含了區間B，且B的右端點 < A的右端點，那麼B就廢掉了。同理可以得到其它會讓一個區間廢掉的條件，所以可以用個 stack 作存活下來的區間們有哪些。但還要注意到，如果兩個區間都存活下來了，且他們的右端點不同，但是有交集，那麼在交集的部分一定是選右邊的區間比較好，所以有時候會需要把一個區間的右端點改小。

最後得到了存活下來的區間之後，只要二分搜哪個區間是滿足「左界 <= 詢問的時間」的最大區間，就可以得到答案了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
struct P
{
    int id,x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ?
            (y==rhs.y ? id<rhs.id : y>rhs.y) : x<rhs.x ;
    }
};
 
P tmp[2*maxn] ;
void cal(vector<P> &v)
{
    sort(v.begin(),v.end()) ;
    int cnt=0 ;
    for(auto i : v)
    {
        if(!cnt) { tmp[cnt++]=i ; continue ; }
        if(tmp[cnt-1].y >= i.y) continue ;
        else if(i.x <= tmp[cnt-1].y)
            tmp[cnt-1].y=max(tmp[cnt-1].y,i.y) ;
        else tmp[cnt++]=i ;
    }
    for(int i=0;i<cnt;i++) v[i]=tmp[i] ;
    v.resize(cnt) ;
}
 
vector<P> v[maxn],seg ;
int n,t ;
 
void cal_seg()
{
    seg.clear() ;
    for(int i=1;i<=n;i++)
    {
        if(v[i].empty())
            {seg.push_back((P){i,0,t}) ; continue ;}
        int sz=v[i].size() ;
        if(v[i][0].x) seg.push_back((P){i,0,v[i][0].x}) ;
        for(int j=0;j<sz-1;j++)
            seg.push_back((P){i,v[i][j].y,v[i][j+1].x}) ;
        if(v[i][sz-1].y < t) seg.push_back((P){i,v[i][sz-1].y,t}) ;
    }
    sort(seg.begin(),seg.end()) ;
    int cnt=0 ;
    for(auto i : seg)
    {
        if(!cnt) { tmp[cnt++]=i ; continue ; }
        if(i.y < tmp[cnt-1].y) continue ;
        if(i.y == tmp[cnt-1].y)
        {
            if(i.x==tmp[cnt-1].x) continue ;
            if(i.id > tmp[cnt-1].id) continue ;
        }
        tmp[cnt++]=i ;
        if(tmp[cnt-2].y < tmp[cnt-1].y)
            tmp[cnt-2].x=min(tmp[cnt-2].x,tmp[cnt-1].x) ;
    }
    for(int i=0;i<cnt;i++) seg[i]=tmp[i] ;
    seg.resize(cnt) ;
}
 
main()
{
    while(scanf("%d%d",&n,&t)==2 && n+t)
    {
        for(int i=1;i<=n;i++) v[i].clear() ;
        int m ; scanf("%d",&m) ;
        while(m--)
        {
            int id,x,y ; scanf("%d%d%d",&id,&x,&y) ;
            v[id].push_back((P){id,x,y}) ;
        }
        for(int i=1;i<=n;i++) if(!v[i].empty()) cal(v[i]) ;
 
        cal_seg() ;
 
        int Q ; scanf("%d",&Q) ;
        while(Q--)
        {
            int x ; scanf("%d",&x) ;
            if(seg.empty()) { printf("Oh, no!\n") ; continue ; }
            else if(seg[0].x > x) { printf("Oh, no!\n") ; continue ; }
            int l=0 , r=seg.size() ;
            while(r-l>1)
            {
                int mid=(r+l)/2 ;
                if(seg[mid].x <= x) l=mid ;
                else r=mid ;
            }
            if(seg[l].y<=x) printf("Oh, no!\n") ;
            else printf("%d %d\n",seg[l].id,seg[l].y-x) ;
        }
    }
}