qssha清华大学AM集训队企业培训资料

1、Time will pierce the surface or youth, will be on the beauty of the ditch dug a shallow groove ; Jane will eat rare!A born beauty, anything to escape his sickle sweep.- Shakespeare清华大学 ACM 集训队培训资料(内部使用)一、 C+ 基础基本知识所有的 C+ 程序都是有函数组成的， 函数又叫做子程序，且每个 C+ 程序必须包含一 个 main 函数，编译器(能够把源代码转换成目标代码的程序)把翻译后的目标代码和一些

2、 启动代码组合起来，生成可执行文件， main 函数就是可执行文件的入口，所以，每个 C+ 程序有且只有一个 main 函数。下面我们看一个最简单 C+ 程序。 (程序 1.1)程序 1.1 int main()return 0;在这个程序中，如果缺少任何一个字符，编译器就无法将其翻译成机器代码。此外，C+是对大小写敏感的，这就意味着，如果我将mian()函数拼为Main(),哪么，编译器在编译这段程序的时候就会出错。编辑源文件 能够提共管理程序开发的所有步骤，包括编辑的程序成为集成开发环境(integrateddevelopment evironments, IDE )。在 windows

3、系统下，使用较为广泛的有 Microsoft Visual C+ 、 Dev-Cpp 等，在 UNIX 系统下，有 Vim 、 emacs、 eclipes 等。这些程序都能提供一个较好的 开发平台， 使我们能够方便的开发一个程序， 接下我们所要了解的都是标准 C+ ，所有源代 码都在 Dev-cpp 下编写，能够编译通过。如果我们修改程序1.1中的main()函数的名称，将其改为 Main()，那么，IDE就会给出 错误信息，比如" Linker error undefined referenee to 'WinMain16' ”，因为编译器没有找 到 main 函

4、数。接下来，我们来看一个经典的C+例子(程序1.2)程序 1.2#inelude<iostream> using namespaee std;int main(void)eout<<"Hello Wrold!"<<endl;return 0;运行结果Hello World!程序说明第一行"#include<iostream> ”，是一句预处理命令，相当于把"iostream”这个文件的所 有内容复制到当前位置，替换该行。因为在输出操作中需要做很多事，C+编译器就提供了很多已经写好的函数(成为C+标准库)，我

5、们做的只是拿来用就可以了。第二行的“usingnamespace std;”是使用标准命名空间，因为我们在程序中用到了在标准命名空间里的函数 和对象。 目前可以不了解其具体如何实现， 在以后的程序设计中可以再对其进行了解。 在明 函数中“ cout<< "Hello World! "<<e ndl; ”是在屏幕上打印“ Hello World!”，“ en dl ”表明打印 完这句话之后需要换行。如果我们替换引号内的内容，程序的输出就会相应改变。另外一个 C+ 程序例子/ ourfunc.cpp - defining your own functio

6、n#include <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 << "Done!" << endl;return 0;voi

7、d simon(int n) / define the simon() functionusing namespace std;cout << "Simon says touch your toes " << n << " times." << endl;/ void functions don't need return statements下面试运行情况：Simon says touch your toes 3 times.Pick an integer: 512Simon says touch

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

9、imple = 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 << stone <<

10、; " 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()用return 将14*sts返回给 main()。函数头

11、中的int表明stonetolb()将返回一个整数。除了 int 类型之外， C+ 的内置数据类型还有： unsigned long、long、unsigned int、unsigned short、 short、char、unsigned char、signed char、bool、float、double、long double。对于数据的输入和输出有几道练习题至 n/showproblem.php?pid=1096二、算法基础1.什么是算法算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：a. 输入。由外部题共零个或多个输入量。b. 输出。至少产生一个输出量。c. 明确性。每

12、条指令必须清楚，不具模糊性。d. 有限性。如果跟踪算法的指令，那么对于所有的情况，算法经过有限步以后终止。e. 有效性。每条指令必须非常基础，原则上使用笔和纸就可以实现例选择排序void Select ion Sort(Type a, int n)/Sort the arrat a1: n into non decreas ing order.for (int i=1; i<=n; i+)int j=1;for (i nt k=i+1; k<=n; k+)if (ak < aj)j = k;Type t = ai;ai = aj;aj = t;使用该函数时，应将Type替换为

13、C+中的数据类型3 性能分析Select ion Sort程序P所用时间定义为 T(P), T(P)是编译时间和运行时间之和。 下面我们计算一下选择排序运行时所要花费的时间C1nC2nnC3二(n - i)itimes costfor (int i=1; i<=n; i+)int j=1;for (i nt k=i+1; k<=n; k+)nif (ak < aj)C4'、(ni)k4j = k；C5tiType t = ai; ai =aj; aj = t;C6n那么该算法运行的时间nnT n =5n C2n C3' (ni) C4' (ni) C5

