Archive

Archive for the ‘OI’ Category

栈都做了些什么?

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

Advertisements
Categories: OI Tags: , , ,

NOIP2010提高组初赛问题求解第三题推广

October 27, 2010 Leave a comment

我们很自然地想求解下面的问题:

题目:记T为一队列,初始时为空,现有k个总和不超过n的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为m,那么k的最小值是___________。

显然当m<=0或n<=0或n<m时此题无解,否则:

类似地我们构建下面的图:

0—m—2m—…—m*[n/m]
1—m+1—2m+1—..—m*[n/m]+1
……
n%m—m+n%m—…—n

n%m+1—n%m+1+m—…—n-m+1

m-1—2m-1—…—n-n%m+1
第0行至第n%m行最多总共选([[n/m]/2]+1)(n%m+1)个
第n%m+1行至第m-1行最多总共选[([n/m]+1)/2](m-1-n%m)个
所以总共最多选([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)个
注意到,我们计算的时候包含了S0,所以k的最小值就是([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)

以原题n=32, m=9代入,得

k=([32/9]/2+1)*(32%9+1)+[(32/9]+1)/2]*(9-1-32%9)=2*6+2*3=18

Categories: OI Tags: , , , , ,

NOIP2010提高组初赛问题求解第三题解答

October 26, 2010 2 comments

题目:记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________。

答案:18

证明:设这些数依次为a1, a2, a3, …, an,且记Si为前i项和,规定S0=0。很明显Si单调递增,且对任意i有0<=Si<=32。

我们可以以Si为顶点构造一张图,两点Si,Sj间连边当且仅当|Si-Sj|=9(图中数字为Si的编号,即i):

0–9–18–27
1–10–19–28
2–11–20–29
3–12–21–30
4–13–22–31
5–14–23–32
6–15–24
7–16–25
8–17–26

我们从这个图中选择一些顶点,将它们的编号排序作为一个可能的序列,比如选择0, 1, 10, 2, 13, 16,

排序后得0, 1, 2, 10, 13, 16,作差得ai依次为

1,1,8,3,3

显然有a2+a3=9 即满足条件

可以发现,若我们选择了图中的两个顶点,且它们之间连边,那么就存在一个和为9的子序列

那么,倘若对于某个n,我们能从图中选择n个顶点,使得任意两点间没有边,那么这个n就是不满足条件的

事实上,我们最多可以选择18个顶点,使得它们之间没有边相连:

第0行~第5行每行可以选第一、三个顶点或第二、四个顶点 最多共选10个

第6行~第8行每行可以选第一、三个顶点 最多选8个

注意到S0=0是必须选的,那么也就是说不满足条件的n的最大值是17

由鸽巢原理,若我们选择18个顶点,必有2个顶点之间有边连接,即必存在一个子序列的和为9

所以答案就是18。

Categories: OI Tags: , , ,

2010年深圳市NOIP提高组复赛名单

October 25, 2010 Leave a comment

姓名 就读学校(学校全称) 年级 参赛语种 初赛成绩
李占嵩 深圳外国语学校 高三 C++ 86
谭舒豪 深圳外国语学校 高二 C 81
段岩 深圳中学 高三 C++ 81
王翔 深圳中学 高一 PASCAL 79.5
谢熠 深圳中学 高二 PASCAL 77.5
彭效为 深圳外国语学校 高三 PASCAL 74.5
彭仰才 深圳市耀华实验学校 高三 PASCAL 71
彭旭晖 深圳市耀华实验学校 高三 PASCAL 68
李柏辰 深圳市第二实验学校 高三 PASCAL 68
郑景旭 深圳外国语学校 高一 C 68
夏侯佐瀚 深圳中学 初三 C++ 65.5
杨宗衡 深圳中学 高二 C++ 65.5
宋泰来 深圳外国语学校 高三 PASCAL 65
刘文蔚 深圳中学 高二 C++ 65
李紫豪 深圳市耀华实验学校 高三 PASCAL 64
巢鹏宁 深圳中学 高一 PASCAL 63.5
田兆琨 深大附中 高一 PASCAL 63.5
尹然 深圳外国语学校 高二 C 63.5
杨洋 深圳外国语学校 高一 C 62.5
王圣雨 深圳外国语学校 高一 C 61
刘亭君 深圳外国语学校 高一 C 60.5
姜昊茗 深圳中学 初三 C++ 60.5
黎子熙 深圳市宝安中学 高三 PASCAL 60
叶瀚文 龙城高级中学 高二 PASCAL 60
乔钰凯 深圳市耀华实验学校 高一 PASCAL 59.5
余铠 深圳中学 高二 C++ 59.5
庄锦坤 龙城高级中学 高二 PASCAL 59
郭志斌 深圳市宝安中学 高三 PASCAL 58.5
卢韵菁 深圳外国语学校 高一 C 58
李鸿宇 深圳外国语学校 高二 PASCAL 57
禹闵淇 深圳市耀华实验学校 高二 PASCAL 56
康明宇 深圳外国语学校 高一 C 54
李东繁 深圳中学 初三 C++ 54
徐峰灏 深圳中学 初三 C++ 53.5
张正浩 深圳中学 初三 C++ 53.5
何宇耕 深圳市耀华实验学校 高二 PASCAL 52.5
刘春凯 深圳实验学校高中部 高三 C 52
吴转豪 深圳中学 高一 C++ 50.5
肖锡晨 深圳市宝安中学 高二 C++ 50.5
谢慧娴 深圳外国语学校 高三 PASCAL 50
姜矜芊 深圳外国语学校 高一 C 50
刘凯 龙城高级中学 高二 PASCAL 48.5
刘宇攀 深圳市高级中学 高一 C++ 48
刘思弘 深圳实验学校高中部 高一 PASCAL 45.5
王胡杰 深大附中 高一 PASCAL 45
肖培浩 布吉高级中学 高三 C 42
区宇祺 深大附中 高一 C++ 42
Categories: OI

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: , , , ,