上海大学ACM集训队培训资料(内部使用

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

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

3、，将其改为 Main()，那么，IDE就会给出 错误信息，比如 Linker error undefined referenee to WinMain16 ”，因为编译器没有找 到main函数。接下来，我们来看一个经典的C+例子(程序1.2)程序1.2#in cludeusing n ames pace std;int mai n(void)coutHello Wrold!e ndl; return 0;运行结果Hello World!程序说明第一行#include ”，是一句预处理命令，相当于把iostream”这个文件的所有内容复制到当前位置，替换该行。因为在输出操作中需要做很多事，C+编

4、译器就提供了很多已经写好的函数(成为C+标准库)，我们做的只是拿来用就可以了。第二行的“usingnames pace std;”是使用标准命名空间，因为我们在程序中用到了在标准命名空间里的函数 和对象。目前可以不了解其具体如何实现，在以后的程序设计中可以再对其进行了解。在明函数中“ cout Hello World! e ndl; ”是在屏幕上打印“ Hello World!”，“ en dl ”表明打印 完这句话之后需要换行。如果我们替换引号内的内容，程序的输出就会相应改变。另外一个C+程序例子/ ourfun c.c pp - defi ning your own function#in

5、 clude void sim on (i nt);/ function p rotot ype for sim on() int mai n()using n ames pace std;sim on (3);/ call the sim on() fun ctio ncout count;sim on(coun t);/ call it aga incout Do ne! endl;return 0;void sim on (i nt n)/ defi ne the sim on() fun cti onusing n ames pace std;cout Sim on says touc

6、h your toes n times. en dl;/ void functions dont n eed retur n stateme ntsF面试运行情况:Simon says touch your toes 3 times.Pick an in teger: 512Simon says touch your toes 512 times. Done!程序中包含了 cin语句来从键盘上获取数据。该程序中包含了除 main函数以外的另一个函数simon()，他和main函数定义的格式相同，函数的统一格式如下：type fun cti onn ame (argume ntlist)stat

7、eme nts注意，定义 simo n()的代码在 main()函数的后面，C+中不允许将函数定义在另一个函数内。每个函数的定义都是独立的，所有的函数的创建都是平等的。simo n()函数的函数头定义如下：void sim on (i nt n)以void开头表明simon()没有返回值，因此我们不能类是这样的使用它。simple = Sim on( 3);有返回值的函数如下/ con vert.c pp - con verts stone to pounds#in clude int ston etolb(i nt);/ function p rotot ypeint mai n()usin

8、g n ames pace std;int stone;cout stone;int pounds = ston etolb(st on e);cout stone stone =;cout pounds poun ds. en dl; return 0; int ston etolb(i nt sts)return 14 * sts;下面是运行情况：En ter the weight in sone: 14 14 stone = 196 pou nds.程序通过cin语句给stone提供一个值，然后在main函数中，把这个值传递给 stonetolb() 函数，这个植被赋给sts之后，sto

9、netolbO用return 将14*sts返回给 main()。函数头中的int表明stonetolb()将返回一个整数。除了 int 类型之外，C+ 的内置数据类型还有：unsigned Iong、long、unsigned int、unsigned short、 short、char、unsigned char、signed char、bool、 float、double、long double。对于数据的输入和输出有几道练习题htt P： /.c n/show problem .php?pi d=1089至htt p: /.c n/show

10、problem .php?pi d=1096二、算法基础1.什么是算法算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准:a.b.c.d.输入。由外部题共零个或多个输入量。输出。至少产生一个输出量。明确性。每条指令必须清楚，不具模糊性。有限性。如果跟踪算法的指令，那么对于所有的情况，算法经过有限步以后终止。e.有效性。每条指令必须非常基础，原则上使用笔和纸就可以实现例选择排序void Select ion Sort(T ype a, int n)/Sort the arrat a1: n into non decreas ing order. for (int i=1; i=n; i

11、+)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替换为C+中的数据类型3.性能分析程序P所用时间定义为 T(P), T(P)是编译时间和运行时间之和。 下面我们计算一下选择排序运行时所要花费的时间Select ion Sortcosttimes17C1C2for (int i=1; i=n; i+)int j=1;for (i nt k=i+1; k=n; k+)C3Z (n-i)i4if (ak 门0)，有f (n) 2有 3n +2 6有 100n +

12、6100有 1000n2 +100n 6 1001 n2，所以 1000n2 +100n 6 = 0(n2)当然对于所有2424二2有 100n +4n +2cXg(n)。对于所有 n 二1 有6X2n + n2 2n，所以 6天 2n + n2 =C(2n)。当然 6c2n + n2 =0(n)，但是 0(n) H0(2n)。现然无论是0还是Q,都不能精确的描述一个函数定义：创函数f(n)=0(g(n)，念做f(n)是g(n)的”theta”，当且仅当存在正常数 c1,c2和 no，使得对于所有的 n(n n。)，有 Cig(n) f (n) 2有3n +2 3n 且 3n +2 4n ,所

13、以 3n +2 =(n)记号要比O和Q都要精确。排列生成器0( n!)void P erm(T ype a, int k, int n)if (k=n) /Out put p ermutati on.for (i nt i-1; in; i+) coutai;else /ak:n has more tha n one p ermutati on. / Gen erate these recursively.for (i nt i=k; i=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All p ermutati ons of ak+1: n t=

14、ak; ak=ai; ai=t;对于下面的程序#in clude using n ames pace std;ai = t;Perm(a, k+1, n);void P erm(i nt a, int k, int n)t = ak; ak = ai;if (k n-1)int i, t;for (i=k; in; i+)ai = t; elseint i;for (i=0; i n; i+)t = ak;ak = ai;coutait;int main( void)int a3 = 1,2, 3;Perm(a, 0, 3); return 0;coute ndl;该程序的运行结果为11223

15、3231321323112那么，该函数就完成了对一个数组进行全排列的操作 下面，分析该程序，我用圆圈代表每次函数的调用 每次函数的调用都用序号表示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 2k: 2排列生成器的另外一个版本他将输出给定n个布尔变量的所有可能的组合void Perm (bool a, int k, int n)if (k = n)/stateme nt

16、elseak = true;Perm(a, k+1, n); ak = false;Perm(a, k+1, n);在上次冬季赛上有这么一道题竞赛真理JUNNY在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是 要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题， 估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。根据每一题解题时间的估计值，确定一种做

17、题方案（即哪些题目认真做， 哪些题目“骗”分,哪些不做），使能在限定的时间内获得最高的得分。INPUT FORMAT:从标准输入（cin,scanf等）读入数据。数据有多组，先输入 两个正整数N和T,表示题目的总数以及竞赛的时限（单位秒） 整数 W1i、T1i、W2i、T2i，分别表示第 来所花费的时间（单位：秒），“骗”来的分数，N 30, 2 T 1080000, 1 W1i、i题:“骗”W2iK（ K组数据）。每组第一行有 。以下的N行，每行4个正 完全正确做出来的得分，完全正确做出 分所花费的时间（单位秒）。其中，3 30000, 1 T1i、T2i T。OUTPUT FORMA T:

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

19、第i题：做出来的得分和做出来所花费的时间 （单位：秒），OUT PUTFORMAT:直接把所求得的最高得分输出。数据之间需换行。SAMPLE INPUT:5 101 205 104 153 202 10SAMPLE OUTPUT :65下面是用全排列生成器完成的代码#in clude using n ames pace std; void work(bool a, int n)int m;int t202;int tSum;void work(bool a, int n);int x;int time=0, score=0;for (x=0; xn; x+)void f(bool a, int k, int n)if (ax)score += tx1;if (k n)time += t x0; elseak = true; f(a, k+1, n);ak = false;f(a, k+1, n);if (time m)work(a, n);m = score;cin tcO;cin tc1;int main( void)bool a30;int n, c;cinn tSum;m = 0;for (c=0; cn; c+)