ACM简单题秒杀和C++STL.ppt

PartIACM竞赛简单题秒杀攻略,简单题,简单题的特点：没有算法或者只有基本的算法编程复杂度不高分辨简单题：简单题一般题目较短校赛的第一题往往是简单题观察ranklist和场上气球情况,简单题是校赛决胜的关键,如何秒杀简单题,提高代码正确率提高写代码的速度熟练掌握各种基本算法,Step1:解析题目,背景介绍、问题提出输入输出要求输入输出样例时间、空间限制以及其他信息,Step2:了解输入输出,输入输出是分离的输出文件输入，以EOF结束（例题：ZOJ1001）while(scanf(“%d”,if(nCases+)printf(“n”);输出，每个case之后输出空行（例题：ZOJ1457）printf(“%dnn”,ans);,Step3:了解常见错误类型,CompilationError编译错误SegmentationFault数组越界、堆栈溢出等TimeLimitError运行时间超限MemoryLimitError内存超限WrongAnswer答案错误PresentationError格式错误OutputLimitError输出超限RestrictedFunction非法函数,Step4:程序调试,重新读题、检查代码数组是否开的够大（大数组开到全局，避免堆栈溢出）int-2312311longlonglargenumber;/-263263-1printf(“%lldn”,largenumber);构造测试数据题目提供的测试数据一般较弱边界数据、特殊数据,Step5:复杂度估计,估计程序空间复杂度默认空间限制：32Mcharc1000000;/1Minta10001000;/4M估计程序时间复杂度一般ZOJ可以接受的时间复杂度为106107,Step5:复杂度估计,数据范围允许的时间复杂度1020O(logN)109O(logN)O(sqrt(N)106O(N)105O(NlogN)104O(NlogN)O(Nsqrt(N)103O(N2)102O(N3)20O(2N),如何秒杀简单题,提高代码正确率提高写代码的速度熟练掌握各种基本算法,Step1:熟悉编程环境,VC6.0、Dev-C+等与ZOJ编译器的区别for(inti=0;inm;coutcout.setf()cout.unsetf()cout.precision(),输入输出流,使用方法示例doublea=1234;cout.setf(ios:fixed);cout.precision(3);coutat)couttendl;输出abc,stringstream类,ostringstream使用示例ostringstreamos;os3“solutions”;coutos.str()操作可以使用Iterator的+运算符来遍历容器一般的容器都提供了begin()和end()两个函数来得到指向容器头、尾的两个Iterator。其中begin指向头元素，end指向最后一个元素的后一个位置。,Iterator的分类,InputIteratorOutputIteratorForwardIteratorBidirectionalIterator双向移动，只支持+和-操作list/map/setRandomAccessIterator支持所有的指针操作vector,vector,#include动态数组vectorarr;arr=vector(10);arr.push_back(3);coutarr2endl;arr=arr2;if(arrarr2),vector,常用的操作arr.clear();arr.push_back(5);arr.pop_back();arr.front();arr.back();arr.erase(arr.begin()+5);arr.erase(arr.begin(),arr.end();arr.insert(arr.begin()+5,4);,vector,vector的初始化vectorarr(100,0);或者arr=vector(100,0);vectorVS数组vector的灵活性比较好，不需要考虑长度问题，可以减少编程复杂度，使用起来和数组一样方便。但是vector的效率远低于数组，在效率要求较高时慎用。,vector,vector的遍历for(vector:iteratorvi=arr.begin();vi!=arr.end();+vi)cout*viendl;或者for(inti=0;iv.size();+i)coutviendl;,list,#include双向链表push_back,pop_back,push_front,pop_front由链表的特性可知，list的迭代器不支持算数运算。例如l.begin()+5是非法的，而list也不支持运算符，因此遍历list只能使用Iterator方式。,deque,#include双向队列deque是vector和list的中间产物，其内部结构是若干小段被连接起来的连续空间。deque支持push_front和pop_frontdeque和vector一样支持下标访问deque的实现比vector和list都要复杂，因此直接影响了它的效率。,priority_queue,#include用最大堆实现的优先队列priority_queue中的元素需要支持操作符。priority_queue不支持clear操作。常用操作pq.top();pq.push(5);pq.pop();,priority_queue,相关题目ZOJ2724，2006年校赛预赛题模拟windows消息队列机制，随着时间不断有新的消息加入到队列，不同的消息有不同的权重，权重高的要先处理。,set,#include有序的元素集合，set中的元素也要支持s;s.insert(3);s.erase(5);if(s.find(5)=s.end()/5不在集合中,set,set的遍历for(set:iteratorsi=s.begin();si!=s.end();+si)cout*si类似常用操作mapm;m“haha”=5;if(m.find(“hoho”)!=m.end()m.erase(m.find(“heihei”);,map,map的遍历for(map:iteratormi=m.begin();mi!=m.end();+mi)coutfirstsecondm;,map和set,map和set的实现map和set使用红黑树的实现，红黑树是一种平衡二叉搜索树，因此插入、查找和删除的操作都是O(logN)的复杂度。但是由于复杂的算法实现，效率并不是很高。,算法,#includesort(arr.begin(),arr.end();stable_sort(arr.begin(),arr.end();reverse(arr.begin(),arr.end();next_permutation(arr.begin(),arr.end();unique(arr.begin(),arr.end();,仿函数,#includesort默认从小到大排序，如果我们要以从大到小的顺序排序，可以给sort函数加上第三个参数sort(arr.begin(),arr.end(),greater();其中greater()就是仿函数，实现了()运算符，可以对两个元素进行大小的比较,自定义仿函数,实现自定义排序事实上，只要支持()运算符的就可以是仿函数，因此普通的函数就是仿函数，可以以此来构造复杂的排序顺序boolcomp(constint相同元素的比较一定要返回false(0),自定义仿函数,相关题目ZOJ2727，2006年校