首页 > 代码库 > [原博客] POI系列(1)

[原博客] POI系列(1)

正规、严谨、精妙。 -POI

  发现POI(波兰信息学奥赛)的题都很有意思。于是开刷bzoj上的poi题目(按ac人数降序。。)。顺手写一写题解,加深印象。
  为了防止一篇文章过于长,打算每五道题另起一篇文章。


  BZOJ 1103 : [POI2007]大都市meg

  给一棵树,每次可以把树上的一些边标记了,问一个点与根之间需要走多少没有标记的边。

  这个可以把这颗树遍历得到一个dfs序每第一次经过一个点的时候记录为+1,第二次经过一个点的时候记录为-1,然后记录每个点第一次经过时在序列里的位置f[i]和第二次经过在序列里的位置l[i],对于查询(x)就是序列中一直到f[x]-1的前缀和,因为真正没走的那些边都+1-1消掉了,只剩下真正要统计的边了。对于每次标记(a,b) 设a<b 就是序列里 f[b]的位置-1,l[b]的位置+1,就相当于消掉了这条边。另外这道题得手写栈dfs,否则会爆栈。

/**************************************************************    Problem: 1103    User: zrts    Language: C++    Result: Accepted    Time:4484 ms    Memory:9596 kb****************************************************************/ #include<cstdio>#include<cstring>#include<algorithm>#define lowbit(x) (x&-x)//by zrt//problem:using namespace std;typedef long long ll;const double eps(1e-10);int n,m;char s[10];int H[250005],P[250005],X[250005],tot;int f[250005],l[250005];int c[500005];int tim;int stk[500005],top;void add(int pos,int x){    for(;pos<=n;pos+=lowbit(pos)){        c[pos]+=x;    }}int ask(int pos){    int ret=0;    for(;pos>0;pos-=lowbit(pos)){        ret+=c[pos];    }    return ret;}inline void Add(int x,int y){    P[++tot]=y;X[tot]=H[x];H[x]=tot;}int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    scanf("%d",&n);    for(int i=1,x,y;i<n;i++){        scanf("%d%d",&x,&y);        if(x<y) Add(x,y);        else Add(y,x);    }    stk[top++]=1;    int k;    while(top>0){        k=stk[--top];        if(f[k]){            l[k]=++tim;            c[tim]=-1;            continue;        }else{            f[k]=++tim;            c[tim]=1;            stk[top++]=k;            for(int i=H[k];i;i=X[i]){                stk[top++]=P[i];            }            continue;        }    }    n*=2;    for(int i=1;i<n;i++){        if(i+lowbit(i)<=n){            c[i+lowbit(i)]+=c[i];        }    }    scanf("%d",&m);    m=n/2+m-1;    for(int i=0,x,y;i<m;i++){        scanf("%s",s);        if(s[0]==W){            scanf("%d",&x);            printf("%d\n",ask(f[x])-1);        }else{            scanf("%d%d",&x,&y);            if(x>y){                add(f[x],-1);                add(l[x],1);            }else{                add(f[y],-1);                add(l[y],1);            }        }    }    return 0;}
View Code

 

  BZOJ 1121 : [POI2008]激光发射器SZK

  刚看完觉得不可做。
  因为光线都是沿45°,所以从一个点发射光线必有一个点接收,又因为光路是可逆的,不可能有不同的点出发的光路重合的现象,所以输出n/2(原题让输出方案。。);

/**************************************************************    Problem: 1121    User: zrts    Language: C++    Result: Accepted    Time:0 ms    Memory:804 kb****************************************************************/ #include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;typedef long long ll;const double eps(1e-10); int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    int n;    scanf("%d",&n);    printf("%d",n>>1);    return 0;}
View Code

 

  BZOJ 1113 : [Poi2008]海报PLA

  显然单调栈啊,相等的时候处理一下。没了。

/**************************************************************    Problem: 1113    User: zrts    Language: C++    Result: Accepted    Time:1496 ms    Memory:1780 kb****************************************************************/ #include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;typedef long long ll;const double eps(1e-10);int stk[250005],top;int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    int n;    scanf("%d",&n);    int ans=0;    for(int i=0,x;i<n;i++){        scanf("%*d%d",&x);        while(top>0&&x<=stk[top-1]) {            top--,ans++;            if(stk[top]==x) ans--;        }        stk[top++]=x;    }    printf("%d\n",ans+top);    return 0;}
View Code

 

  BZOJ 1529 : [POI2005]ska Piggy banks

  一堆存钱罐,每个存钱罐的钥匙在另一个存钱罐里,问最少砸烂多少个存钱罐。
  如果A罐的钥匙在B罐里,我们连边B->A,表示只要开了B就能开A。然后得到一张无向图,显然在一个强连通分量中的罐子最多只用砸烂一个,而每个强连通分量的罐子有可能被别的强连通分量的罐子打开,所以将这张图缩点,得到一个DAG,显然我们只用砸那些入度为0的强连通分量并且每个分量砸一个就ok了,也就是DAG的叶子节点。
