2012 成都网络赛小记

一直想以优质的文章回馈互联网，无奈本菜太弱，只得修炼一段时日再一类类的总结

好了，废话不多说，今天的网络赛状态还好，只是有点小遗憾，DP太弱了

1001：一看就是裸的线段树，然后回想一下省赛的题，区间记录5个域，然后再记录下区间总共有几个数，信息上传的时候注意下取模即可

1002：转换一下模型其实就是拆点后求S 到 T 的最小切割，因为S出发到T一定会经过这些割边，要求最小的就是最小割啦

1004:打表题

1005：又是网络流，从左往右依次是 源点 食物 人 饮料 汇点 人需要拆点，因为人只能选择一次，然后就是食物向人的入点建边，人的出点向汇点建边，源点向食物建边，饮料向汇点建边

1006：每个人所在的组都可以看做一个区间，原题据说是http://poj.org/problem?id=2168

1007：学长说是DP，我的DP还是太弱了啊。。。。

1009：按 w+S 排个序，遍历一遍即可AC，我也不知道为什么

懒得贴代码：就贴下第一题吧

#include<cstring>#include<algorithm>using namespace std;typedef __int64 lld;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn = 100010;int sum[maxn<<2];lld ans[maxn<<2][5];int key[maxn];int x[maxn];int flag;char op[maxn][10];void pushup(int rt){    for(int i=0;i<5;i++){        ans[rt][i]=ans[rt<<1][i]+ans[rt<<1|1][(i-sum[rt<<1]%5+5)%5];    }}void update(int pos,int l,int r,int rt){    sum[rt]+=2*flag-1;    if(l==r){        ans[rt][0]=flag*key[pos];        return;    }    int m=(l+r)>>1;    if(pos<=m) update(pos,lson);    else update(pos,rson);    pushup(rt);}void build(int l,int r,int rt){    sum[rt]=0;    for(int i=0;i<5;i++) ans[rt][i]=0;    if(l==r)     return ;    int m=l+r>>1;    build(lson);    build(rson);}int main(){    int n,i,j;    while(scanf("%d",&n)!=EOF){        int sets=0;        int tot=0;        for(i=0;i<n;i++){            scanf("%s",op[i]);            if(op[i][0]=='a' || op[i][0]=='d') scanf("%d",&x[i]),key[tot++]=x[i];        }        if(tot>0){            sort(key,key+tot);            tot=unique(key,key+tot)-key;            build(0,tot-1,1);        }        for(i=0;i<n;i++){            int pos=lower_bound(key,key+tot,x[i])-key;            if(op[i][0]=='a') flag=1,update(pos,0,tot-1,1),sets++;            else if(op[i][0]=='d') flag=0,update(pos,0,tot-1,1),sets--;            else {                if(sets) printf("%I64d\n",ans[1][2]);                else printf("0\n");            }        }    }    return 0;}

2楼haha5935720134小时前

ni shuo na ti

1楼chen_zhan_ge4小时前

kan bu dong