edward_mj

POJ 2892 平衡树or线段树

题意：

给出直线上一系列的村庄，如果相邻村庄都没有被破坏，则两村庄是连接的，题目给出一系列的破坏操作，对指定号码的村庄进行破坏，还有一系列的询问操作，询问与指定号码的村庄直接相连或间接相连的村庄有几个，还有一个修复操作，是对最后破坏的村庄进行修复。

分析：

我们可以建立一棵平衡树，储存已经删除了的结点。

然后查询个数可以用平衡树找到比我大一点点的那个村庄和小一点点的那个村庄。

破坏的话就是插入了。

修复的话就是删除。

当然，线段树也可以实现这些操作。

插曲：

本来可以1A的。。。忘了删文件，又贡献WA一个。

第一次用类（对象）来写程序吖

code:

#include #include using namespace std;
const int N=1000000;
const int INF=0x7FFFFFFF;
int n,q,L[N],Lt=0,v[N];
class sbttype{
       public:
       int tot,root;
       struct treetype{int l,r,s,w;}tr[N];
       void Left(int &p){
            int t=tr[p].r;
            tr[p].r=tr[t].l;
            tr[t].l=p;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
            p=t;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
       }
       void Right(int &p){
            int t=tr[p].l;
            tr[p].l=tr[t].r;
            tr[t].r=p;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
            p=t;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
       }
       void Repair(int &p){
            bool flag=false;
            if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
              Right(p);
              flag=true;
            }
            if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
              Left(tr[p].l);
              Right(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
              Left(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
              Right(tr[p].r);
              Left(p);
              flag=true;
            }
            if (flag){
              Repair(tr[p].l);
              Repair(tr[p].r);
              Repair(p);
            }
       }
       void ins(int &p,int w){
            if (p==0){
              tr[++tot].l=0;
              tr[tot].r=0;
              tr[tot].s=1;
              tr[tot].w=w;
              p=tot;
              return;
            }
            if (w                      else ins(tr[p].r,w);
            Repair(p);
       }
       int del(int &p,int w){
           if (tr[p].w==w || tr[p].l==0 && w             int delnum=tr[p].w;
             if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
                                      else tr[p].w=del(tr[p].l,INF);
             return delnum;
           }
           if (w                     else return del(tr[p].r,w);
       }
       int fewmin(int p,int w){
           if (p==0) return 0;
           if (w<=tr[p].w) return fewmin(tr[p].l,w);
           return max(tr[p].w,fewmin(tr[p].r,w));
       }
       int fewmax(int p,int w){
           if (p==0) return n+1;
           if (w>=tr[p].w) return fewmax(tr[p].r,w);
           return min(tr[p].w,fewmax(tr[p].l,w));
       }
}sbt;

int main(){
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     scanf("%d%dn",&n,&q);
     sbt.root=0;
     sbt.tot=0;
     char ch;
     int x;
     for (int i=1;i<=q;i++){
         scanf("%c",&ch);
         if (ch==’R’){
           while (Lt>0 && v[L[Lt]]==0) Lt–;
           if (Lt>0){
             sbt.del(sbt.root,L[Lt]);
             v[L[Lt]]=0;
             Lt–;
           }
           scanf("n");
         }
         else if (ch==’Q’){
              scanf("%dn",&x);
              if (v[x]==1) {printf("0n");continue;}
              int tl=sbt.fewmin(sbt.root,x),tr=sbt.fewmax(sbt.root,x);
              printf("%dn",tr-tl-1);
         }
         else{
              scanf("%dn",&x);
              if (v[x]==1) continue;
              v[x]=1;
              sbt.ins(sbt.root,x);
              L[++Lt]=x;
         }
     }
    return 0;
}

SGU 148 堆优化+模拟 or 平衡树

题意：

有一个大水桶，里面有N层。从上至下标为1、2、3…层。

如果破坏某一层（需要一定代价），那么水就会流到下一层。

另外，如果某一层的水量超过了他能负荷的水量。也会自动爆炸。。。水就会自动流到下一层。

现在你是恐怖分子，求怎样花费最少，可以破坏掉第N层。

分析：

首先水不可能是断流的。因为这样上面一层就没有任何意义了。

所以我们可以枚举水开始下流在哪一层。如果中间遇到水量不够自动破坏，就需要破坏掉这一层（即付出相应花费）。

这样到达每一个层的水量就是sum(i,j)其中i为开始流的层，j表示当前层。

我们发现这满足单调性。我们把i从N枚举到1。再用堆or平衡树维护即可。

因为i减1不会破坏他们的大小关系。

code:

#include #include using namespace std;
const int N=20000;
const int INF=0x7FFFFFFF;
struct headtype{int limit,w,p,i;} heap[100000];
int n,tot=0,water[N],limit[N],p[N],Swater=0,outtime[N];

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++)
       scanf("%d%d%d",&water[i],&limit[i],&p[i]);
}

inline int f(int t){
return (heap[t].limit-heap[t].w);
}