(原来tarjan中,dfn没有记录的必要啊,详见程序。)

/**************************************************************    Problem: 1529    User: zrts    Language: C++    Result: Accepted    Time:2316 ms    Memory:63620 kb****************************************************************/ #include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;typedef long long ll;const double eps(1e-10);int n;int H[1000005],X[1000005],P[1000005],tot;inline void add(int x,int y){    P[++tot]=y;X[tot]=H[x];H[x]=tot;}int tim,low[1000005],stk[1000005],top;bool instack[1000005];int cnt;int belong[1000005];void tarjan(int x){    int dfn=low[x]=++tim;    instack[x]=1;stk[top++]=x;    for(int i=H[x];i;i=X[i]){        if(!low[P[i]]) tarjan(P[i]),low[x]=min(low[x],low[P[i]]);        else if(instack[P[i]]) low[x]=min(low[x],low[P[i]]);    }    if(low[x]==dfn){        cnt++;        int k;        do{            k=stk[--top];            instack[k]=0;            belong[k]=cnt;        }while(k!=x);    }}bool ind[1000005];int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    scanf("%d",&n);    for(int i=1,x;i<=n;i++){        scanf("%d",&x);        add(x,i);    }    for(int i=1;i<=n;i++){        if(!low[i]) tarjan(i);    }    for(int i=1;i<=n;i++){        for(int j=H[i];j;j=X[j]){            if(belong[i]!=belong[P[j]]) ind[belong[P[j]]]=1;        }    }    int ot=0;    for(int i=1;i<=cnt;i++){        if(!ind[i]) ot++;    }    printf("%d\n",ot);    return 0;}
View Code

 

  BZOJ 1532 : [POI2005]Kos-Dicing

  网络流里这个模型太熟了。
  首先求最大值最小先二分,然后判定是否可以相互制约使得都在ans场内决出冠军。具体连边就是S向每场比赛连边容量为1,每场比赛向两个人分别连边,容量1。然后每个人向T连边,容量为ans。看看最大流S是否满载。搞定。

/**************************************************************    Problem: 1532    User: zrts    Language: C++    Result: Accepted    Time:576 ms    Memory:2764 kb****************************************************************/ #include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;typedef long long ll;const double eps(1e-10);int n,m;int H[20005],X[110005],P[110005],flow[110005],d[20005],tot;int q[20005],h,t;int a[10005],b[10005];int S,T;inline void add(int x,int y,int z){    P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;}bool bfs(){    memset(d,0,sizeof d);h=t=0;    d[S]=1;q[t++]=S;    int k;    while(h!=t){        k=q[h++];        for(int i=H[k];i;i=X[i]){            if(flow[i]>0&&(!d[P[i]])){                q[t++]=P[i];                d[P[i]]=d[k]+1;            }        }    }    return d[T];}int dfs(int x,int a){    if(a==0||x==T) return a;    int f=a,tmp;    for(int i=H[x];i&&a;i=X[i]){        if(d[P[i]]==d[x]+1&&flow[i]>0){            tmp=dfs(P[i],min(a,flow[i]));            a-=tmp;            flow[i]-=tmp;            flow[i^1]+=tmp;        }    }    if(f==a) d[x]=-1;    return f-a;}int dinic(){    int f(0);    while(bfs()){        f+=dfs(S,1<<30);    }    return f;}bool judge(int x){    memset(H,0,sizeof H);tot=1;    for(int i=0;i<m;i++){        add(S,i,1);add(i,S,0);        add(i,a[i]+m,1);add(a[i]+m,i,0);        add(i,b[i]+m,1);add(b[i]+m,i,0);    }    for(int i=1;i<=n;i++) add(i+m,T,x),add(T,i+m,0);    if(dinic()>=m) return true;    else return false;}int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    scanf("%d%d",&n,&m);    for(int i=0;i<m;i++){        scanf("%d%d",&a[i],&b[i]);    }    int L(0),R(m),M;    S=20003,T=20004;    while(R-L>1){        M=(L+R)>>1;        if(judge(M)){            R=M;        }else L=M;    }    printf("%d\n",R);    return 0;}
View Code

 


以上。

[原博客] POI系列(1)