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

上海大学ACM/icpc上海大学ACM/icpc集训队 何琪辰2007.3.25#上海大学ACM集训队培训资料(内部使用)一、C++基础基本知识所有的C++程序都是有函数组成的，函数又叫做子程序，且每个C++程序必须包含一个main函数，编译器(能够把源代码转换成目标代码的程序)把翻译后的目标代码和一些启动代码组合起来，生成可执行文件，main函数就是可执行文件的入口，所以，每个C++程序有且只有一个main函数。下面我们看一个最简单C++程序。(程序1.1)程序1.1intmain(){return0;}在这个程序中，如果缺少任何一个字符，编译器就无法将其翻译成机器代码。此外，C++是对大小写敏感的，这就意味着，如果我将mian()函数拼为Main(),哪么，编译器在编译这段程序的时候就会出错。编辑源文件能够提共管理程序开发的所有步骤，包括编辑的程序成为集成开发环境(integrateddevelopmentevironments,IDE)o在windows系统下，使用较为广泛的有MicrosoftVisualC++、Dev-Cpp等，在UNIX系统下，有Vim、emacs、eclipes等。这些程序都能提供一个较好的开发平台，使我们能够方便的开发一个程序，接下我们所要了解的都是标准C++,所有源代码都在Dev-cpp下编写，能够编译通过。如果我们修改程序1.1中的main()函数的名称，将其改为Main(),那么，IDE就会给出错误信息，比如“[Linkererror]undefinedreferenceto'WinMain@16'”，因为编译器没有找到main函数。接下来，我们来看一个经典的C++例子(程序1.2)程序1.2#include<iostream>usingnamespacestd;intmain(void){cout<<"HelloWrold!"<<endl;return0;}运行结果HelloWorld!程序说明第一行“#include<iostream>"，是一句预处理命令，相当于把“iostream”这个文件的所有内容复制到当前位置，替换该行。因为在输出操作中需要做很多事，C++编译器就提供了很多已经写好的函数(成为C++标准库)，我们做的只是拿来用就可以了。第二行的“usingnamespacestd;”是使用标准命名空间，因为我们在程序中用到了在标准命名空间里的函数和对象。目前可以不了解其具体如何实现，在以后的程序设计中可以再对其进行了解。在明函数中"cout<<”HelloWorld!”<<endl;”是在屏幕上打印“HelloWorld!”，“endl”表明打印完这句话之后需要换行。如果我们替换引号内的内容，程序的输出就会相应改变。另外一个C++程序例子//ourfunc.cpp--definingyourownfunction#include<iostream>voidsimon(int);//functionprototypeforsimon()intmain(){usingnamespacestd;simon(3);//callthesimon()functioncout<<"Pickaninteger:";intcount;cin>>count;simon(count);//callitagaincout<<"Done!"<<endl;return0;}voidsimon(intn)//definethesimon()function{usingnamespacestd;cout<<"Simonsaystouchyourtoes"<<n<<"times."<<endl;} //voidfunctionsdon'tneedreturnstatements下面试运行情况：Simonsaystouchyourtoes3times.Pickaninteger:512Simonsaystouchyourtoes512times.Done!程序中包含了cin语句来从键盘上获取数据。该程序中包含了除main函数以外的另一个函数simon()，他和main函数定义的格式相同，函数的统一格式如下：typefunctionname(argumentlist){statements}注意，定义simon()的代码在main()函数的后面，C++中不允许将函数定义在另一个函数内。每个函数的定义都是独立的，所有的函数的创建都是平等的。simon()函数的函数头定义如下：voidsimon(intn)以void开头表明simon()没有返回值，因此我们不能类是这样的使用它。simple=simon(3);有返回值的函数如下//convert.cpp--convertsstonetopounds#include<iostream>intstonetolb(int);//functionprototypeintmain(){usingnamespacestd;intstone;cout<<"Entertheweightinstone:";cin>>stone;intpounds=stonetolb(stone);cout<<stone<<"stone=";cout<<pounds<<"pounds."<<endl;return0;}intstonetolb(intsts){return14*sts;}下面是运行情况：Entertheweightinsone:1414stone=196pounds.程序通过cin语句给stone提供一个值，然后在main函数中，把这个值传递给stonetolb()函数，这个植被赋给sts之后，stonetolb(^return将14*sts返回给main()。函数头中的int表明stonetolb()将返回一个整数。除了int类型之外，C++的内置数据类型还有:unsignedlong、long、unsignedint>unsignedshort、short、char、unsignedchar、signedchar、bool、 float、double、longdouble。对于数据的输入和输出有几道练习题/showproblem.php?pid=1089至/showproblem.php?pid=1096二、算法基础什么是算法算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：输入。由外部题共零个或多个输入量。

