清华大学ACM集训队培训资料(内部使用)

1、清华大学ACM/icpc集训队2007.3.25清华大学ACM集训队培训资料（内部使用）一、C+基础基本知识所有的CH程序都是有函数组成的，函数又叫做子程序，且每个C+程序必须包含一 个main函数，编译器（能够把源代码转换成目标代码的程序）把翻译后的目标代码和一些 启动代码组合起来，生成可执行文件，main函数就是可执行文件的入口，所以，每个C+ 程序有且只有一个main函数。下而我们看一个最简单C+程序。（程序1.1） 程序1.1int main() return 0;在这个程序中，如果缺少任何一个字符，编译器就无法将其翻译成机器代码。此外，C+是对大小写敏感的，这就意味着，如果我将mia

2、n（）函数拼为Main。,哪么，编 译器在编译这段程序的时候就会出错。编辑源文件能够提共管理程序开发的所有步骤，包括编辑的程序成为集成开发环境（integrated development evironments, IDE）。在 windows 系统下，使用较为广泛的有 Microsoft Visual C+、 Dev-Cpp等，在UNIX系统下，有Vim、emacs、eclipes等。这些程序都能提供一个较好的 开发平台，使我们能够方便的开发一个程序，接下我们所要了解的都是标准C+,所有源代 码都在Dev-cpp下编写，能够编译通过。如果我们修改程序L1中的main。函数的名称,将其改为Ma

3、in（）,那么，IDE就会给出 错误信息，比如”Linker error undefined reference to、WinMain比如 因为编译器没有找 到main函数°接下来，我们来看一个经典的C+例子（程序1.2） 程序12#include<iostreanr> using namespace std;int main(void)cout«MHelIo Wrold!u«endl; return 0:运行结果Hello World!程序说明第一行a#include<iostream>是一句预处理命令，相当于把“iostream”这个文

4、件的所 有内容复制到当前位置，替换该行。因为在输出操作中需要做很多事，C+编译器就提供了 很多已经写好的函数(成为C+标准库)，我们做的只是拿来用就可以了。第二行的"using namespace std;”是使用标准命名空间，因为我们在程序中用到了在标准命名空间里的函数 和对象。目前可以不了解其具体如何实现，在以后的程序设计中可以再对其进行了解。在明 函数中 “coutvv'Hello World!«endl;"是在屏幕上打印 aHello World!”，“endl” 表明打印 完这句话之后需要换行。如果我们替换引号内的内容，程序的输出就会相应改变。另

