NOIP复赛复习12STL算法与树结构模板

NOIP复赛复习12STL算法与树结构模板STL算法STL算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each(遍历)到复杂如stable_sort(稳定排序)，头文件是：#include<algorithm>。常用STL算法库包括：sort快速排序算法、二分查找算法、枚举排列算法等。1、 sort排序系列sort：对给定区间所有元素进行排序(全排)stable_sort：对给定区间所有元素进行稳定排序，就是相等的元素位置不变，原来在前面的还在前面。partial_sort：对给定区间所有元素部分排序，就是找出你指定的数目最小或最大的值放在最前面或最后面，比如说我只要找到1000000个数中最大的五个数，那你用这个函数是最好的，排序后最大的五个数就在最前面的五个位置，其他的元素位置分布不确定。partial_sort_copy：对给定区间复制并排序，和上面的一样，只是这是指定区间进行复制然后排序的。nth_element：找出给定区间的某个位置对应的元素，根据比较函数找到第n个最大(小)元素，适用于寻找“第n个元素”。is_sorted：判断一个区间是否已经排好序(返回bool值判断是否已排序)partition:使得符合某个条件的元素放在前面，划分区间函数，将［first,last］中所有满足的元素置于不满足的元素前面，这个函数会返回迭代器，设返回的迭代器为i，则对［first,i］中的任意迭代器j，*j满足给定的判断，对［i,last］中的任意迭代器k，*k不满足。stable_partition：相对稳定的使得符合某个条件的元素放在前面(和上面的一样，只是位置不变)使用时根据需要选择合理的排序函数即可，所有的排序函数默认从小到大排序，可以定义自己的比较方式。2、 二分系列二分检索，复杂度O(log(last-first))itr=upper_bound(first,last,value,cmp);//itr指向大于value的第一个值(或容器末尾)itr=lower_bound(first,last,value,cmp);//itr指向不小于valude的第一个值(或容器末尾)pairequal_range(first,last,value,cmp);//找出等于value的值的范围O(2*log(last-first))Binary_search(first,last,value)返回bool值，找到则true，否则false。二分经常会与其他算法结合。例：HDU1496#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;intval[40010];intmain()(pair<int*,int*>p;inta,b,c,d;while(cin>>a>>b>>c>>d)(if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0))(cout<<0<<endl;continue;}memset(val,0,sizeof(val));intk=0;for(inti=-100;i<=100;i++)(if(i==0)continue;for(intj=-100;j<=100;j++)(if(j==0)continue;val[k++]=a*i*i+b*j*j;}}sort(val,val+k);intcnt=0;for(intj=-100;j<=100;j++)(if(j==0)continue;for(inti=-100;i<=100;i++)(if(i==0)continue;intsum=c*j*j+d*i*i;p=equal_range(val,val+k,-sum);cnt+=p.second-p.first;}}cout<<cnt<<endl;return0;}3、排列系列next_permutation是一个求一个排序的下一个排列的函数，可以遍历全排列，要包含头文件<algorithm>，与之完全相反的函数还有prev_permutation。int类型的next_permutationintmain()(inta[3];a[0]=1;a[1]=2;a[2]=3;do(cout<<a[0]<<""<<a[1]<<""<<a[2]<<endl;}while(next_permutation(a,a+3));}输出：23TOC\o"1-5"\h\z3213311221char类型的next_permutationintmain()(charch[205];cin>>ch;sort(ch,ch+strlen(ch));char*first=ch;char*last=ch+strlen(ch);do(cout<<ch<<endl;)while(next_permutation(first,last));return0;string类型的next_permutationintmain()(stringline;while(cin>>line&&line!="#")(if(next_permutation(line.begin(),line.end()))cout<<line<<endl;elsecout<<"Nosuccesor\n";}}intmain()(stringline;while(cin>>line&&line!="#")(sort(line.begin(),line.end());cout<<line<<endl;while(next_permutation(line.begin(),line.end()))cout<<line<<endl;}}4、常用函数copy、copy_if：copy直接拷贝，比for循环高效，最坏为线性复杂度，而且这个可以说是一个copy族函数，还有类似的满足一定条件的copy_if等。find、find_i：查找第一个匹配的值或第一个满足函数使其为true的值位置，没有返回指定区间的末尾，线性复杂度，还有一些不怎么常用的find族函数就不多介绍了。count、count_if：返回匹配或使函数为true的值的个数，线性复杂度。search：这是寻找序列是否存在于另一个序列中的函数，挺好用的，某些简单的寻找公共子串的题就可以这样写，时间复杂度二次。reverse：翻转一个区间的值，我经常遇到需要这种题，直接reverse了，不需要for循环了，主要是方便。for_each：直接对一个区间内的每个元素执行后面的函数操作，写起来简单。max、min、max_element、min_element：寻找两个数或者一个区间的最大最小值，都可以添加比较函数参数。集合操作函数：includes>set_union、set_difference、set_intersection、set_symmetric_difference、前面这些函数的最差复杂度为线性，另外附加一个序列的操作函数merge,相当于归并排序中的合并函数，时间复杂度为线性，注意这些函数的操作对象都必须是升序的。例：#include<cstdio>#include<algorithm>usingnamespacestd;voidout(inta)(if(a!=-1)printf("%d",a);}intmain()(inta[5]=(1,8,10,52,100};intb[5]=(6,8,9,10,1000};intc[20];printf("a集合为：");for_each(a,a+5,out);puts("");printf("b集合为：");for_each(b,b+5,out);puts("");//判断b是否是a的子集。if(includes(a,a+5,b,b+5))printf("bisasubsetofa\n");//合并两个有序序列，必须为合并后的序列分配空间，否则程序会崩溃。printf("两个集合的合并序列为：");merge(a,a+5,b,b+5,c);for_each(c,c+10,out);puts("");//求两个集合的并集。fill(c,c+20,-1);set_union(a,a+5,b,b+5,c);printf("两个集合的并集为：");for_each(c,c+10,out);puts("");//求两个集合的交集。fill(c,c+20,-1);set_intersection(a,a+5,b,b+5,c);printf("两个集合的交集为：");for_each(c,c+10,out);puts("");//求两个集合的差集，这里为a-b。fill(c,c+20,-1);set_difference(a,a+5,b,b+5,c);printf("a-b的差集为：");for_each(c,c+10,out);puts("");//求两个集合的差集，这里为b-a。fill(c,c+20,-1);set_difference(b,b+5,a,a+5,c);printf("b-a的差集为：");fOr_each(c,c+10,out);puts("");//求两个集合的对称差set_symmetric_difference(a,a+5,b,b+5,c);printf("两个集合的对称差为：");fOr_each(c,c+10,out);puts("");return0;}树结构模板1、树状数组例：HDU1166#include<stdio.h>#include<math.h>constintMAX=50010*4;intsegment[MAX];voidpushUp(introot)(segment[root]=segment[root*2]+segment[root*2+1];}voidbuildTree(introot,intleft,intright)(scanf("%d",&segment[root]);return;}intmid=(left+right)/2;buildTree(root*2,left,mid);buildTree(root*2+1,mid+1,right);pushUp(root);}voidupdate(introot,intpos,intadd_num,intleft,intright)(if(left==right)(segment[root]+=add_num;return;}intmid=(left+right)/2;if(pos<=mid)update(root*2,pos,add_num,left,mid);elseupdate(root*2+1,pos,add_num,mid+1,right);pushUp(root);}intgetSum(introot,intleft,intright,intL,intR)(if(left==L&&right==R)(returnsegment[root];}intmid=(L+R)/2;intres=0;if(left>mid)(res+=getSum(root*2+1,left,right,mid+1,R);5…L86^00(*'S'L，mid)；else*W,岫L,mid);广—+顷™+您;returnres;EintT;scanf("%d”,&T);f0r(intkase=1;kase<=T;kase++)intn;scanf("%d",&n);buildTree(1,1,n);charop[10];intt1,t2;printf("Case%d:\n",kase);while(scanf("%s",op))if(op[0]=='E')break;scanf("%d%d”,&t1,&t2);if(op[0]=='A')sumelseif(op[0]=='S')update(1,t1,-t2,1,n);}else(printf("%d\n",getSum(1,t1,t2,1,n));}}}return0;}2、后缀树例：CodeForces128B#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>#include<iostream>#include<stdlib.h>#include<set>#include<map>#include<queue>#include<vector>#include<bitset>#pragmacomment(linker,"/STACK:1024000000,1024000000")template<classT>boolscanff(T&ret)(//FasterInputcharc;intsgn;Tbit=0.1;if(c=getchar(),c==EOF)return0;while(c!='-'&&c!='.'&&(c<'0'||c>'9'))c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');if(c==''||c=='\n')(ret*=sgn;return1;}while(c=getchar(),c>='0'&&c<='9')ret+=(c-'0')*bit,bit/=10;ret*=sgn;return1;}#defineinf1073741823#definellinf4611686018427387903LL#definePIacos(-1.0)#definelth(th<<1)#definerth(th<<1|1)#definerep(i,a,b)fOr(inti=int(a);i<=int(b);i++)#definedrep(i,a,b)fOr(inti=int(a);i>=int(b);i--)#definegson(i,root)fOr(inti=ptx[root];~i;i=ed[i].next)#definetdatainttestnum;scanff(testnum);for(intcas=1;cas<=testnum;cas++)#definemem(x,val)memset(x,val,sizeof(x))#definemkp(a,b)make_pair(a,b)#definefindx(x)lower_bound(b+1,b+1+bn,x)-b#definepb(x)push_back(x)usingnamespacestd;typedeflonglongll;typedefpair<int,int>pii;#defineSIZE27structsuffixtree(structnode(intl,r,point,a[SIZE];voidinit()(mem(a,0);point=l=0;r=-1;})T[400011];chars[400011];intactnode,actride,actline;intrest,total,temp,linker,len;voidbuiltleaf(introot,intline)(total++;T[total].init();T[total].l=len;T[total].r=100000001;T[root].a[line]=total;rest--;}boolpd_ride(intnext)(temp=T[next].r-T[next].l+1;if(actride>=temp)(actride-=temp;actnode=next;actline+=temp;returntrue;}returnfalse;}voidlink(intx)(if(linker>0)T[linker].point=x;linker=x;}voidinsert(intwait)(s[++len]=wait;rest++;linker=0;while(rest>0)(if(actride==0)actline=len;if(T[actnode].a[s[actline]]==0){builtleaf(actnode,s[actline]);link(actnode);}else{intnext=T[actnode].a[s[actline]];if(pd_ride(next))continue;if(s[T[next].l+actride]==wait){actride++;link(actnode);break;}total++;T[total].init();T[actnode].a[s[actline]]=total;T[total].l=T[next].l;T[total].r=T[next].l+actride-1;T[next].l+=actride;T[total].a[s[T[next].l]]=next;link(total);builtleaf(total,wait);}if(actnode==0&&actride>0)(actride--;actline=len-rest+1;}elseactnode=T[actnode].point;}}voidclear()(total=0;len=0;T[0].init();actnode=actride=actline=0;}voiddebug()(rep(i,0,total)(printf("T[%d](%d%d)\n",i,T[i].l,T[i].r);}}}st;#defineNN400400chars[NN];llcot[NN];llsum;llk;intlen;llgetcot(intx)(lltemp=0;llbj=1;rep(i,0,26)(if(st.T[x].a[i])(bj=0；}——returncot[x];5;intalen=0;charans[NN];voiddfs(intx)(sum+=(ll)(min(st.T[x].r,len)-st.T[x].l+1)*cot[x];if(sum>=k)(edx=x;edr=min(ll(st.T[x].r),ll(len));while(sum-cot[x]>=k)(sum-=cot[x];edr--;//printf("%lld%lld\n",edx,edr);rep(i,0,26)(if(st.T[x].a[i]&&sum<k){dfs(st.T[x].a[i]);if(sum>=k){drep(i,min(edr,ll(st.T[x].r)),st.T[x].l){st.clear();scanf("%s",s+1);len=strlen(s+1);rep(i,1,len)st.insert(s[i]-'a');st.insert(26);scanf("%lld”,&k);if(ll(len)*ll(len+1)/2LL<k){printf("Nosuchline.\n");return0;}getcot(0);dfs(0);ans[alen]=0;reverse(ans,ans+alen);printf("%s\n",ans);}3、线段树例：HDU1542#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>usingnamespacestd;constintSIZE=505;intadd[SIZE<<2];doublex[SIZE<<2],sum[SIZE<<2];structnode{intss;doublel,r,h;node(){)node(doublea,doubleb,doublec,intd):l(a),r(b),h(c),ss(d){}friendbooloperator<(nodep,nodeq){returnp.h<q.h;)s[SIZE];voidpushup(intrt,intl,intr)(if(add[rt])sum[rt]=x[r+1]-x[l];elseif(l==r)sum[rt]=0;elsesum[rt]=sum[rt<<1]+sum[rt<<1|1];}voidupdate(intL,intR,intc,intl,intr,intrt)(intm;if(L<=l&&r<=R)(add[rt]+=c;pushup(rt,l,r);return;}m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,rt<<1|1);pushup(rt,l,r);}intmain()(intn,i,k,l,m,r,cas;doublea,b,c,d,ans;cas=1;while(scanf("%d",&n)!=EOF&&n){k=1,ans=m=0;for(i=0;i<n;i++){scanf("%lf%lf%lf%lF,&a,&b,&c,&d);x[m]=a;s[m++]=node(a,c,b,1);x[m]=c;s[m++]=node(a,c,d,-