输出。至少产生一个输出量。明确性。每条指令必须清楚，不具模糊性。有限性。如果跟踪算法的指令，那么对于所有的情况，算法经过有限步以后终止。有效性。每条指令必须非常基础，原则上使用笔和纸就可以实现例选择排序voidSelectionSort(Typea[],intn)//Sortthearrata[1:n]intonondecreasingorder.{for(inti=1;i<=n;i++){intj=1;for(intk=i+1;k<=n;k++)if(a[k]<a[j])j=k;Typet=a[i];a[i]=a[j];a[j]=t;}}使用该函数时，应将Type替换为C++中的数据类型3．性能分析程序P所用时间定义为T(P),T(P)是编译时间和运行时间之和。下面我们计算一下选择排序运行时所要花费的时间SelectionSortcostTOC\o"1-5"\h\zfor(inti=1;i<=n;i++) c1{intj=1; c2for(intk=i+1;k<=n;k++) c3if(a[k]<a[j]) c4j=k; c5timesnnZ(n-i)itimesnnZ(n-i)i=1Z(n-i)i=1tin那么该算法运行的时间123i=14i=15i6T(n)=cn+cn+cZ(n-i)+cZ(n123i=14i=15i6那么，在最坏的条件下，t的值应该是Z(n-i)ii=1所以，算法的运行时间为() 1 1 1 1Tm)=(c+c+c——c——c——c)n+—(c+c+c)n21262342425 23454．渐进符号定义：［大0函数f(n)=O(g(n))，念做f(n)是g(n)的大”oh”，当且仅当存在正常数c和n，使得对于所有的n(n>n)，有f(n)<cxg(n)。00例对于所有n>2有3n+2<4n，所以3n+2=O(n)。对于所有n>6有100n+6<101n，所以100n+6=O(n)对于所有n>100有1000n2+100n-6<1001n2，所以1000n2+100n-6=O(n2)当然对于所有n>2有100n2+4n+2<10n4，所以10n2+4n+2=O(n4)定义：［0函数f(n)=Q(g(n))，念做f(n)是g(n)的"omega”，当且仅当存在正常数c和n，使得对于所有的n(n>n)，有f(n)>cxg(n)。00例对于所有n>1有6x2n+n2>2n，所以6x2n+n2=Q(2n)。当然6x2n+n2=Q(n)，但是Q(n)wQ(2n)。现然无论是O还是Q，都不能精确的描述一个函数定义：［日］函数f(n)=0(g(n))，念做f(n)是g(n)的”肥1屋，当且仅当存在正常数c,c12和n，使得对于所有的n(n>n)，有cg(n)<f(n)<cg(n)。0 01 2例对于n>2有3n+2>3n且3n+2<4n，所以3n+2=0(n)

