网上找的一些综合材料小册子

1、Pa r tI如何秒杀 ACM 竞赛中的简单题秒杀第一招：提高代码的正确率ZOJ 的判题方式gcc/g+编译 输出文件输出文件与标准输出文件字符比较简单题是校赛决胜的关键* Spel Judge1.输入输出格式默认格式：每行末尾一般没有空格每行中间一般是一个空格Ref:88CS 版 3446 贴88CS 版guanyao(跑腿gogogo):ZOJ 做题指南 for复试2.输入格式：a)输入一开始就会说有 N 个Input Block,下面接着是N 个Input Block。如 1526: 赛题秒杀攻略 速成 赛题秒杀攻略 速成 - 1 - - 2 -秒杀简单题的方法：年份比赛简单题数目AC4

2、 题可能奖项2004道富杯4二等奖2005合勤杯4二等奖2006合勤杯初赛52 题进入决赛2006合勤杯决赛4三等奖51 2 3 4 5块与块之间可能有空行最后一块之后3可能没有空行3 2 1奖项队数奖金第二课堂学分其他特等奖0-12000 元4 分保研一等奖1-21000 元3 分二等奖4-6500 元2 分三等奖8-10300 元2 分鼓励奖30-501.5 分成功参赛奖80-1001 分行。如 1001:cin n; for( i=0.;in;i+).cout ans n&n!=0)if ( nCases+ ) cout endl;.cout ans ab).cout ans endl

3、endl;d)在一个 Block，一行输出多个eger。如 1016:for(i=0 ; i0)cout ;.cout endl;d)输入是一整行的字符串的，如 1392:/ 如果你用 char buf255 来保存的：cin.getline( buf, 255 );/ 如果你用 string buf 来保存的：getline( cin , buf );输出格式a)一个 Input Block 对应一个 Output Block，Output Block 之间没有空3.Algorithm Series -ACM 赛题秒杀攻略&STL 速成Algorithm Series -ACM 赛题秒杀攻略

4、&STL 速成Technology Club- 3 -Technology Club- 4 -程序二：#include main()a,b;while(scanf(%d %d,&a, &b) != 0)/prf(%dn,a+b);return 0;ZOJ 常见错误类型程序三：#include main()a,b;while(scanf(%d %d,&a, &b)/prf(%dn,a+b);疯狂提交找错法1. 二分注释法程序一：#include main()a,b; while(scanf(%d!=EOF)return 0;%d,&a,&b)!=0)prf(%dn,a+b);2. 故意造错法#i

5、nclude return 0;Algorithm Series -ACM 赛题秒杀攻略&STL 速成Algorithm Series -ACM 赛题秒杀攻略&STL 速成Technology Club- 5 -Technology Club- 6 -Compile Error编译错误Restricted Function函数Runtime Error SIGSEGV数组越界Runtime Error SIGFPE除数为零Output Limit Exceeded输出超限Memory Limit Exceeded内存超限Time Limit Exceeded时间超限Wrong Answer错误

