Archive

Posts Tagged ‘OI’

栈都做了些什么?

October 27, 2010 Leave a comment

当一个数列经过一个栈的时候,经由它独特的入栈和出栈操作,这个数列会发生些什么?抛开具体的数值,对于一数列1, 2, 3, … , n, 将它以不同的方式,经过完整的入栈和出栈操作,可以得到哪些数列?

我们来考察一个较为简单的序列1, 2, 3, 4, 5

以及两个待考察的结果:

1, 2, 4, 5, 3

1, 2, 5, 3, 4

很明显,第一个序列是可得到的。我们依次将1入栈,1出栈,2入栈,2出栈, 3, 4入栈,4出栈, 5入栈, 5出栈就可得到该数列。

然而,第二个是不可能的。前两个元素都没有问题。为了第三个弹出5,我们需要先将3,4入栈,此时下一个出栈的只能是4,而该数列中却弹出了3,故不可能。

那么,一般地,如何判断一个数列是否是满足条件的呢?

可以观察到,每一个数列可以划分为若干段单调递增的子数列,比如第一个:1245|3,第二个:125|34

事实上,一个数列满足条件,当且仅当在它每两段单调递增的子数列的交界处,满足后一个数列的第一个数是之前没有出现过的数中最大的

证明也并不困难,事实上,同时在这个栈中的元素一定满足从栈底到栈顶单调递增,那么在这个交界处(也就是开始往外弹积存已久的数了)必定先弹出栈顶较大的元素;另一方面,我们也很容易根据单调递增子数列的分段方法,构造出一种具体的入栈出栈次序。

这样,我们就可以很快知道,下面几个数列都不能由1, 2, 3, …, 9经栈操作得到

1, 3, 2, 5, 4, 8, 6, 7, 9 –> 13|25|48|679

3, 2, 1, 5, 7, 4, 6, 8, 9 –> 3|2|157|4689

Categories: OI Tags: , , ,

Poj 3277

July 29, 2010 Leave a comment

一开始以为这道题不需要传递参数,后来发现我错了..比如,先插入线段12 40 11,再插入13 40 13,若不传递参数,那么12~13这一段就会被无视

范围很大,要离散化;注意结果可能超int;区间划分时要注意

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 100001 #define MAXP 200001 #define MAXT 400001 struct segment{     int x,y,h; } seg[MAXN]; struct Point{     int x,id1,id2; } point[MAXP]; int N,pnum,tot; long long area[MAXT],height[MAXT],change[MAXP]; int cmp(const void *a, const void *b){     segment *x=(segment*)a, *y=(segment*)b;     return x->h-y->h; } int cmp1(const void *a, const void *b){     Point *x=(Point*)a, *y=(Point*)b;     return x->x-y->x; } void add(int p, int l, int r, int x, int y, int h){     if(l==x&&r==y||r-l<=1){         height[p]=h;         area[p]=(change[y]-change[x])*h;         return;     }     int m=l+r>>1;     if(height[p]){         height[p*2]=height[p*2+1]=height[p];         area[p*2]=(change[m]-change[l])*height[p];         area[p*2+1]=(change[r]-change[m])*height[p];     }     height[p]=0;     if(y<=m){         add(p*2,l,m,x,y,h);     }else if(x>=m){         add(p*2+1,m,r,x,y,h);     }else{         add(p*2,l,m,x,m,h);         add(p*2+1,m,r,m,y,h);     }     area[p]=area[p*2]+area[p*2+1]; } int main(){     scanf("%d\n",&N);     for(int i=1;i<=N;++i){         scanf("%d %d %d\n",&seg[i].x,&seg[i].y,&seg[i].h);         point[++pnum].x=seg[i].x;         point[pnum].id1=i;         point[pnum].id2=1;         point[++pnum].x=seg[i].y;         point[pnum].id1=i;         point[pnum].id2=2;     }     qsort(point+1,pnum,sizeof(point[0]),cmp1);     for(int i=1;i<=pnum;++i){         if(point[i].x!=point[i-1].x){             ++tot;             change[tot]=point[i].x;         }         if(point[i].id2==1){             seg[point[i].id1].x=tot;         }else{             seg[point[i].id1].y=tot;         }     }     qsort(seg+1,N,sizeof(seg[0]),cmp);     for(int i=1;i<=N;++i){         add(1,1,tot,seg[i].x,seg[i].y,seg[i].h);     }     printf("%lld\n",area[1]);     return 0; }
Categories: OI Tags: , , , ,