5、外一个C+程序例子/ ourfunc.cpp - defining your own functioninclude <iostream>void simon(int); / function prototype for simon()int main()(using namespace std:simon(3); / call the simon() functioncout« "Pick an integer: "；int count;cin » count;simon(count); / call it againcout «

6、 "Done!” « endl;return 0:)void simon(int n) / define the simon() function(using namespace std:cout « "Simon says touch your toes M « n « ” times.M « endl;/ void functions don't need return statements下面试运行情况：Simon says touch your toes 3 times.Pick an integer: 51

7、2Simon says touch your toes 512 times.Done!程序中包含了 cin语句来从键盘上获取数据。该程序中包含了除main函数以外的另一个函数simon(),他和main函数定义的格式相 同，函数的统一格式如下： type functionname (argumentlist) (statements)注意，定义simon()的代码在main。函数的后面，C+中不允许将函数定义在另一个函 数内。每个函数的定义都是独立的，所有的函数的创建都是平等的。simon()函数的函数头定义如下：void simon(int n)以void开头表明simon()没有返回值，因

8、此我们不能类是这样的使用它。simple = simon(3);有返回值的函数如下/ convert.cpp - converts stone to pounds include <iostream>int stonetolb(int); / function prototypeint main()(using namespace std:int stone;cout « "Enter the weight in stone: "；cin » stone;int pounds = stonetolb(stone);cout « st

9、one « H stone = "；cout « pounds « ” pounds/*« endl;return 0:)int stonetolb(int sts)(return 14 * sts;)下面是运行情况：Enter the weight in sone: 1414 stone = 196 pounds.程序通过cin语句给stone提供一个值，然后在main函数中，把这个值传递给stonetolb() 函数，这个植被赋给sts之后，stonetolb。用retum 将14*sts返回给main。函数头中的int表明stonetol

10、b。将返回一个整数。除了 int 类型之外,C+的内置数据类型还有：unsigned longlongunsigned intxunsigned short、shortx char、unsigned char signed char book float、double、long doubleo对于数据的输入和输出有几道练习题 1089至.cii/showproblem.php?pid=1096二、算法基础1 .什么是算法莫法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：a.输入。由外部题共零个或多个愉入量。3清华大学ACM/icpc集训队2007.

11、3.25b.输出。至少产生一个输出量0C.明确性。每条指令必须清楚，不具模糊性。d.有限性。如果跟踪算法的指令，那么对于所有的情况，算法经过有限步以后终止。 e.有效性。每条指令必须非常基础，原则上使用笔和纸就可以实现例选择排序void SelectionSort(Type int n)/Sort the arrat al:n into nondecreasing order.(for (int i=l; i<=n; i+)(for (int k=i+l; k<=n: k-H-)if(ak<aj) j = k;Type t = ai;ai = aU;a(j = t；)使用该函

12、数时，应将Type替换为C+中的数据类型3.性能分析程序P所用时间定义为T(P),T(P)是编译时间和运行时间之和。下面我们计算一下选择排序运行时所要花费的时间times costSelectionSortfor (int i=l; i<=n; i+)(intj=l;for (int k=i+l: k<=n; k-H-)if(ak<aU)j = k;aj = t; c6 Type t = ai; ai = aj;那么该算法运行的时间anT(n) = q + c2n + n -z) + c4 (n -/) + c5ti + c6n r-lr-l那么，在最坏的条件下，。的值应该是

13、95-i) 所以，算法的运行时间为T(/2)=(Cj+C2+C6-4.渐进符号定义：大O函数/5) = O(g("),念做/'()是g()的大“oh”，当且仅当存在正常数C和“0，使得对于所有的，?(之0)，有/(") <cxg()。例对于所有之2有3 + 2 4 4，所以3 + 2 = O(n)»对于所有 n > 6W100/7 + 6 < 10b?,所以 100 + 6 = O(n)对于所有"N100有 1000/ +100-6<1001”2,所以 1000/J +100-6 =。/) 当然对于所有之 2有 100/J

14、 + 4 + 2 K IO”，所以 10/12 + 4 + 2 = O(n4)定义：0函数f(") = Q(g()，念做/()是g()的“omega”，当且仅当存在正常数c和o，使得对于所有的32)，有f(n) >cx g()。例对于所有M>lW6x2n+w2 >2 所以6x2" + 2 = q(2")°当然6x2"+/ =q()，但是现然无论是0还是C，都不能精确的描述一个函数定义：切函数f(") = O(g()，念做/()是g()的“theta”，当且仅当存在正常数q,C2和°,使得对于所有的，?(之0

15、)，有qg。?)</()qg()。例对于“22有3 + 223且3 + 2<4，所以3 + 2 =。()。记号要比O和。都要精确。排列生成器0(n!)void Pcrin(T),pe a, int k, int n) (if (k=n) /Output permutation.for (int i-1; i<n; i+) cout«ai«H M;)else /ak:n has more than one permutation./ Generate these recursively.for (int i=k; i<=n; i+)iype t=ak;

16、 ak=ai; ai=t;Perm(a, k+L n);/All permutations of ak+l:n t=ak; ak=ai; ai=t;)对于下面的程序#include<iostream>using namespace std;void Penn(int a, int k, int n)(if (k<n-l)(int i, t;for (i=k; i<n; i+)(t = ak;ak = ai;ai=t;Perm(a, k+L n);t = ak;ak = ai;ai = t;)elseint i;for (i=0; i<n; i+)(cout

17、1;a|i«t )cout«endl;)int inain(void)(int a3= 1,2,3);Perm(a, 0, 3);return 0;该程序的运行结果为123132213231321312那么，该函数就完成了对一个数组进行全排列的操作 下而，分析该程序，我用圆圈代表每次函数的调用 每次函数的调用都用序号表示76. a:2 1 3 k:27. a: 23 1 k:28. a: 32 1 k: 19. a: 32 1 k:210. a:3 1 2 k:2La:123k:02. a:123k: 13. a:123k:24. a:132k:25. a:21 3k: 1

18、排列生成器的另外一个版本他将输出给定n个布尔变量的所有可能的组合 void Perm (bool a, int k, int n)(if (k = n)(/statement)else(ak = true;Perm(a, k+L n);a(k = false;Perm(a, k+1, n);)在上次冬季赛上有这么一道题竞赛真理JUNNY在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是 要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限°所以开始做 清华大学ACM/icpc集训队2007.3.25题之前最好先认真审题，估计一下每一题如果要完全正

19、确地做出来所需要的时间，然后选择 一些有把握的题目先做。当然，如果做完了预先选择的题目之后还有时间，但是这些时间 又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一 点分数。根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，那些题目“骗”分， 哪些不做），使能在限定的时间内获得最高的得分。INPUT FORMAT:从标准输入（cin、scanf等）读入数据。数据有多组，先输入K （K组数据）。每组第一行有 两个正整数N和T,表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行4个正 整数Wli、Tli、W2i、T2i ,分别表示第i题：完全正确做

20、出来的得分，完全正确做出 来所花费的时间（单位：秒），“骗”来的分数，“骗”分所花费的时间（单位秒其中，3 W N W 30, 2 W T W 1080000, 1 W Wli、W2i W 30000, 1 W Tli、T2i W T。OUTPUT FORMAT:直接把所求得的最高得分输出。数据之间需换行。SAMPLE INPUT:24 1080018 3600 3 180022 4000 12 300028 6000 0 300032 8000 24 60003 720050 5400 10 90050 7200 10 90050 5400 10 900SAMPLE OUTPUT :5070

21、下面我们对问题进行简化。我们只要考虑是做题还是不做题。从标准输入（cin.scanf等）读入数据。数据只有一组，先输入K （K组数据）。每组第一行 有两个正整数N和T,表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行2个 正整数Wi、Ti,分别表示第i题：做出来的得分和做出来所花费的时间（单位：秒）,OUTPUT FORMAT:直接把所求得的最高得分输出。数据之间需换行。SAMPLE INPUT:5 101 205 104 153 202 10SAMPLE OUTPUT :65#清华大学ACM/icpc集训队2007.3.25下面是用全排列生成器完成的代码9#include<io

22、stream>using namespace std;int m;int t202;int tSum;void work(bool a, int n);void f(bool a, int k, int n) (if (k < n)(ak = true;f(a, k+1, n);ak = false;f(a, k+1, n);)else( work(a, n);)void work(bool a, int n)(int x;int time=0, score=0;for (x=0; x<n; x+)if(ax)score += txl time += txOJ;)if (ti

23、me <= tSuni)(if (score > m)(m = score;)int niain(void)(bool a30;int n, c;cin»n»tSum;m = 0;for (c=0; c<n; C+)(cin»tc0;cin»tcl;)f(a, 0, n);cout«m«endl;return 0;通过一个排列生成器将所有的可能送入work。函数内，然后work函数找到在时间范围内的最高的分数，现在我们将其优化，将work()和f()合并，就能得到更好的程序#include<iostream>using namespace std;int m;int t202;int tSum;void dfs(int k, int n, int eScore, int cTime) dfs(k+U n. eScore , cTime);dfs(k+l, n, eScore + tkl, cTime + tk(O);)else(i