[POI 19 Stage 2] Tour de Byteotia

作法：

以下稱編號 1 ~ k 的點為黑點，所以問題等價成要取最多的邊，使得黑點都不落在圈上。如果在一種邊的取法之中，有一條兩端點都不是黑點的邊沒有被取到，那麼加上這條邊之後，至多會形成一個包含黑點的圈（否則可以推出原本就有包含黑點的圈，矛盾），所以可以任意拔掉一條圈上的連接黑點的邊。由這個結論可以得到如果一條邊的兩端點都不是黑的，那麼一定可以取這條邊。所以一開始就先把所有的這種邊加進來，用並查集維護，把連接起來的點都縮成一坨。這樣問題就變成了要在好幾坨點和好幾個黑點之間加上最多條邊，使得加完之後不存在圈（注意到縮完之後任兩坨之間不會有任何邊）。而這也是用並查集就可以解決了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
struct P{int x,y;};
 
int fa[maxn] ;
int getfa(int x)
{
     return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
vector<P> v,ans ;
main()
{
     int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
     for(int i=1;i<=n;i++) fa[i]=i ;
     while(m--)
     {
          int x,y ; scanf("%d%d",&x,&y) ;
          if(x>k && y>k) fa[getfa(x)]=getfa(y) ;
          else v.push_back((P){x,y}) ;
     }
     for(int i=0;i<v.size();i++)
     {
          int x=getfa(v[i].x) , y=getfa(v[i].y) ;
          if(x==y) ans.push_back(v[i]) ;
          else fa[x]=y ;
     }
     printf("%d\n",ans.size()) ;
     for(int i=0;i<ans.size();i++) printf("%d %d\n",ans[i].x,ans[i].y) ;
}
 

[POI 20 Stage 2] Tales of seafaring

作法：

因為可以重複走好幾次同樣的邊，所以可以想到一直在同樣一條邊來回走，就可以一直讓路徑長增加 2 。所以只要預處理出任兩個點之間的最短的奇數長路徑和偶數長路徑就可以了，並且也容易證明這是充要條件。

code :

#include<bits/stdc++.h>
#define INF 30000
using namespace std;
const int maxn=5000+5 ;
 
short d[maxn][2*maxn] ;
vector<int> v[maxn] ;
int n,que[2*maxn] ;
void BFS(int i,short *dis)
{
     int head=0 , tail=0 ;
     for(int i=1;i<=2*n;i++) dis[i]=INF ;
     que[0]=i ; dis[i]=0 ;
     while(tail<=head)
     {
          int u=que[tail++] , tp=(u>n ? 0 : 1) , u2=(u>n ? u-n : u) ;
          for(int i=0;i<v[u2].size();i++)
          {
               int to= v[u2][i]+tp*n ;
               if(dis[to]==INF) dis[to]=dis[u]+1 , que[++head]=to ;
          }
     }
}
 
main()
{
     int m,Q ; scanf("%d%d%d",&n,&m,&Q) ;
     while(m--)
     {
          int x,y ; scanf("%d%d",&x,&y) ;
          v[x].push_back(y) ;
          v[y].push_back(x) ;
     }
     for(int i=1;i<=n;i++) BFS(i,d[i]) ;
     while(Q--)
     {
          int x,y,k ; scanf("%d%d%d",&x,&y,&k) ;
          int d1=(int)d[x][y] , d2=(int)d[x][y+n] ;
          if(v[x].empty()) printf("NIE\n") ;
          else if(d1!=INF && ((k-d1)%2==0) && k>=d1) printf("TAK\n") ;
          else if(d2!=INF && ((k-d2)%2==0) && k>=d2) printf("TAK\n") ;
          else printf("NIE\n") ;
     }
}
 

[POI 20 Stage 2] Watering can

作法：

建一個可以區間加值和區間查詢最大值與最大值位置的線段樹，作法是每次就直接對要加值的區間加值，然後對那個區間查詢最大值，如果最大值 >= k ，那麼在之後他就永遠會 >= k 了，所以可以直接把他調成負無限大，並把他標記起來。重複這個步驟直到最大值 < k 為止。並且再用另外一棵線段樹紀錄一個區間裡面已經有幾個數被標記了，就可以對他做查詢了。

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=300000+10 ;
 
struct P{int val,tag,id;}ST[4*maxn];
struct RET{int val,id;};
int ST2[4*maxn] ;
 
int n,k,a[maxn] ;
 
void pull(int id)
{
     ST[id].val = max(ST[2*id].val,ST[2*id+1].val) ;
     if(ST[2*id].val > ST[2*id+1].val) ST[id].id=ST[2*id].id ;
     else ST[id].id=ST[2*id+1].id ;
}
 
void push(int id)
{
     if(!ST[id].tag) return ;
     int t=ST[id].tag ;
     ST[2*id].val+=t ; ST[2*id].tag+=t ;
     ST[2*id+1].val+=t ; ST[2*id+1].tag+=t ;
     ST[id].tag=0 ;
}
 
void build(int l,int r,int id)
{
     if(l==r) { ST[id]=(P){a[l],0,l} ; return ; }
     int mid=(l+r)/2 ;
     build(l,mid,2*id) ;
     build(mid+1,r,2*id+1) ;
     pull(id) ;
}
 
void add(int l,int r,int L,int R,int id,int val)
{
     if(l==L && r==R) { ST[id].val+=val ; ST[id].tag+=val ; return ; }
     push(id) ;
     int mid=(L+R)/2 ;
     if(r<=mid) add(l,r,L,mid,2*id,val) ;
     else if(l>mid) add(l,r,mid+1,R,2*id+1,val) ;
     else add(l,mid,L,mid,2*id,val) ,
          add(mid+1,r,mid+1,R,2*id+1,val) ;
     pull(id) ;
}
 
RET cal(const RET &x,const RET &y)
{
     RET r ;
     r.val=max(x.val,y.val) ;
     if(x.val > y.val) r.id=x.id ;
     else r.id=y.id ;
     return r ;
}
 
RET query(int l,int r,int L,int R,int id)
{
     if(l==L && r==R) return (RET){ST[id].val,ST[id].id} ;
     int mid=(L+R)/2 ;
     if(r<=mid) return query(l,r,L,mid,2*id) ;
     else if(l>mid) return query(l,r,mid+1,R,2*id+1) ;
     else return cal(query(l,mid,L,mid,2*id),
                     query(mid+1,r,mid+1,R,2*id+1)) ;
}
 
void modify2(int L,int R,int id,int pos)
{
     if(L==R) { ST2[id]++ ; return ; }
     int mid=(L+R)/2 ;
     if(pos<=mid) modify2(L,mid,2*id,pos) ;
     else modify2(mid+1,R,2*id+1,pos) ;
     ST2[id]++ ;
}
 
int query2(int l,int r,int L,int R,int id)
{
     if(l==L && r==R) return ST2[id] ;
     int mid=(L+R)/2 ;
     if(r<=mid) return query2(l,r,L,mid,2*id) ;
     else if(l>mid) return query2(l,r,mid+1,R,2*id+1) ;
     else return query2(l,mid,L,mid,2*id)+query2(mid+1,r,mid+1,R,2*id+1) ;
}
 
void inicjuj(int N,int K,int *D)
{
     n=N ; k=K ;
     for(int i=1;i<=n;i++) a[i]=D[i-1] ;
     build(1,n,1) ;
     while(1)
     {
          RET tmp=query(1,n,1,n,1) ;
          if(tmp.val < k) break ;
          modify2(1,n,1,tmp.id) ;
          add(tmp.id,tmp.id,1,n,1,-INF) ;
     }
}
 
void podlej(int l,int r)
{
     l++ ; r++ ;
     add(l,r,1,n,1,1) ;
     while(1)
     {
          RET tmp=query(l,r,1,n,1) ;
          if(tmp.val < k) break ;
          modify2(1,n,1,tmp.id) ;
          add(tmp.id,tmp.id,1,n,1,-INF) ;
     }
}
 
int dojrzale(int l,int r)
{
     return query2(l+1,r+1,1,n,1) ;
}
 

[POI 20 Stage 2] Triumphal arch

作法：

首先最外層二分答案，那麼這個問題就可以看成一個遊戲：先手是工人們，後手是國王，先手每次可以把樹上的 k 個點塗黑，後手可以移動到一個相鄰的點。如果後手移動到沒有塗黑的點就贏了。一開始國王在 1 號節點，且 1 已經被塗黑了，問先手是否必勝。

而這只要對每個子樹DP出：若國王現在在這個子樹的根，並且根已經塗黑了，那麼這棵子樹裡必須要預先塗好至少幾個黑點才能讓先手獲勝，這樣就不難列出轉移式了，並且最後如果整棵樹還需要預先塗好 > 0 個黑點的話就會是後手贏，否則先手贏。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10 ;
 
vector<int> v[maxn] ;
 
int dfs(int x,int f,int num)
{
     if(x!=1 && v[x].size()==1) return 0 ;
     int val=0 ;
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          val+=dfs(v[x][i],x,num)+1 ;
     return max(0,val-num) ;
}
 
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) ;
     }
 
     int l=-1 , r=n-1 ;
     while(r-l>1)
     {
          int mid=(r+l)/2 ;
          if(dfs(1,1,mid)==0LL) r=mid ;
          else l=mid ;
     }
     printf("%d\n",r) ;
}
 

