1、论C+语言在信息学竞赛中的应用,浙江省余姚中学 韩文弢,关于信息学竞赛,信息学竞赛一般要求在一定的时间内，理解并分析题意，设计符合给定时间和空间复杂度要求的算法，并在计算机上使用一定的程序设计语言正确地实现算法。由于整个竞赛存在时间限制，因此所使用的程序设计语言能否正确、快速地实现算法对竞赛的成绩影响颇大。,关于信息学竞赛,所以，编程复杂度成为和算法的时间以及空间复杂度同等重要的因素。编程复杂度在很大程度上与所选用的程序设计语言有关。一般信息学竞赛中比较常用的程序设计语言有BASIC、Pascal、C+、Java等。,信息学竞赛中常用语言的特点,中学信息学竞赛的语言现状,BASIC语言正逐渐被
2、淘汰。Pascal语言使用较为广泛，基本保持稳定。C+语言凭借其本身所具有的高度的灵活性，以及它所带的库的强大功能，被越来越多的选手所使用。 ,本文的目的和结构,目的：使读者在掌握Pascal语言的前提下，能尽快地掌握C+语言，并在此基础上进一步深入C+语言的高级应用。结构：1 从Pascal到C+2 深入C+语言3 STL简介,3 STL简介,阅读本章的必要条件：了解C+面向对象程序设计的基础知识、了解一定的算法知识本章的结构：3.1 STL概述3.2 迭代器3.3 算法3.4 容器3.5 本章小结,3.1 STL概述,一般化编程,一般化编程(generic programming)的提出v
3、oidswap(int,模板函数,模板函数templatevoidswap(T,模板函数的调用,模板函数的调用隐式调用swap(x,y);显式调用swap(x,y);,模板类,模板类templatestructc_arraytypedefTvalue_type;typedefT,模板类的使用,模板类的使用c_arraya;c_arrayb;c_array,10c;,STL概述,STL就是建立在模板函数和模板类基础之上的功能强大的库模板函数可以实现一般化的常用算法（如统计、排序、查找等）模板类可以实现支持几乎所有类型的容器，用来实现常用的数据结构（如链表、栈、队列、平衡二叉树等）,STL头文件一
4、览,3.2 迭代器,迭代器的定义和种类,迭代器(iterator)实际上是一种一般化的指针类型，是对指针类型的抽象。 根据所支持操作的不同，迭代器被分为五大类：输出迭代器(input iterator)输入迭代器(output iterator)前向迭代器(forward iterator)双向迭代器(bidirectional iterator)随机迭代器(random access iterator),各种迭代器的功能,更多关于迭代器的信息,指针类型就是一种特殊的随机迭代器类型。对于一般的迭代器，这些功能都是通过操作符重载来实现的。,更多关于迭代器的信息,各种迭代器类型之间的关系：迭代器的
5、作用访问元素算法与容器之间的纽带,模板类pair,templatestructpairtypedefT1first_type;typedefT2second_type;T1first;T2second;pair():first(T1(),second(T2()pair(constT1,模板类pair,templatepairmake_pair(constT1作用储存一对密切相关的值使用在当算法需要返回两个值时作为映射的元素类型（关键字和被映射的值）,3.3 算法,与算法有关的知识,算法(algorithm)每个算法都是一个或者一组模板函数，用来完成一项特定的操作。序列(sequence)序列用
6、两个迭代器来描述，表示一组连续的元素；其中，第一个迭代器指向序列中的第一个元素，第二个迭代器指向序列最后一个元素的后一个位置。,与算法有关的知识,函数对象(function object)函数对象重载了函数调用操作符(operator ()，可以像普通函数一样被使用。谓词(predicate)返回值类型为bool的函数对象,函数对象举例,templateclassSumTres;public:Sum(Ti=T():res(i)voidoperator()(constT,常用函数对象,STL在头文件中提供了一些常用运算的函数对象。,STL算法一览,访问元素类for_each(), transfo
7、rm()顺序查找类find(), find_if(), find_first_of(), adjacent_find(), search(), find_end(), search_n()统计类count(), count_if(),STL算法一览,比较类mismatch(), equal(), lexicographical_compare()复制类copy(), copy_backward()交换类swap(), iter_swap(), swap_ranges(),STL算法一览,替换类replace(), replace_if(), replace_copy(), replace_co
8、py_if()填充发生类fill(), fill_n(), generate(), generate_n()删除类remove(), remove_if(), remove_copy(), remove_copy_if,STL算法一览,去重类unique(), unique_copy()反转类reverse(), reverse_copy()旋转类rotate(), rotate_copy()随机打乱类random_shuffle(),STL算法一览,排序类sort(), stable_sort(), partial_sort(), partial_sort_copy(), nth_eleme
9、nt()二分查找类lower_bound(), upper_bound(), equal_range(), binary_search()合并类merge(), inplace_merge(),STL算法一览,分区类partition(), stable_partition()集合运算类includes(), set_union(), set_intersection(), set_difference(), set_symmetric_difference()堆操作类make_heap(), push_heap(), pop_heap(), sort_heap(),STL算法一览,最大最小类
10、min(), max(), min_element(), max_element()排列类next_permutation(), prev_permutation()数值运算类accumulate(), inner_product(), partial_sum(), adjacent_difference(),常用算法介绍（排序）,排序算法原型templatevoidsort(Ranfirst,Ranlast);templatevoidsort(Ranfirst,Ranlast,Cmpcmp);时间复杂度：平均O(n log n)，最坏O(n2)使用举例sort(a,a+n);sort(b,b
11、+m,greater();,常用算法介绍（二分查找）,二分查找算法原型：templateboolbinary_search(Forfirst,Forlast,constT时间复杂度：随机迭代器O(log n)，其他O(n),常用算法介绍（二分查找）,算法的要求序列有序查找的谓词与排序的谓词相同算法的作用binary_search()返回val是否在序列中。lower_bound()返回指向序列中第一个大于或等于val的元素的迭代器。upper_bound()返回指向序列中第一个大于val的元素的迭代器。equal_range()返回一个pair，表示序列中与val相等的元素所构成的子序列。,算
12、法的组合使用,例如，要对一组范围较大的整数进行离散化，步骤如下：用sort()排序；用unique()去掉重复的元素；对于每个整数，用lower_bound()查找在序列中的位置 。,例题：最长单调递增子序列,题目描述给定一个长度为n的整数序列A = a1, a2, ., an，求一个最大的整数m，使得存在另一个序列P = p1, p2, ., pm，满足 ，且 。约束条件n不超过30,000ai在0, 1,000,000,00)的区间内,思路分析,原算法设fi表示结尾元素为原序列中第i个元素的最长单调递增序列的长度（为了简便，设a0=-，f0=0），状态转移方程如下：时间复杂度O(n2)，不
13、符合要求。,思路分析,改进后的算法设gi表示到目前为止，所有长度为i的单调递增子序列中最后一个元素的最小值。易知，gi-1gi。当到第i-1个字符为止的gi已知时，fi就等于在gi中第一个大于或等于ai的元素的位置j。此时，令gj=ai，更新gi。一开始，gi=。时间复杂度O(n log n)，符合要求。,改进算法运行实例,n=10,1,1,1,2,2,3,3,3,4,4,3,1,4,2,5,3,9,6,核心代码,原算法(O(n2)：for(inti=0;in;i+)fi=1;for(intj=0;ji;j+)if(ajai)fi=max(fi,fj+1);改进后的算法(O(n log n)：
14、fill(g,g+n,infinity);for(inti=0;im;for(intj=0;ja;bills.insert(a);cout*bills.begin()*-bills.end()endl;bills.erase(bills.begin();bills.erase(-bills.end();,3.5 本章小结,STL的利弊,优点：降低编程复杂度提高代码的正确率缺点：编译时会出各种错误给动态调试增加难度,几点建议,多用STL的算法优先使用内置数组多用静态查错动态查错时向屏幕输出,总结,STL以面向对象的程序设计和一般化编程为基础，提供了功能强大的算法和容器，并通过迭代器把这两部分有机地结合起来。在信息学竞赛中正确、恰当地使用STL可以大大降低编程复杂度，提高代码的正确率，节约宝贵的竞赛时间。但是，STL只是一种工具，在竞赛中只能起到辅助的作用。丰富的算法知识、健康的身体素质和良好的心理素质才是竞赛中起决定作用的因素。,谢谢大家！,欢迎提问！,