NOI 2008 志愿者招募

July 28, 2010 Leave a comment

这题竟然在省赛第3天中出现,要是当时有多做点NOI原题就好了

以样例来分析,设X[i]为第i类志愿者的人数,那么可得到约束为

Day[1]=X[1]>=2

Day[2]=X[1]+X[2]>=3

Day[3]=X[2]+X[3]>=4

添加辅助变量Y,将其化为等式得

Day'[1]=X[1]-Y[1]=2

Day'[2]=X[1]+X[2]-Y[2]=3

Day'[3]=X[2]+X[3]-Y[3]=4

添加第0、第4个等式,相邻等式两两相减(下减上)得

P[1]=X[1]-Y[1]=2

P[2]=X[2]+Y[1]-Y[2]=1

P[3]=X[3]+Y[2]-X[1]-Y[3]=1

P[4]=Y[3]-X[2]-X[3]=-4

进一步转化等式得

2-X[1]+Y[1]=0

1-X[2]-Y[1]+Y[2]=0

1-X[3]-Y[2]+X[1]+Y[3]=0

-4-Y[3]+X[2]+X[3]=0

分析上面四个等式,每个X[i]、Y[i]一正一负恰出现一次,若以每个等式为网络流中的顶点,上式就是流量守恒的形式

现规定以正为入,负为出,则对于每个P[i]:

若右端常数为正,从源点向该等式连边,容量为常数值,费用为0

若右端常数为负,从该等式向汇点连边,容量为常数值绝对值,费用为0