[POI 21 Stage 2] Little Bird

作法：

這題是單調隊列優化DP。當我們在算 dp[ i ] 的時候，會需要考慮到 dp[ i - k ] ~ dp[ i - 1 ] ，但如果這裡面存在 x , y 滿足 x < y 且 dp[ x ] > dp[ y ] ，那麼 x 就廢掉了，因為這裡的 DP 有個重要的性質，就是每次的轉移只會等於上一個的值或是上一個的值+1，所以在怎麼樣用 dp[ y ] 轉移 dp[ i ] 時大不了值多 1 而已，dp[ x ] 永遠不會比 dp[ y ] 好。所以只要維護一個 deque ，裡面保持 dp 值是遞增的，如果 dp 值一樣的話，就要把點的高度考慮進來了。因為越高的點在轉移時可以越有機會不用讓 dp 值增加，所以當 x 和 y 的 dp 值一樣 ( x < y )，且 a[ y ] > a[ x ] 時， x 就廢掉了，把他從 deque 裡 pop 掉。最後記得每次要從 deque 後面把過期的東西 pop 掉。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int n,k ;
int a[maxn],dp[maxn] ;
deque<int> dq ;
 
main()
{
     scanf("%d",&n) ;
     for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
     int Q ; scanf("%d",&Q) ;
     while(Q--)
     {
          scanf("%d",&k) ;
          dq.clear() ;
          dp[1]=0 ; dq.push_front(1) ;
          for(int i=2;i<=n;i++)
          {
               while(dq.back()+k < i) dq.pop_back() ;
               dp[i]= a[dq.back()]>a[i] ? dp[dq.back()] : dp[dq.back()]+1 ;
               while(!dq.empty() && dp[dq.front()]>dp[i]) dq.pop_front() ;
               while(!dq.empty() && dp[dq.front()]==dp[i] && a[i]>a[dq.front()])
                    dq.pop_front() ;
               dq.push_front(i) ;
          }
          printf("%d\n",dp[n]) ;
     }
}
 

