NOIP复赛复习7STL算法与树结构模板.pdf

《NOIP复赛复习7STL算法与树结构模板.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP复赛复习7STL算法与树结构模板STL算法STL算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each（遍历）到复杂如stable_sort（稳定排序），头文件是：#include。常用STL算法库包括：sort快速排序算法、二分查找算法、枚举排列算法等。1、sort排序系列sort：对给定区间所有元素进行排序（全排）stable_sort：对给定区间所有元素进行稳定排序，就是相等的元素位置不变，原来在前面的还在前面。partial_sort：对给定区间所有元素部分排序，就是找

2、出你指定的数目最小或最大的值放在最前面或最后面，比如说我只要找到1000000个数中最大的五个数，那你用这个函数是最好的，排序后最大的五个数就在最前面的五个位置，其他的元素位置分布不确定。partial_sort_copy：对给定区间复制并排序，和上面的一样，只是这是指定区间进行复制然后排序的。nth_element：找出给定区间的某个位置对应的元素，根据比较函数找到第n个最大（小）元素，适用于寻找“第n个元素”。is_sorted：判断一个区间是否已经排好序（返回bool值判断是否已排序）partition：使得符合某个条件

3、的元素放在前面，划分区间函数，将[first,last]中所有满足的元素置于不满足的元素前面，这个函数会返回迭代器，设返回的迭代器为i，则对[first,i]中的任意迭代器j，*j满足给定的判断，对[i,last]中的任意迭代器k，*k不满足。stable_partition：相对稳定的使得符合某个条件的元素放在前面（和上面的一样，只是位置不变）使用时根据需要选择合理的排序函数即可，所有的排序函数默认从小到大排序，可以定义自己的比较方式。2、二分系列二分检索，复杂度O(log(last-first))itr=upper_bou

4、nd(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。二分经常会与其他算法结合。例：HDU14

5、96#include#include#includeusingnamespacestd;intval[40010];intmain(){pairp;inta,b,c,d;while(cin>>a>>b>>c>>d){if((a>0&&b>0&&c>0&&d>0)

6、

7、(a<0&&b<0&&c<0&&d<0)){cout<<0<

8、;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.sec

9、ond-p.first;}}cout<，与之完全相反的函数还有prev_permutation。int类型的next_permutationintmain(){inta[3];a[0]=1;a[1]=2;a[2]=3;do{cout<

10、;}输出：123132213231312321char类型的next_permutationintmain(){charch[205];cin>>ch;sort(ch,ch+strlen(ch));char*first=ch;char*last=ch+strlen(ch);d