void up(int k){
     while (k>1 && f(k/2)>f(k)){
           swap(heap[k],heap[k/2]);
           k/=2;
     }
}

void down(int k){
     while (k*2<=tot){
           int t;
           if (k*2+1<=tot && f(k*2+1)                                         else t=k*2;
           if (f(t)           k=t;
     }
}

void ins(int W,int L,int P,int i){
     tot++;
     heap[tot].w=W;
     heap[tot].limit=L;
     heap[tot].p=P;
     heap[tot].i=i;
     up(tot);
}

void del(){
     heap[1]=heap[tot];
     tot–;
     down(1);
}

void work(){
     int ans=INF,now=0,ansi=0;
     for (int i=n;i>=1;i–){
         Swater+=water[i];
         now+=p[i];
         ins(water[i]-Swater,limit[i],p[i],i);
         while (tot>0 && heap[1].w+Swater>heap[1].limit){
               now-=heap[1].p;
               outtime[heap[1].i]=i;
               del();
         }
         if (now           ans=now;
           ansi=i;
         }
     }
     for (int i=ansi;i<=n;i++)
       if (outtime[i]}

int main(){
init();
work();
}

线性规划与网络流之7 试题库问题网络流

题目：

假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别
属性。现要从题库中抽取 m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个
满足要求的组卷算法。

由文件input.txt提供输入数据。文件第1行有2个正整数n和k (2 <=k<= 20, k<=n<= 1000)
k 表示题库中试题类型总数，n 表示题库中试题总数。第 2 行有 k 个正整数，第 i 个正整数
表示要选出的类型i的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题
库中每个试题的类型信息。每行的第1 个正整数 p表明该题可以属于 p类，接着的 p个数是
该题所属的类型号。

分析：

明显的网络流模型，对于每个试题，连一条边(S,i,1)

对于每个试题类型，连一条边(i,T,tmp)。其中tmp表示这个类型需要多少题。

然后最大流。

如果流量等于SUM(tmp)，有解，按要求输出，否则，输出No Solution！

HINT
我写的check程序(No Solution 请手测)：

#include using namespace std;

int n,m,a[2000][2000],num[2000],v[2000];

void init(){
     cin >> m >> n;
     for (int i=1;i<=m;i++) scanf("%d",&num[i]);
     for (int i=1;i<=n;i++){
         int num,tmp;
         scanf("%d",&num);
         for (int j=1;j<=num;j++){
           scanf("%d",&tmp);
           a[i][tmp]=1;
         }
     }
}

bool work(){
     for (int i=1;i<=m;i++){
         int tmp;
         scanf("%d:",&tmp);
         if (tmp!=i) return false;
         for (int j=1;j<=num[i];j++){
           scanf("%d",&tmp);
           if (v[tmp]==1) return false;
           if (a[tmp][i]==0) return false;
           v[tmp]=1;
         }
     }
     return true;
}

int main(){
    freopen("input.txt","r",stdin);
    init();
    freopen("output.txt","r",stdin);
    freopen("result.txt","w",stdout);
    if (work()) cout << "AC" << endl;
          else cout << "WA" << endl;
}

code：

#include using namespace std;
const int P=10000;
const int E=2000000;
const int INF=0x7FFFFFFF;
struct gtp{int x,y,next,c,op;}g[E];
int n,m,e=0,ls[P],fa[P],cur[P],d[P],num[P],total=0;
int link[1000][1000];

inline void addedge(int x,int y,int c){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
       e++;
       g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}

void init(){
     scanf("%d%d",&m,&n);
     for (int i=1;i<=n;i++) addedge(0,i,1);
     for (int i=1;i<=m;i++){
         int tmp;
         scanf("%d",&tmp);
         addedge(n+i,m+n+1,tmp);
         total+=tmp;
     }
     for (int i=1;i<=n;i++){
         int num,tmp;
         scanf("%d",&num);
         for (int j=1;j<=num;j++){
             scanf("%d",&tmp);
             addedge(i,tmp+n,1);
         }
     }
}

void relabel(int k){
     int min=m+n+1;
     cur[k]=ls[k];
     for (int i=ls[k];i!=0;i=g[i].next)
       if (g[i].c>0 && d[g[i].y]         min=d[g[i].y];
     d[k]=min+1;
}

void change(int &flow){
     int nf=INF;
     for (int i=n+m+1;i!=0;i=g[fa[i]].x)
       if (g[fa[i]].c     flow+=nf;
     for (int i=n+m+1;i!=0;i=g[fa[i]].x){
         g[fa[i]].c-=nf;
         g[g[fa[i]].op].c+=nf;
     }
}

int sap(){
    int flow=0;
    for (int i=0;i<=n+m+1;i++){
        d[i]=0;
        cur[i]=ls[i];
        num[i]=0;
    }
    num[0]=n+m+2;
    int i=0;
    while (d[0]          while (cur[i]!=0){
                if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
                cur[i]=g[cur[i]].next;
          }
          if (cur[i]==0){
            num[d[i]]–;
            if (num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=0) i=g[fa[i]].x;
          }
          else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==n+m+1){
              change(flow);
              i=0;
            }
          }
    }
    return flow;
}

void work(){
     int flow=sap();
     if (flow     else{
          for (int i=1;i<=e;i++)
            if (i%2==1 && g[i].c==0 && 1<=g[i].x && g[i].x<=n && n+1<=g[i].y && g[i].y<=n+m){
              link[g[i].y-n][0]++;
              link[g[i].y-n][link[g[i].y-n][0]]=g[i].x;
            }
          for (int i=1;i<=m;i++){
            cout << i << ":";
            for (int j=1;j<=link[i][0];j++)
              cout << link[i][j] << " ";
            cout << endl;
          }
     }
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    init();
    work();
}

C++随机学习笔记

一直还在用pascal做数据。。。现在终于学会了C++的随机。

首先需要

#include

写一个srand((unsigned)time(NULL)) （随机种子）

然后就可以这样用了。t=rand()%xxxx；

但是比赛的时候是不允许读时间的，所以比赛的时候直接rand()就可以得到一串随机数。但是每次运行程序的结果是一样的(但每次rand()的结果不一样)。

所以做数据对拍的时候我们可以用那个随机种子。

比赛时直接rand()就可以了。

线性规划与网络流之6 构图、网络流

题目参见：http://www.byvoid.com/blog/lpf24-solution/

题意：给定A[1],A[2]…A[N]

Question1：最长上升子序列的长度是多少？

Question2：从这个序列中，最多能取出多少个没有重复使用的元素的上升子序列。其长度=Question1

Question3：同2，但A[1]和A[N]能使用无限次。

分析：

第一问：DP

第二问：

对于f[i]=1的点加一条边(S,i,1)

对于f[i]=len的点加一条边(i,T,1)

对于a[j]

求最大流

第三问：

在第二问的图的基础上加入以下两条边

(S,1,INF)

如果f[n]=len，加这条边(n,T,INF)

求最大流

HINT:

1、len表示第一问的答案。

2、我的程序是从0开始的。。。和分析有点出入

code:

#include #define E 4000000
#define N 1000000
using namespace std;
const int INF=0x7FFFFFFF/2;
struct gtp{int x,y,next,c,op;} g[E];
int n,a[500],f[500],e,ls[N],d[N],num[N],cur[N],fa[N],S,T,Flow;

int problem1(){
     for (int i=0;i     int ans=1;
     for (int i=1;i       for (int j=0;j         if (a[j]           f[i]=f[j]+1;
           ans=max(f[i],ans);
         }
     return ans;
}

void add(int x,int y,int c){
     e++;
     g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
     e++;
     g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}

void relabel(int k){
     int min=T,i=ls[k];
     cur[k]=ls[k];
     while (i!=0){
       if (g[i].c>0 && d[g[i].y]       i=g[i].next;
     }
     d[k]=min+1;
}

void change(){
     int nf=INF;
     for (int i=T;i!=S;i=g[fa[i]].x)
       if (g[fa[i]].c     Flow+=nf;
     for (int i=T;i!=S;i=g[fa[i]].x){
         g[fa[i]].c-=nf;
         g[g[fa[i]].op].c+=nf;
     }
}

void sap(){
     Flow=0;
     for (int i=0;i<=T;i++){
         d[i]=0;
         num[i]=0;
         cur[i]=ls[i];
     }
     num[0]=T+1;
     int i=S;
     while (d[S]<=T){
           while (cur[i]!=0){
                 if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
                 cur[i]=g[cur[i]].next;
           }
           if (cur[i]==0){
             num[d[i]]–;
             if (num[d[i]]==0) break;
             relabel(i);
             num[d[i]]++;
             if (i!=S) i=g[fa[i]].x;
           }
           else{
             fa[g[cur[i]].y]=cur[i];
             i=g[cur[i]].y;
             if (i==T){
               change();
               i=S;
             }
           }
     }
}

void problem2(int len){
     memset(ls,0,sizeof(ls));
     S=n;
     T=n+1;
     e=0;
     for (int i=0;i       if (f[i]==1) add(S,i,1);
       if (f[i]==len) add(i,T,1);
     }
     for (int i=0;i       for (int j=i+1;j         if (a[i]     sap();
     cout << Flow << endl;
}

void problem3(int len){
     memset(ls,0,sizeof(ls));
     S=n;
     T=n+1;
     e=0;
     add(S,0,INF);
     if (f[n-1]==len) add(n-1,T,INF);
     for (int i=0;i       if (f[i]==1) add(S,i,1);
       if (f[i]==len) add(i,T,1);
     }
     for (int i=0;i       for (int j=i+1;j         if (a[i]     sap();
     cout << Flow << endl;
}

int main(){
    freopen("alis.in","r",stdin);
    freopen("alis.ans","w",stdout);
    scanf("%d",&n);
    for (int i=0;i    int len=problem1();
    cout << len << endl;
    problem2(len);
    problem3(len);
    return 0;
}