14、ti C6ni 二idn那么，在最坏的条件下，ti的值应该是a (n-i)i -1所以，算法的运行时间为111 1 2T n i=(G C2 C6C34C4C5)n (C3 C4 C5)n2 2 2 24 渐进符号定义：大O函数f(n) =0(g( n),念做f(n)是g(n)的大”oh”当且仅当存在正常数 c和n°，使得对于所有的n(n_n°)，有f (n )c g(n)。例对于所有n - 2有3n 2乞4n，所以3n - 2 =0(n)。对于所有 n - 6有 100n6 101n，所以 100n 6 = O( n)对于所有 n _100有 1000n2 100n -6

15、 岂 1001 n2，所以 1000n2 100n -6 =O(n2)当然对于所有 n 2有 100n2 4n 2 _10n4，所以 10n2 4n 2 =O(n4)定义：Q函数f(n) =C(g( n)，念做f(n)是g(n)的”omega”当且仅当存在正常数 c和n°,使得对于所有的n(nn°)，有f (n )_c g(n)。例对于所有有6 2n - n2-2n，所以 6 2n - n2f】(2n)。当然 62n n2-门(n)，但是门(n)T2n)。现然无论是O还是Q,都不能精确的描述一个函数定义：创函数f(n)=O(g(n)，念做f(n)是g(n)的”theta”，

16、当且仅当存在正常数 c1,c2和no，使得对于所有的n(n _ n°)，有Gg(n)乞f (n)乞c?g(n)。例对于 n _ 2有 3n 2 _ 3n 且 3n 2 乞 4n，所以 3n 2 - c-j (n)记号要比O和Q都要精确。排列生成器0( n!)void Perm(Type a, int k, int n)if (k=n) /Output permutati on.for (i nt i-1; i<n; i+) cout<<ai<<""else ak:n has more than one permutation. / G

17、en erate these recursively.for (i nt i=k; i<=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All permutati ons of ak+1: n t=ak; ak=ai; ai=t;对于下面的程序else#in clude<iostream>using n amespace std;void Perm(i nt a, int k, int n)if (k< n-1)int i, t;for (i=k; i<n; i+)t = ak;ak = ai; ai = t;Perm

18、(a, k+1, n); t = ak;ak = ai; ai = t;int i;for (i=0; i<n; i+)cout<<ai<<'t'cout<<e ndl;int main( void)int a3 = 1,2, 3;Perm(a, 0, 3);return 0;1.a: 1 2 3k: 06.a:2 1 3k: 22.a: 1 2 3k: 17.a:2 3 1k: 23.a: 1 2 3k: 28.a:3 2 1k: 14.a: 1 3 2k: 29.a:3 2 1k: 25.a: 2 1 3k: 110.a:3 1 2

19、k: 2排列生成器的另外一个版本他将输出给定n个布尔变量的所有可能的组合该程序的运行结果为1 231 322 132 313 213 12那么，该函数就完成了对一个数组进行全排列的操作 下面，分析该程序，我用圆圈代表每次函数的调用 每次函数的调用都用序号表示k=0k=2285369107void Perm (bool a, int k, int n) if (k = n)/stateme nt elseak = true;Perm(a, k+1, n); ak = false;Perm(a, k+1, n); 在上次冬季赛上有这么一道题 竞赛真理JUNNY 在经历了无数次学科竞赛的失败以后，得

20、到了一个真理：做一题就要对一题！但是 要完全正确地做对一题是要花很多时间（包括调试时间） ，而竞赛的时间有限。所以开始做 题之前最好先认真审题， 估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间 又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗” 一点分数。根据每一题解题时间的估计值， 确定一种做题方案 （即哪些题目认真做， 哪些题目 “骗”分， 哪些不做），使能在限定的时间内获得最高的得分。INPUT FORMAT:从标准输入（ cin,scanf 等）读入数据。数据有多组，

21、先输入K （ K 组数据）。每组第一行有两个正整数N和T,表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行4个正整数 W1i 、T1i 、W2i 、T2i ，分别表示第 i 题：完全正确做出来的得分，完全正确做出 来所花费的时间（单位：秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。其中，3 <N < 30, 2 < T < 1080000, 1 < W1i、W2i < 30000, 1 < T1i、T2i < T。OUTPUT FORMA T: 直接把所求得的最高得分输出。数据之间需换行。SAMPLE INPUT:24 10800

22、18 3600 3 180022 4000 12 300028 6000 0 300032 8000 24 60003 720050 5400 10 90050 7200 10 90050 5400 10 900SAMPLE OUTPUT :5070下面我们对问题进行简化。我们只要考虑是做题还是不做题。从标准输入（ cin,scanf 等）读入数据。数据只有一组,先输入 K（ K 组数据）。每组第一行 有两个正整数 N和T,表示题目的总数以及竞赛的时限（单位秒） 。以下的N行，每行2个 正整数 Wi、Ti，分别表示第i题：做出来的得分和做出来所花费的时间 （单位：秒），OUTPUT FORMA

23、T:直接把所求得的最高得分输出。数据之间需换行。SAMPLE INPUT:5 101 205 104 153 202 10void work(bool a, int n)int x;int time=0, score=0;for (x=0; x<n; x+)if (ax) 通过一个排列生成器将所有的可能送入 最高的分数。int main(void)bool a30;int n, c;cin>>n>>tSum;m = 0;for (c=0; c<n; c+)cin>>tc0;cin>>tc1;f(a, 0, n);cout<<

24、;m<<endl;return 0;work() 函数内，然后 work 函数找到在时间范围内的SAMPLE OUTPUT :65下面是用全排列生成器完成的代码 #include<iostream> 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);elsework(a, n);score += tx1; time += tx0;if (time <= tSum)if (score > m)m = score;现在我们将其优化，将 work() 和 f() 合并，就能得到更好的程序int m;using namespace std;#include<iostream>int t202; int tSum;int main(void)int n, c; cin>>n>>tSum;m = 0;for (c=0; c<n; c+) cin>>tc0;cin>>