[POI 21 Stage 2] Criminals

作法：

第一個人從左到右跳的過程很明顯是用貪心最好，而如果考慮把這個過程反過來，就變成當我們決定好終點時，就一直往左邊跳，並且也是貪心的跳最近的，右邊也同理。而因為他給的條件保證一個人在跳的時候經過的顏色都不一樣，所以當我們考慮從左跳到右的人時，只要紀錄每個點往左跳（現在已經把整個過程反過來了）會跳到哪裡就可以了。而處理完這件事之後。就可以利用類似並查集的作法得到對於一個終點顏色，他往左跳到底會跳到誰。而從右邊出發的人也同理，可以找出對每個終點顏色，他往右跳到底會跳到誰。

這樣左邊和右邊就會分別跳到兩個點，叫他們 x 和 y 好了，這時候我們需要查詢 1 ~ x-1 之間和 y+1 ~ n 之間是否有一樣的數，這樣才可以讓他們兩人的起點顏色一樣。而這件事可以反過來想，只要處理出對於一個 u ，滿足 1 ~ u 和 v ~ n 之中有相同顏色的最大的 v 是誰就可以了，這只會花O( n ) 的時間。最後我傳上去後拿到 OK 99 分，加了輸入優化之後才拿100。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int getint()
{
     char c=getchar() ;
     while(c<'0' || c>'9') c=getchar() ;
     int x=0 ;
     while(1)
     {
          x=x*10+(c-'0') ;
          c=getchar() ;
          if(c<'0' || c>'9') return x ;
     }
}
 
vector<int> v[maxn] ;
 
int a[maxn] ;
int p[maxn],q[maxn] ;
int le[maxn],ri[maxn] ;
 
int num1[maxn],num2[maxn],R[maxn] ;
vector<int> ans ;
 