对于每个X[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为C[i]

对于每个Y[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为0

求最小费用最大流即为答案

#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 20001 #define QMAX 20001 #define MAXE 100001 #define oo 0x77777777 struct Edge{     int v,w,p;     Edge *next,*pair; } *edge[MAXN],*fe[MAXN],mempool[MAXE]; int S,T,memnum,dis[MAXN],Que[MAXN],vis[MAXN], Closed,Open,Size,ft[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w, int p){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->p=p,x->next=edge[s],x->pair=y,edge[s]=x;     y->v=s,y->w=0,y->p=-p,y->next=edge[t],y->pair=x,edge[t]=y; } int spfa(){     memset(dis,0x77,sizeof(dis));     memset(vis,0,sizeof(vis));     memset(ft,0,sizeof(ft));     memset(fe,0,sizeof(fe));     Closed=0,Open=0,Size=1,Que[0]=S,vis[S]=1,dis[S]=0;     while(Size){         int now=Que[Closed];         vis[now]=0,--Size,Closed=(Closed+1)%QMAX;         for(Edge *tmp=edge[now];tmp;tmp=tmp->next){             if(tmp->w>0){                 if(dis[now]+tmp->p<dis[tmp->v]){                     dis[tmp->v]=dis[now]+tmp->p;                     ft[tmp->v]=now;                     fe[tmp->v]=tmp;                     if(!vis[tmp->v]){                         ++Size;                         vis[tmp->v]=1;                         if(!Size||dis[tmp->v]<dis[Que[Closed]]){                             Closed=(Closed-1+QMAX)%QMAX;                             Que[Closed]=tmp->v;                         }else{                             Open=(Open+1)%QMAX;                             Que[Open]=tmp->v;                         }                     }                 }             }         }     }     return dis[T]<oo; } void aug(){     int delta=oo;     for(int i=T;i!=S;i=ft[i]){         if(fe[i]->w<delta){             delta=fe[i]->w;         }     }     for(int i=T;i!=S;i=ft[i]){         fe[i]->w-=delta,fe[i]->pair->w+=delta,ans+=delta*fe[i]->p;     } } int main(){     int N,M,x,y=0,s,t,c;     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     scanf("%d%d",&N,&M);     S=0,T=N+2;     for(int i=1;i<=N;++i){         scanf("%d",&x);         t=x-y;         if(t>0){             add(S,i,t,0);         }else{             add(i,T,-t,0);         }         y=x;         add(i+1,i,oo,0);     }     add(N+1,T,x,0);     for(int i=1;i<=M;++i){         scanf("%d%d%d",&s,&t,&c);         add(s,min(N+1,t+1),oo,c);     }     while(spfa())         aug();     printf("%d\n",ans);     return 0; }
Categories: OI Tags: , , , ,

NOI 2006 最大获利

July 28, 2010 Leave a comment

最大权闭合图。可参考胡伯涛的论文。该题的标准解法是贪心初始流+最大流。但用SAP+GAP+当前弧优化可以秒过。

早就听说当前弧优化,但是一加到自己代码上就错。这次终于找到原因了,因为以前把更新距离标号的一部分操作挪到寻找可行弧时完成,但这样一来就会出现问题。把操作独立出来之后问题就解决了。

#include<stdio.h> #include<string.h> #define MAXN 70001 #define MAXE 400001 #define oo 0x77777777 struct Edge{     int v,w;     Edge *next,*pair; } *edge[MAXN],mempool[MAXE],*cur[MAXN]; int S,T,counter[MAXN],layer[MAXN],minf,found,ans,memnum; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->pair=y,x->next=edge[s],edge[s]=x;     y->v=s,y->w=0,y->pair=x,y->next=edge[t],edge[t]=y; } void aug(int now){     if(now==T){         found=1;         ans+=minf;         return;     }     Edge *i;     int tmp=minf;     for(i=cur[now];i;i=i->next){         if(i->w>0){             if(layer[now]==layer[i->v]+1){                 cur[now]=i;                 minf=min(minf,i->w);                 aug(i->v);                 if(layer[S]>T) return;                 if(found) break;                 minf=tmp;             }         }     }     if(!found){         int minl=T;         for(i=cur[now]=edge[now];i;i=i->next) if(i->w>0) minl=min(minl,layer[i->v]);         if(!(--counter[layer[now]])) layer[S]=T+1;         ++counter[layer[now]=minl+1];     }else{         i->w-=minf;         i->pair->w+=minf;     } } void sap(){     memset(counter,0,sizeof(counter));     memset(layer,0,sizeof(layer));     counter[0]=T+1;     memcpy(cur,edge,sizeof(edge));     while(layer[S]<=T){         found=0;         minf=oo;         aug(S);     } } int main(){     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     int sum=0,a,b,c,x,N,M;     scanf("%d %d\n",&N,&M);     S=0,T=N+M+1;     for(int i=1;i<=N;++i){         scanf("%d",&x);         add(i,T,x);     }     for(int i=1;i<=M;++i){         scanf("%d %d %d\n",&a,&b,&c);         add(i+N,a,oo);         add(i+N,b,oo);         add(S,i+N,c);         sum+=c;     }     sap();     printf("%d\n",sum-ans);     return 0; }
Categories: OI Tags: , , , ,

poj 1180

July 28, 2010 Leave a comment

可参见黑书P152
设F(i)表示前i个任务的代价以及之后任务的等待代价之和的最小值,则
F(i)=Min{F(j)+W[j+1,i]}
其中W[j+1,i]=(S+SumT(j+1,i))*SumF(j+1,n)
进一步可证明该方程满足决策单调性,因此可优化到O(nlogn)
此外本题有O(n)算法,详见黑书

#include<stdio.h> #include<string.h> #define MAXN 10001 #define oo 0x77777777 struct Stack{     int s,t,id; } stack[MAXN]; int N,S,sumt[MAXN],sumf[MAXN],f[MAXN],head,K; inline int min(int a, int b){     return a<b?a:b; } inline int getw(int i, int j){     return (S+sumt[j]-sumt[i])*(sumf[N]-sumf[i]); } inline int getf(int j, int i){     return f[j]+getw(j,i); } void update(int now){     while(head&&now<stack[head].s&&getf(now,stack[head].s)<getf(stack[head].id,stack[head].s)){         stack[head-1].t=stack[head].t;         --head;     }     int l=stack[head].s,r=stack[head].t,m;     while(l<=r){         m=l+r>>1;         if(getf(now,m)<getf(stack[head].id,m))             r=m-1;         else             l=m+1;     }     while(l<=stack[head].t&&getf(now,l)>getf(stack[head].id,l)) ++l;     stack[head].t=l-1;     if(stack[head].t<stack[head].s) --head;     if(l>N) return;     stack[++head].s=l;     stack[head].t=N;     stack[head].id=now; } int main(){     scanf("%d\n%d\n",&N,&S);     for(int i=1;i<=N;++i){         scanf("%d %d",&sumt[i],&sumf[i]);         sumt[i]+=sumt[i-1],sumf[i]+=sumf[i-1];     }     stack[head=1].s=1,stack[K=1].t=N;     for(int i=1;i<=N;++i){         if(i>stack[K].t)             ++K;         f[i]=getf(stack[K].id,i);         update(i);     }     printf("%d\n",f[N]);     return 0; }

poj 2763

July 27, 2010 Leave a comment

这题要求两个操作:求树上两个顶点的距离,以及改变某条边的权值。

通过巧妙地利用DFS序列和树状数组,我们可以在O(lg n)时间内完成每个操作。

比如对于一个有8个顶点,且边集如下的树:

1 2

1 3

1 4

2 5

2 6

4 7

7 8

它的DFS序列为 1 2 5 6 3 4 7 8

对于某条树上的边,我们将边指向的子结点的权值加上边的权值,再将这棵子树之后的第一个结点的权值减去这条边的权值,那么就可以用一个树状数组维护每个结点到根结点的距离。

比如 连接1和2的这条边权值为3,我们在2上加3,在3上减3即可。这样修改边权也非常方便。

两个结点间距离:dis(a)+dis(b)-2*dis(LCA(Tree,a,b))

拿这题来复习树状数组,RMQ,LCA…

要注意几个情况

RE一般是数组没开够 开大点..

TLE可能是算法没优化好 实在不行试试用getchar输入加速

WA原因很多,要注意结点到自身的LCA

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 222222
struct Edge{
	int v,w;
	Edge *next;
} *edge[MAXN], mempool[MAXN];
int memnum, road[MAXN][3], dep[MAXN], vis[MAXN], tapp[MAXN],
stack[MAXN], app[MAXN], snum, tnum, n, q, cur, tree[MAXN],
son[MAXN], cnum[MAXN], st[MAXN][20];
inline int rmin(int a, int b){
	return dep[a]<dep[b]?a:b;
}
void add(int u, int v, int w){
	Edge *e=&mempool[memnum++];
	e->v=v,e->w=w,e->next=edge[u],edge[u]=e;
}
int getn(){
	char ch;
	int res=0;
	for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())
		res=res*10+ch-'0';
	return res;
}
void predfs(int now, int deep){
	dep[now]=deep;
	vis[now]=1;
	stack[++snum]=now;
	tree[++tnum]=now;
	tapp[now]=tnum;
	if(!app[now]) app[now]=snum;
	for(Edge *tmp=edge[now];tmp;tmp=tmp->next){
		if(!vis[tmp->v]){
			predfs(tmp->v,deep+1);
			stack[++snum]=now;
			son[now]+=son[tmp->v]+1;
		}
	}
}
void find(int i, int k){
	if(k==0){
		st[i][k]=stack[i];
		return;
	}
	if(!st[i][k-1]) find(i,k-1);
	if(!st[i+(1<<(k-1))][k-1]) find(i+(1<<(k-1)),k-1);
	st[i][k]=rmin(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
int rmq(int l, int r){
	int k=int(log(1.0*(r-l+1))/log(2.0)),kr=r-(1<<k)+1;
	if(!st[l][k]) find(l,k);
	if(!st[kr][k]) find(kr,k);
	return rmin(st[l][k], st[kr][k]);
}
int getsum(int x){
	int res=0;
	for(;x>0;x-=x&-x)
		res+=cnum[x];
	return res;
}
void add(int x, int d){
	for(;x<=n;x+=x&-x)
		cnum[x]+=d;
}
int lca(int a, int b){
	if(a==b) return a;
	int x=app[a], y=app[b];
	if(x<y) return rmq(x,y);
	else return rmq(y,x);
}
int dist(int now){
	return getsum(tapp[now]);
}
int ask(int a, int b){
	return dist(a)+dist(b)-2*dist(lca(a,b));
}
void change(int i, int w){
	int a=road[i][0], b=road[i][1];
	if(dep[a]>dep[b]){int tmp=a;a=b;b=tmp;}
	add(tapp[b], w-road[i][2]);
	add(tapp[b]+son[b]+1, road[i][2]-w);
	road[i][2]=w;
}
int main(){
	int u,a,b,w,c;
	scanf("%d %d %d\n",&n,&q,&cur);
	for(int i=1;i<n;++i){
		a=getn(), b=getn(), w=getn();
		add(a,b,w);
		add(b,a,w);
		road[i][0]=a;
		road[i][1]=b;
		road[i][2]=w;
	}
	predfs(1,0);
	for(int i=1;i<n;++i){
		w=road[i][2];
		road[i][2]=0;
		change(i,w);
	}
	for(int i=1;i<=q;++i){
		c=getn();
		if(!c){
			u=getn();
			printf("%d\n",ask(cur,u));
			cur=u;
		}else{
			a=getn(), b=getn();
			change(a,b);
		}
	}
	return 0;
}
Categories: OI Tags: , , , , ,