0记号要比O和Q都要精确。排列生成器0(n!)voidPerm(Typea[],intk,intn){if(k==n){//Outputpermutation.for(inti-1;i<n;i++)cout<<a[i]<<"";}else//a[k:n]hasmorethanonepermutation.//Generatetheserecursively.for(inti=k;i<=n;i++){Typet=a[k];a[k]=a[i];a[i]=t;Perm(a,k+1,n);//Allpermutationsofa[k+1:n]t=a[k];a[k]=a[i];a[i]=t;}}对于下面的程序}else}else{inti;for(i=0;i<n;i++){cout<<a[i]<<'\t';}cout<<endl;}usingnamespacestd;voidPerm(inta[],intk,intn){if(k<n-1){inti,t;for(i=k;i<n;i++){t=a[k]; }a[k]=a[i];a[i]=t;Perm(a,k+1,n);t=a[k];a[i]=t;Perm(a,k+1,n);t=a[k];a[k]=a[i];a[i]=t;}intmain(void){inta[3]={1,2,3};Perm(a,0,3);return0;}该程序的运行结果为1 2 3该程序的运行结果为1 2 31 3 22 1 32 3 13 2 13 1 2那么，该函数就完成了对一个数组进行全排列的操作下面，分析该程序，我用圆圈代表每次函数的调用每次函数的调用都用序号表示那么，该函数就完成了对一个数组进行全排列的操作下面，分析该程序，我用圆圈代表每次函数的调用每次函数的调用都用序号表示a: 2 1 3 k: 2a: 2 3 1 k: 2a: 2 1 3 k: 2a: 2 3 1 k: 2a: 3 2 1 k: 1a: 3 2 1 k: 2a: 3 1 2 k: 2a: 1 23 k: 1a: 1 23 k: 2a: 1 32 k: 2a: 2 13 k: 1排列生成器的另外一个版本他将输出给定n个布尔变量的所有可能的组合voidPerm(boola[],intk,intn){if(k==n){//statement}else{a[k]=true;Perm(a,k+1,n);a[k]=false;Perm(a,k+1,n);}}在上次冬季赛上有这么一道题竞赛真理JUNNY在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定的时间内获得最高的得分。INPUTFORMAT:从标准输入（。山耻2比等）读入数据。数据有多组，先输入K（K组数据）。每组第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行4个正整数W1i、T1i、W2i、T2i，分别表示第i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位：秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。其中，3WNW30，2WTW1080000，1WW1i、W2iW30000，1WT1i、T2iWT。OUTPUTFORMAT:直接把所求得的最高得分输出。数据之间需换行。SAMPLEINPUT:2410800183600318002240001230002860000300032800024600037200505400109005072001090050540010900SAMPLEOUTPUT:5070下面我们对问题进行简化。我们只要考虑是做题还是不做题。从标准输入1亩趾2比等）读入数据。数据只有一组，先输入K（K组数据）。每组第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行2个正整数Wi、Ti，分别表示第i题：做出来的得分和做出来所花费的时间（单位:秒），OUTPUTFORMAT:直接把所求得的最高得分输出。数据之间需换行。SAMPLEINPUT:510120510415320210SAMPLEOUTPUT:65下面是用全排列生成器完成的代码#include<iostream>usingnamespacestd;intm;intt[20][2];inttSum;voidwork(boola[],intn);voidf(boola[],intk,intn){if(k<n){a[k]=true;f(a,k+1,n);a[k]=false;f(a,k+1,n);}else{work(a,n);}}voidwork(boola[],intn){intx;inttime=0,score=0;for(x=0;x<n;x++){if(a[x]){score+=t[x][1];time+=t[x][0];}}if(time<=tSum){if(score>m){m=score;}}}intmain(void){boola[30];intn,c;cin>>n>>tSum;m=0;for(c=0;c<n;c++){cin>>t[c][0];cin>>t[c][1];}f(a,0,n);cout<<m<<endl;return0;}通过一个排列生成器将所有的可能送入work()函数内，然后work函数找到在时间范围内的最高的分数。现在我们将其优化，将work()和f()合并，就能得到更好的程序#include<iostream>usingnamespacestd;{dfs(k+1,n,cScore,cTime);dfs(k+1,n,cScore+t[k][1],cTimeintm;intt[20][2];inttSum;voiddfs(intk,