main()
{
     int n=getint(),k=getint() ;
     for(int i=1;i<=n;i++)
     {
          a[i]=getint() ;
          v[a[i]].push_back(i) ;
          ri[i]=n+1 ;
     }
     ri[n+1]=n+1 ;
 
     int m=getint(),l=getint() ;
     for(int i=1;i<=m;i++) p[i]=getint() ;
     for(int i=1;i<=l;i++) q[i]=getint() ;
     for(int i=1;i<m;i++) for(int j=0;j<v[p[i+1]].size();j++)
     {
          int x=v[p[i+1]][j] ;
          int id=lower_bound(v[p[i]].begin(),v[p[i]].end(),x)
                    -v[p[i]].begin()-1 ;
          if(id>=0) le[x]=v[p[i]][id] ;
          if(i!=1) le[x]=le[le[x]] ;
     }
 
     for(int i=1;i<l;i++) for(int j=0;j<v[q[i+1]].size();j++)
     {
          int x=v[q[i+1]][j] ;
          int id=lower_bound(v[q[i]].begin(),v[q[i]].end(),x)
                    -v[q[i]].begin() ;
          if(id<v[q[i]].size()) ri[x]=v[q[i]][id] ;
          if(i!=1) ri[x]=ri[ri[x]] ;
     }
 
     for(int i=1;i<=n;i++) num2[a[i]]++ ;
     for(int i=1 , j=1 , now=0;i<=n;i++)
     {
          num1[a[i]]++ ;
          if(num1[a[i]]==1 && num2[a[i]]) now++ ;
          while(j<=n)
          {
               num2[a[j]]-- ;
               if(!num2[a[j]] && num1[a[j]]) now-- ;
               if(!now) { num2[a[j]]++ ; now++ ; break ; }
               j++ ;
          }
          R[i]=j ;
     }
     for(int i=1;i<=n;i++) if(a[i]==p[m])
     {
          int x= (m==1 ? i : le[i]) ;
          int y= (l==1 ? i : ri[i]) ;
          if(x>1 && y<n && R[x-1]>=y+1)
               ans.push_back(i) ;
     }
     printf("%d\n",ans.size()) ;
     for(int i=0;i<ans.size();i++)
        printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
     if(ans.empty()) printf("\n") ;
}
 

[POI 21 Stage 2] Cards

作法：

我們想要知道的東西是，若第一張卡取小的那個，那麼是否有辦法在取到最後一張時是取到小的或是大的。而這個東西有可以合併的性質，也就是可以從兩個小的區間的答案算出大區間的答案。所以我們考慮建一棵線段樹，每個節點 [ L , R ]紀錄兩個值，代表在第 L 張卡片取小的那個或是大的那個時，在第 R 張卡片必須要取小的還是大的，若無法達成目標則為 -1 。這樣就只要在交換兩張卡片時對那兩個交換的位置重算就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
int ST[4*maxn][2] ;
int a[2][maxn] ;
 
inline int cal(int pos,int x,int y)
{
    if(pos>y) return -1 ;
    if(pos>x) return 1 ;
    return 0 ;
}
 
void pull(int l,int r,int id)
{
    int mid=(l+r)/2 ;
    for(int i=0;i<2;i++)
    {
        if(ST[2*id][i]==-1) ST[id][i]=-1 ;
        else
        {
            int tmp=cal(a[ST[2*id][i]][mid],a[0][mid+1],a[1][mid+1]) ;
            ST[id][i]= (tmp==-1 ? -1 : ST[2*id+1][tmp]) ;
        }
    }
}
 
void build(int l,int r,int id)
{
    if(l==r)
    {
        ST[id][0]=0 ;
        ST[id][1]=1 ;
        return ;
    }
    int mid=(l+r)/2 ;
    build(l,mid,2*id) ;
    build(mid+1,r,2*id+1) ;
    pull(l,r,id) ;
}
 
void modify(int L,int R,int id,int pos)
{
    if(L==R) return ;
    int mid=(L+R)/2 ;
    if(pos<=mid) modify(L,mid,2*id,pos) ;
    else modify(mid+1,R,2*id+1,pos) ;
    pull(L,R,id) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[0][i],&a[1][i]) ;
        if(a[0][i]>a[1][i]) swap(a[0][i],a[1][i]) ;
    }
 
    build(1,n,1) ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int l,r ; scanf("%d%d",&l,&r) ;
        swap(a[0][l],a[0][r]) ;
        swap(a[1][l],a[1][r]) ;
        modify(1,n,1,l) ;
        modify(1,n,1,r) ;
        printf("%s\n",ST[1][0]==-1 ? "NIE" : "TAK") ;
    }
}