NOIP復(fù)賽復(fù)習(xí)12STL算法與樹結(jié)構(gòu)模板

NOIP復(fù)賽復(fù)習(xí)12STL算法與樹結(jié)構(gòu)模板STL算法STL算法是一些模板函數(shù)，提供了相當多的有用算法和操作，從簡單如for_each(遍歷)到復(fù)雜如stable_sort(穩(wěn)定排序)，頭文件是：#include<algorithm>。常用STL算法庫包括：sort快速排序算法、二分查找算法、枚舉排列算法等。1、 sort排序系列sort：對給定區(qū)間所有元素進行排序(全排)stable_sort：對給定區(qū)間所有元素進行穩(wěn)定排序，就是相等的元素位置不變，原來在前面的還在前面。partial_sort：對給定區(qū)間所有元素部分排序，就是找出你指定的數(shù)目最小或最大的值放在最前面或最后面，比如說我只要找到1000000個數(shù)中最大的五個數(shù)，那你用這個函數(shù)是最好的，排序后最大的五個數(shù)就在最前面的五個位置，其他的元素位置分布不確定。partial_sort_copy：對給定區(qū)間復(fù)制并排序，和上面的一樣，只是這是指定區(qū)間進行復(fù)制然后排序的。nth_element：找出給定區(qū)間的某個位置對應(yīng)的元素，根據(jù)比較函數(shù)找到第n個最大(小)元素，適用于尋找“第n個元素”。is_sorted：判斷一個區(qū)間是否已經(jīng)排好序(返回bool值判斷是否已排序)partition:使得符合某個條件的元素放在前面，劃分區(qū)間函數(shù)，將［first,last］中所有滿足的元素置于不滿足的元素前面，這個函數(shù)會返回迭代器，設(shè)返回的迭代器為i，則對［first,i］中的任意迭代器j，*j滿足給定的判斷，對［i,last］中的任意迭代器k，*k不滿足。stable_partition：相對穩(wěn)定的使得符合某個條件的元素放在前面(和上面的一樣，只是位置不變)使用時根據(jù)需要選擇合理的排序函數(shù)即可，所有的排序函數(shù)默認從小到大排序，可以定義自己的比較方式。2、 二分系列二分檢索，復(fù)雜度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。二分經(jīng)常會與其他算法結(jié)合。例：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是一個求一個排序的下一個排列的函數(shù)，可以遍歷全排列，要包含頭文件<algorithm>，與之完全相反的函數(shù)還有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、常用函數(shù)copy、copy_if：copy直接拷貝，比for循環(huán)高效，最壞為線性復(fù)雜度，而且這個可以說是一個copy族函數(shù)，還有類似的滿足一定條件的copy_if等。find、find_i：查找第一個匹配的值或第一個滿足函數(shù)使其為true的值位置，沒有返回指定區(qū)間的末尾，線性復(fù)雜度，還有一些不怎么常用的find族函數(shù)就不多介紹了。count、count_if：返回匹配或使函數(shù)為true的值的個數(shù)，線性復(fù)雜度。search：這是尋找序列是否存在于另一個序列中的函數(shù)，挺好用的，某些簡單的尋找公共子串的題就可以這樣寫，時間復(fù)雜度二次。reverse：翻轉(zhuǎn)一個區(qū)間的值，我經(jīng)常遇到需要這種題，直接reverse了，不需要for循環(huán)了，主要是方便。for_each：直接對一個區(qū)間內(nèi)的每個元素執(zhí)行后面的函數(shù)操作，寫起來簡單。max、min、max_element、min_element：尋找兩個數(shù)或者一個區(qū)間的最大最小值，都可以添加比較函數(shù)參數(shù)。集合操作函數(shù)：includes>set_union、set_difference、set_intersection、set_symmetric_difference、前面這些函數(shù)的最差復(fù)雜度為線性，另外附加一個序列的操作函數(shù)merge,相當于歸并排序中的合并函數(shù)，時間復(fù)雜度為線性，注意這些函數(shù)的操作對象都必須是升序的。例：#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;}樹結(jié)構(gòu)模板1、樹狀數(shù)組例：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,-