6、Presenion Error格式错误main()根据时间复杂度估计算法a,b;while(scanf(%d %d,&a, &b) != EOF)if(a=0 |b 3最好提前一起练过，制定好相应的策略链表 堆栈 队列树 堆Hash 并查集排序图论三人一台电脑协调好，多，队长很重要利用学会放弃，在纸上 debug关于TopCoder常见题型 HYPERLINK http:/w/ http:/w/tc简单题模拟题搜索题贪心题 DP 题图论题模块题博弈题数学题（智力题、数论题、几何题、概率题）TopCoder 和ACM 的比较学习算法途径多与高手，到 88 Algorithm 版，98 编程答疑版

7、灌水做题和看书两手抓，两手都要硬！做 zoj200 题，进 ACM 暑期集训队满世界的做题和参加比赛Algorithm Series -ACM 赛题秒杀攻略&STL 速成Algorithm Series -ACM 赛题秒杀攻略&STL 速成Technology Club- 11 -Technology Club- 12 -TopCoderACM75min5 hour快慢相对简单相对较难秒杀搞定一人比赛多人比赛个人主义团队合作精神一次提交多次提交一鼓作气百折不挠ChallengeOnline JudgeDebug 别人Debug 自己Pa r tII 用 cin 和 cout 进行输入输出不及

8、scanf 和 prf 灵活，且效率低很多。在输入数据量很大且时限小（如 1s）的情况下，用 cin 和cout 很容易超时。判断输入的结束写法 1：wh il e ( c i nn ) 写法 2：wh il e ( 1 ) c i nn ;i f ( c i n . f a il () STL十分钟速成STL:C+标准模版库b r ea k ;Preface使用 C+风格的头文件方式读入一行方法 1：c h a r buf 1000 ; c i n . ge t l in e ( bu f ,方法 2：1000 ) ;s t r ingg e t l in es ;( c i n ,s )

9、; 赛题秒杀攻略 速成 赛题秒杀攻略 速成 - 13 - - 14 -输入输出流# i n c l ud e # i n c l ud e # i n c l ud e # i n c l ud e # i n c l ud e / 在 中别忘了使用u s i ng n ame s p at d ;跳过多余的空格c i nnws ;输出指定精度的浮点数doub l e a = 1234 ;c ou t . s e t f( i o s : f i x e d ) ;容易出现的错误a s d f j k l qwe rc ou t . p r ec ic ou t anws ;输出指定宽度的浮点

10、数c ou t . f ill ( 0 ) ; c ou t . wi d t h ( 10 ) ; c ou t ae nd l; c ou t ae nd l; 输出00000012341234f o r (i= 0 ; i n ;g e tli n e ( c i n , s ) ;f o r (i = 0 ; i n ;g e tli n e ( c i n , s ) ;i + )控制输出格式c ou t . s e t f() c ou t . un s e t f() string 类c ou t s e ti o s f l a g s () c ou t r e s e ti

11、 o s f l a g s () c ou t . p r ec i c ou t . f ill () c ou t . b a s e () c ou t . wi d t h () () c ou t s e t p r ec i c ou t s e t f ill () c ou t s e t b a s e () c ou t s e tw() (# i n c l ud e 常用的运算符s = “o wo r l d ” ; 赛题秒杀攻略 速成 赛题秒杀攻略 速成 - 15 - - 16 -s += “ h ” ;s = t + “a s d f ” ; i f ( s t

12、)i s t r i ng s t r eam，o s t r i ng s t r eam/ 用法类似于 c i n 和 c ou t有用的成员函数STL 容器STL 容器实现了最常用的几种数据结构。I t er a t o r可以把 Iterator 看成某种指针，指向容器的 C 语言中的指针就是一种特殊的 Iterator。 Iterator 和指针一样支持*和-运算符可以使用 Iterator 的+运算符来遍历容器。STL Algorithm 均以 Iterator 为对象进行操作，这样便实现了算法实现与实际数据结构的分离。一般的容器都提供了begin()和end()两个函数来得到分别

13、指向容器的开头和末尾的两个 Iterator。某些可以逆向遍历的容器还提供了rbegin()和rend()两个函数来得到分别指向容器的末尾和开头的两个 Iterator。这两个 Iterator 的+运算符是逆向移动的。string 也是一种容器常用技巧：p=s . f i nd_ b s t r( 0 ,b s t r( p ) ;_o f( “ . ” ) ;s 1 =s 2 =p ) ;I t er a t o r 的分类/ 将 s 按照.分割成前后两部分Input Iterator Output IteratorForward Iteratorss t re am# i n c l u

14、d e 赛题秒杀攻略 速成 赛题秒杀攻略 速成 - 17 - - 18 -s.size()字符串长度s.c_str()转换成 chars.find(“asdf”)s.rfind(“asdf”)查找子串，如找不到则返回 string:ns.find_ _of(“tn“); s.find_not_of(“tn“); s.find_last_of(“tn“);s.find_last_not_of(“tn“);查找某个特定字符串中的任意字符s.erase(0, 5);s.erase(5);删除字符串的一部分s.insert(0, “asdf”);bstr(0, 5);bstr(5);取字符串的一部分B

15、idirectional Iteratorvector 的初始化Random Acs Iterator第一种 read only，第二种 write only，后三种 read 和write 均可。前三种只支持+运算符，使Iterator 向前移动。第四种支持+和-运算符，使 Iterator 可以双向移动。第五种支持所有的指针运算。vector arr(100, 0);/ 有 100 个 0 的 arr这样的初始化之后 arr.size()=100，如果仅仅想为 arr 保留 100 个元素的空间而保持 arr.size()=0，使用以下的代码：vector arr;vectorarr.re

16、serve(100);动态数组#include vector 的实现vector 可以看成静态数组vector arr;在遇到空间间，然后将所有数据时，一种常用的解决方案是分配一块原空间两倍大小的新空过去。常用的运算符arr = arr2;if (arr arr2) arr0容易出现的错误程序 1:for (vector:iterator it =arr.begin();it != arr.end(); it+)arr.insert(arr.end(), 0);程序 2:常用的操作arr.clear(); arr.push_back(5); arr.pop_back(); arr.front(

17、);arr.back();arr.erase(arr.begin()for (i = 0; i arr.size();i+) arr.insert(arr.end(),0);+ 5);程序 3:vector arr;main() Algorithm Series -ACM 赛题秒杀攻略&STL 速成Algorithm Series -ACM 赛题秒杀攻略&STL 速成Technology Club- 19 -Technology Club- 20 -while (1) n;Iterator 失效的情况。list 支持push_front()和 pop_front()操作。deque#inclu

18、de cinn;if (cin.fail()break;记清空全局变量arr.clear();/0;for(i =t;it;arr.push_back(t);returnpriority_queue使用最大堆实现的优先队列。0;priority_queue 中的元素要求运算符有定义。priority_queue 支持的常用操作：vectorVS 数组vector 有许多很好用的方法，为编程减少不少麻烦，同时它不需要考虑长度问题。但 vector 的效率远低于数组，在效率要求比较高的时候应慎用。list.pq.top()pq.push(5);pq.pop();取堆顶元素（最大的一个

19、）往堆中加入一个元素没有任何返回值priority_queue 不支持 clear()操作，所以一般为了实现 clear，将#includepriority_queue 在某个循环while (1) 进行定义：list 是一个双向链表。由于和 vector 同样是线性表，因此大部分函数和操作是一样的。priority_queue pq;.由双向链表的特性可知： list的 Iterator 只能是一个 BidirectioalIterator，因此不能对它像 vector 的 Iterator 一样施加算术运算。例如priority_queue 在模拟题中可以用来实现事件消息队列。l.begi

20、n()+5 是的。同样地，list 本身也不可能支持运算符，因此遍历一个 list 只能使用 Iterator。同样由于链表的特性，在 list 中，不会存在由于 insert 操作而使得原先的mapAlgorithm Series -ACM 赛题秒杀攻略&STL 速成Algorithm Series -ACM 赛题秒杀攻略&STL 速成Technology Club- 21 -Technology Club- 22 -实现了任意两种类型元#include 间的pairmap 的 Iterator 可以被视为指向一个 pair 的指针。pair 是 STL 中很好用的一个类。map m;map

21、 要求 key 对于运算符有定义。pair p; 运算符VC 和g+的STL 实现是不一样的，如果将运算符定义在类的表示第一个元素，p.second 表示第二个元素。容易出现问make_pair 函数用于构建一个 pair。例如 make_pair(0, string(“test”); 返回一个 pairclass MyClass.;for (mapstring, it+) cout.:iterator it = m.begin(); it != m.end();operator.(constMyClass&c1,constMyClass&c2) secondendl;这样得到的所有 key

22、均是有序的。常用的运算符m“asdf” = 5;a = m“td”;m“asdf”;运算符首先在 map 中查找对应的 key，若找到则直接返回一个setset 和 map 类似，只不过没有 value，也不支持运算符。set s;s.insert(5);，否则if if(s.insert(5).second); (s.find(5) != s.end();map 和 setmap 和 set 都使用了在 map 中这个key 后再返回。常用的操作m.clear(); m.find(“asdf”);树实现，树是一种平衡二叉搜索树，因此 map 和set 的查找、删除算法时间复杂度均为 log2

23、n。但是由于复/ 存在 key 则返回对应的 Iterator，否则返回杂的算法实现，因此 map 和set 的效率并不是很高。set 可以用于宽度优先搜索中的节点判重。m.end();m.size();/ 返回 map 中元素的个数Algorithm Series -ACM 赛题秒杀攻略&STL 速成Algorithm Series -ACM 赛题秒杀攻略&STL 速成Technology Club- 23 -Technology Club- 24 -a 5 = 5 , 4 , 1 , 3 , 2 ;s o r t ( a , a + 5 ) ;算算法# i n c l ud e 限于篇幅，

24、这里仅介绍最常用的算法。s o r t ( a rr . b e g i n () , a rr . e nd () s t a b l e _ s o r t ( a rr . b e g i n () , a rr . e nd () un i qu e ( a rr . b e g i n () , a rr . e nd () l owe r _bound ( a rr . b e g i n () , a rr . e nd () ,upp e r _bound ( a rr . b e g i n () , a rr . e nd () , r e v e r s e ( a rr

25、 . b e g i n () , a rr . e nd () 仿函数有时候需要把元素按照从大到小的顺序排列，可以采用以下方法：s o r t ( a rr . b e g i n () , a rr . e nd () , g r ea t e r () ;这里的 greater()就是所谓的仿函数。5 )5 )仿函数事实上是一个支持()运算符的对象。STL 的算法基本上都支持两种形式，可以在最后添加一个仿函数参数以满足不同的需求。lp a r e ( a rr 1 . b e g i n () ,a rr 1 . e nd () ,常用的关系运算仿函数e qu a l _ t o ()

26、no t _ e qu a l _ t o () g r ea t e r () g r ea t e r _ e qu a l () l e ss () l e ss _ e qu a l () a rr 2 . b e g i n () , a rr 2 . e nd () p r e v_p e rmun e x t _p e rmui on ( a rr . b e g i n () ,i on ( a rr . b e g i n () ,a rr . e nd () a rr . e nd () mi n ( a ,ma x ( a ,b )b )swa p ( a , b )有关 un i que的说明自定义仿函数unique 并不改变元素的个数例如：1222345 执行 unique 以后变成 1234545。因此 unique 通常需要配合 erase 使用:s o r t ( a rr . b e g