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

（培训体系）清华大学AM 集训队企业培训资料程序说明第一行“#include<iostream>”，是一句预处理命令，相当于把“iostream”这个文件的所有内容复制到当前位置，替换该行。

因为在输出操作中需要做很多事，C++编译器就提供了很多已经写好的函数(成为C++标准库)，我们做的只是拿来用就可以了。

第二行的“usingnamespacestd;”是使用标准命名空间，因为我们在程序中用到了在标准命名空间里的函数和对象。

目前可以不了解其具体如何实现，在以后的程序设计中可以再对其进行了解。

在明函数中“cout<<”HelloWorld!”<<endl;”是在屏幕上打印“HelloWorld!”，“endl”表明打印完这句话之后需要换行。

如果我们替换引号内的内容，程序的输出就会相应改变。

另外一个C++程序例子//--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语句来从键盘上获取数据。

第三节本堂课目标a+b输入输出练习，比较复杂的题目练习，强化知识点，常见bug，纯c。

第一部分，知识点提要1．C语言程序设计基础任务：熟悉程序设计语言、熟悉CodeBlocks、了解编码规范，学习解决问题的基本方法（查文档、书，百度，问人）。

具体内容包括：基本输入输出(scanf, printf,格式控制符)，顺序结构程序设计，数据类型，运算符及其优先级。

分支结构程序设计(if，case) ，循环语句(for, while,continue,break)。

数组，二维数组，字符串数组，RE错误，memset。

宏定义，指针简介，函数初步，结构体。

CodeBlocks工具实际编程和程序调试（观察变量、断点、中间结果输出）。

知识点大纲：HDU 8个a+b 练习HDU:1089-1096Hrbust：1885-1892模拟方式解决问题范式：用函数模拟整数输入输出思维题目hrbust 1164程序设计中函数设计范式：函数只干份内的事常见bugRe错误等细化知识点二维数组输入输出格式语法练习题目第二部分，练习重点讲解，此代码摘自网络，可能有同学看过类似的输入输出方式，这里简单讲几句，做为扫盲，暂时不需要学具体使用方法，不过要看得懂别人写的。

#include<iostream>using namespace std;int main() {int n,m,x,sum;while(cin>>n) {while(n--) {cin>>m;sum = 0;while(m--) {cin>>x;sum+=x;}cout<<sum<<endl;if(n!=0) //注意n=0的时候cout<<"\n";}}return 0;}模拟的方式输入输出整数#include<cstdio>bool END=false;int scan_int() {char c;while (c = getchar(), (c < '0' || c > '9') && (c != '-')) {if(c==EOF) {END=true;return 0;}}bool flag = (c == '-');if (flag) c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x*10 + c -48;c = getchar();}return flag ? -x : x;}char io[200];inline void print_int(int n) {if(n<0) {putchar('-');n=-n;}int k=0;do {io[k++]=n%10+'0';n/=10;} while(n);while(putchar(io[--k]),k);}int main () {int n;while(n=scan_int(),!END) {print_int(n+n);putchar('\n');}}1164 ac 代码#include<cstdio>#include<cstring>int a[1000006];int main(){int n;while(~scanf("%d",&n)){n--;memset(a,0,sizeof(a));int ans=0;for(int i=0; i<=n; i++){int b;scanf("%d",&b);if(!a[b]){ans++;a[b]=1;}}printf("%d\n",ans);for(int i=0; i<=1000000; i++){if(a[i]){ans--;if(ans==0){printf("%d\n",i);break;}else{printf("%d ",i);}}}}return 0;}解决问题过程中，函数设计范式：#include<cstdio>int jisuan (int time,int miles) {if(miles>3) {if(5<=time&&time<23) {return 14+(miles-3)*2.3;} else if(23<=time&&time<=24||0<=time&&time<5) { return 14+(miles-3)*2.3*1.2;}} else if(0<miles&&miles<=3) {return 14;}return 0;}int test(int time,int miles) {if(miles>0&&0<=time&&time<24) {int now=jisuan(time,miles);printf("%d------%d\n",time,now);return now;} else {printf("wrong!!\n");return 0;}}int main () {int time1,time2,miles1,miles2;int sum=0;scanf("%d%d",&time1,&miles1);sum+=test(time1,miles1);scanf("%d%d",&time2,&miles2);sum+=test(time2,miles2);printf("sum = %d\n",sum);}第三部分，正确的代码////#include<stdio.h>////int main(){////// printf("hello world\n");//输出字符串，注意\n表示换行// printf("hello world\n");// return 0;//}//基本数据类型//#include<stdio.h>//int main(){// int a=5;// double d=2.3;// char c='g';//注意别忘记''// long long int ll=222;//// printf("%d %lf %c %lld \n ",a,d,c,ll);//占位符和变量名要一一对应//////// return 0;//}//---------------------------////float :精确到小数点后5-6位////double:精确到小数点后15-16位//#include<stdio.h>//int main(){// int a;// double d;// float f;//// scanf("%d %lf %f",&a,&d,&f);// printf("--------------\n");//注意下面两个输出虽然一样，但是建议第二种，double类型并未定义输出用lf输出，//只是有点编译器兼容，但是输入必须区分// printf("%d %lf %f\n",a,d,f);// printf("%d %f %f\n",a,d,f);////////// return 0;//}////#include<stdio.h>//int main(){// int a;// double d;// float f;// scanf("%d %lf %f",&a,&d,&f);// printf("%d %.0f %.3f\n",a,d,f);//怎么控制浮点型后面的小数点位数//////// return 0;//}//#include<stdio.h>//int main(){//// int a=4;// int b=2;// double aa=3.0;// double bb=1.0;//整数/整数=整数浮点数/浮点数=浮点数// printf("%d %lf\n",a/b,aa/bb);////// return 0;//}//#include<stdio.h>//int main(){//// int a=4;// int b=2;// double aa=3.0;// double bb=1.0;//整数/浮点数=浮点数浮点数/整数=浮点数// printf("%f %f\n",a/aa,b/bb);////// return 0;//}//计算圆柱表面积//#include<stdio.h>//int main(){//主函数// const double pi=3.14;// double s1,s2,s;// double r,h;// scanf("%lf %lf",&r,&h);// s1=pi*r*r;// s2=2*pi*r*h;// s=2*s1+s2;// printf("%.3f\n",s);////// return 0;//}// float 5-6// double 15-16// codeblock//需要下载的软件////#include<stdio.h>//int main(){//// int aa=25;// printf("%d \n",aa);// printf("%05d ",aa);//如何在整数前加前导0,520--》025 ////}////if分支判断语句//int a=2;// int a,b;// scanf("%d %d",&a,&b);// if(a>b)// printf("%d",a);////// else if(a<b)// printf("%d",b);//// else if(a==b){// printf("%d %d",a,b);// printf("%d %d",a,b);// }// else{// printf(" ");//// }//////// return 0;//}//&& || ！三个用法//#include<stdio.h>//int main(){// int a,b,c;// scanf("%d",&a);// //&&如果两边条件都成立那么为真//// if(a>0&&b>0)//// printf("nihao\n");// // || 如果两边条件有一个成立那么为真//// if(a>0||b>0)//// printf("nihao\n");//////! 如果条件为真就，加上！条件变为假// if(!(a>0))// printf(" nihap\n");//}//switch语句用法，（去掉break怎么输出）//#include<stdio.h>//int main(){// char c;// c='/';// switch(c){// case '+':// printf("%d\n",2+2);// break;// case '-':// printf("%d\n",2-2);// break;// case '*':// printf("%d\n",2*2);// break;// case '/':// printf("%d\n",2/2);// break;// default:// printf("nihao\n");// break;//// }////}//#include<stdio.h>//int main(){//自增自减运算符// int a1=5,a2=5,a3=5,a4=5;// printf("%d\n",++a1);// printf("%d\n",--a2);// printf("%d\n",a3++);// printf("%d\n",a3);// printf("%d\n",a4--);// printf("%d\n",a4);////}//define的基本用法和意义（修改方便）//#include<stdio.h>//#define pi 3.14//int main(){//////// printf("%f\n",pi);//////}//typedef 的用途//#include<stdio.h>//typedef long long int ll;//int main(){// ll a=233333;// printf("%lld\n",a);////}//getchar和putchar//#include<stdio.h>//int main(){//// char c;// c=getchar();// putchar(c);////}转义\n\t"\\\\"数据范围，//#include<stdio.h>//int main(){// unsigned int a=4296;//注意我课上演示的int 以及long long在取到最大值输出什么，最大值+1后又输出什么// printf("%u",a);//}while循环//#include<stdio.h>//int main(){// int num=10;// while(num>0){//控制循环的条件// printf("%d\n",num);// num--;//num=num-1;//// }////// return 0;////}do-while和while两个代码得到同一个结果，注意他们区别和联系////#include<stdio.h>//int main(){// int num=1;// while(num<=10){// printf("%d\n",num);// num++;//// }//}//#include<stdio.h>//int main(){// int num=10;//// do{//// printf("%d ",num);// num--;// }while(num>0);// return 0;//}////continue用法////15/6=2...3 模的含义，其实就是余数//15%6==3//1 3 5 7 9输出1-100的偶数//#include<stdio.h>//#include<math.h>//#include<iostream>//#include<algorithm>//using namespace std;//int main(){// for( int i=1 ; i<=100 ; i++ )// {// if(i%2)//奇数// continue;判断为奇数便不执行下面// printf("%d ",i);// }// return 0;//}//!EOF和～控制多组输入//#include<stdio.h>////int main(){// int a,b;//// while( scanf("%d%d",&a,&b) !=EOF){////// printf("%d\n",a+b);//// }// return 0;//}//////#include<stdio.h>////int main(){// int a,b;//// while( ~ scanf("%d%d",&a,&b) ){////// printf("%d\n",a+b);//// }// return 0;//}求1!+2!+.....+n!//#include<stdio.h>////int main(){// int n;// int sum=0;// while(scanf("%d",&n)!=EOF){// int sum=0;//// for(int i=1;i<=n;i++){ // 此层循环为1！+2！+n! //// int cnt=1;// for(int j=1;j<=i;j++){ // 此层循环求i！// cnt=cnt*j;// //i!==cnt// }//// sum=sum+cnt;//// }// sum=sum%100000 //怎么取一个数的后六位////////// }//// return 0;////}对等关系//int a//a=a+5;//a+=5;////a=a-5;//a-=5;//a=a*5;//a*=5;////a=a/5;//a/=5;////a=a%5;//a%=5;一维数组//#include<stdio.h>////int main(){// int a[10];// for(int i=0;i<=9;i++){// a[i]=i+1;//// }// for(int i=0;i<10;i++){// printf("%d \n",a[i]);//// }////////}二维数组//#include<stdio.h>////int main()//{// int a[10][10];// int cnt=1;//// for(int i=0;i<=9;i++){// for(int j=0;j<=9;j++){// a[i][j]=cnt;// cnt++;// }// }// for(int i=0;i<=9;i++){//// for(int j=0;j<=9;j++){// printf("%3d",a[i][j]);// }// puts("");//换行的另一种表示方法//// }//////}字符串输入输出方式//#include<stdio.h>////int main(){// char str[10];// scanf("%s",str); //注意%s 没有&///// printf("%s",str);////////}//单个字符赋值，最后不要忘记加上\0才能一起输出//#include<stdio.h>////int main(){// char str[10];// // scanf("%s",str);//////// str[0]='n';// str[1]='i';// str[2]='h';// str[3]='a';// str[4]='o';// str[5]='\0'; //注意//// printf("%s",str);//// //hahah '\0' //字符串//////}//字符串\0//#include<stdio.h>////int main(){// char str[5];//// hahah//表面看长度为5，str可以存储//但是实际上需要长度为6的数组hahah'\0' //字符串//}memset//#include<stdio.h>//#include<string.h>//int main(){////// int a[10];//a 这段空间的首地址// for(int i=0;i<10;i++){// a[i]=10;// }////// memset(a,0,sizeof(a)); //sizeof释义看我课件的代码，////// for(int i=0;i<10;i++){// printf("%d ",a[i]);// }////}//memset字符赋值以字节方式，char类型为1个字节，可以//#include<stdio.h>//#include<string.h>//int main(){////// char a[10];//a 这段空间的首地址////// memset(a,'1',sizeof(a));////// for(int i=0;i<10;i++){// printf("%c ",a[i]);// }////}memset整数（反例，此种为错误赋值方式）整数为4个字节，不可以//#include<stdio.h>//#include<string.h>//int main(){//主笔Angel 日期：2016-11-1 版本1.0//// int a[10];//a 这段空间的首地址//// //char 1字节int 4字节0x01010101// memset(a,1,sizeof(a));////// for(int i=0;i<10;i++){// printf("%d ",a[i]);// }////}strlen//#include<stdio.h>//#include<string.h>//int main(){// char str[30];// while(scanf("%s",str)!=EOF){// int len=strlen(str); //string.h// printf("%d ",len);//// }//}字符串函数//#include<stdio.h>//#include<string.h>//下面3个函数都需要加上这个头文件//int main(){// char str[30];// char tmp_str[30];// while(scanf("%s %s",str,tmp_str)!=EOF){// // int len=strlen(str); //string.h// //printf("%d ",len);//// strcpy(tmp_str,str);//拷贝把str拷贝到tmp_str//// printf("%s ",tmp_str);// // NI NA// int judge=strcmp(str,tmp_str);//ANSCI比较0 -1 1返回值// printf("%d \n",judge);// }//}常用数学函数//#include<stdio.h>//#include<math.h>//#include<iostream>//#include<algorithm>//using namespace std;////int main(){// int x=abs(-1);//特殊需要额外加头文件////// int y=fabs(-2);//////////// double s=sqrt(4);//////// double pi=acos(-1);//////////// printf("%d %f %f",y,s,pi);// printf(" x=== %d",x);//特殊//////}、。

ACM培训资料目录第一篇入门篇 (3)第1章新手入门 (5)1ACM国际大学生程序设计竞赛简介 (5)2ACM竞赛需要的知识 (8)3团队配合 (14)4练习、练习、再练习 (15)5对新手的一些建议 (16)第2章C++语言介绍 (22)1C++简介 (22)2变量 (23)3C++数据类型 (25)4C++操作符 (30)5数组 (35)6字符数组 (38)7字串操作函数 (41)8过程控制 (45)9C++中的函数 (54)10函数规则 (59)第3章STL简介 (61)1泛型程序设计 (61)2STL 的组成 (67)第二篇算法篇 (102)第1章基本算法 (103)1算法初步 (103)2分治算法 (115)3搜索算法 (124)4贪婪算法 (135)第2章进阶算法 (165)1数论基础 (165)2图论算法 (180)3计算几何基础 (222)第三篇实践篇 (246)第1章《多边形》 (247)第2章《灌溉问题》 (255)第3章《L GAME》 (263)第4章《NUMBER》解题报告 (271)第5章《J OBS》解题报告 (275)第6章《包裹运送》 (283)第7章《桶的摆放》 (290)第一篇入门篇练就坚实的基础，总有一天……我们可以草木皆兵！第1章新手入门1ACM国际大学生程序设计竞赛简介1.1背景与历史1970年在美国TexasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。

1977年，该项竞赛被分为两个级别，即区域赛和总决赛，这便是现代ACM竞赛的开始。

在亚洲、美国、欧洲、太平洋地区均设有区域赛点。

1995至1996年，来自世界各地的一千多支高校的代表队参加了ACM区域竞赛。

ACM 大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。

清华大学ACM集训队培训资料（内部使用）一、C++基础基本知识所有的C++程序都是有函数组成的，函数又叫做子程序，且每个C++程序必须包含一个main函数，编译器（能够把源代码转换成目标代码的程序）把翻译后的目标代码和一些启动代码组合起来，生成可执行文件，main函数就是可执行文件的入口，所以，每个C++程序有且只有一个main函数。

下面我们看一个最简单C++程序。

(程序1.1)程序1.1int main(){return 0;}在这个程序中，如果缺少任何一个字符，编译器就无法将其翻译成机器代码。

此外，C++是对大小写敏感的，这就意味着，如果我将mian()函数拼为Main(),哪么，编译器在编译这段程序的时候就会出错。

编辑源文件能够提共管理程序开发的所有步骤，包括编辑的程序成为集成开发环境（integrated development evironments, IDE）。

在windows系统下，使用较为广泛的有Microsoft Visual C++、Dev-Cpp等，在UNIX系统下，有Vim、emacs、eclipes等。

这些程序都能提供一个较好的开发平台，使我们能够方便的开发一个程序，接下我们所要了解的都是标准C++，所有源代码都在Dev-cpp下编写，能够编译通过。

如果我们修改程序1.1中的main()函数的名称，将其改为Main()，那么，IDE就会给出错误信息，比如“[Linker error] undefined reference to `WinMain@16'”，因为编译器没有找到main函数。

接下来，我们来看一个经典的C++例子（程序1.2）程序1.2#include<iostream>using namespace std;int main(void){cout<<"Hello Wrold!"<<endl;return 0;}运行结果Hello World!程序说明第一行“#include<iostream>”，是一句预处理命令，相当于把“iostream”这个文件的所有内容复制到当前位置，替换该行。

说明：本次队内赛旨在考察大家上阶段训练情况，让大家体验一下现场的赛制。

比赛通过PC^2系统进行，这也是windows环境下ACM的标准比赛系统。

大家通过账号密码自行登陆，完成题目内容之后，选择题目，语言无论是C还是C++都选择GUN C++，并提交文件（.c/.cpp），文件名不限。

程序中不需要使用文件输入输出，按照正常的程序提交即可。

注意主函数int main()结束时返回0。

题目难度不会很大，关键在于读懂题意。

另外需要多注意输入输出格式等细节问题。

要特别注意以下几题的输出格式可能很像但是有区别（因为是多个人出的题）。

题目：A: Magical Prime NumberBy Jcf【Description】M has a little brother named R. One day, R’s math teacher tells him a new word – prime number. R is really interested in the prime number, so after he returns to home, he asked M for help. M tells him that prime number cannot be divided exactly by any other number except itself and the number 1, for example, 2,3,5,7,11 are prime numbers, but 4 is not a prime number.R: So, is X a prime number?M: YES.R: How about Y?M: ……R is so interested in it that he has asked many numbers. Your task is writing a program to help M answer R’s questions. R will ask N numbers, for each number, if it is a prime number, just tell him ‘YES’. But if it is not a prime number, you have to tell him ‘NO’, then find the nearest prime number for him.【Input Format】Line 1: A single integer, N ;Line 2 to n+1: each line has a number X, you have to judge whether X is a prime number.(1<=N<=15000,1<=X<=32767)【Output Format】For each X, first you should output the case number. Output ‘Case’, then a blank, then ‘#’, then a blank, then the number and ‘:’.(To see the sample outout)If X is a prime number, just print ‘YES’. But if X is not a prime number, please print ‘NO’ in the first line and then print an integer (the nearest prime number) in the next line.If there are two prime numbers that have same distances to X, print the bigger one. For example, if X is 9, you find 7 and 11, both their distance is 2 from 9, print 11.There needs a new line between two cases.Take it easy, just use the simple way to solve it, there is no need for you to use advanced algorithm.But pay attention to your Output Format.B: Hello World!By Lq【Description】We all know that the simplest program is the “Hello World!” program. This is a problem just as simple as the “Hello World!”In a large matrix, there are some elements has been marked. For every marked element, return a marked element whose row and column are larger than the showed element’s row and column respectiv ely. If there are multiple solutions, return the element whose row is the smallest; and if there are still multiple solutions, return the element whose column is the smallest. If there is no solution, return -1 -1.【Input Format】The input consists of several test cases.The first line of input in each test case contains one integer N (0<N ≤1000), which represents the number of marked element.Each of the next N lines containing two integers r and c, represent the element’s row and column. You can assume that 0<r, c≤300. A marked element can be repeatedly showed.The last case is followed by a line containing one zero.【Output Format】For each case, print the case number (1, 2 …), and for each element’s row and column, output the result. Your output format should imitate the sample output. Print a blank line after each test case.C: Spyke TalksBy Psw【Description】Polycarpus is the director of a large corporation. There are n secretaries working for the corporation, each of them corresponds via the famous Spyke VoIP system during the day. We know that when two people call each other via Spyke, the Spyke network assigns a unique ID to this call, a positive integer session number.One day Polycarpus wondered which secretaries are talking via the Spyke and which are not. For each secretary, he wrote out either the session number of his call or a 0 if this secretary wasn't talking via Spyke at that moment.Help Polycarpus analyze these data and find out the number of pairs of secretaries that are talking. If Polycarpus has made a mistake in the data and the described situation could not have taken place, say so.Note that the secretaries can correspond via Spyke not only with each other, but also with the people from other places. Also, Spyke conferences aren't permitted — that is, one call connects exactly two people.【Input Format】The first line contains the number of test cases — T.For each test case,the first line contains a integer n (1 ≤ n ≤ 1000) — the number of secretaries in Polycarpus's corporation.The next line contains n space-separated integers: id1, id2, ..., idn (0 ≤ idi ≤ 109). Number idi equals the number of the call session of the i-th secretary, if the secretary is talking via Spyke, or zero otherwise.Consider the secretaries indexed from 1 to n in some way.【Output Format】For each test case, print a single integer — the number of pairs of chatting secretaries, or -1 if Polycarpus's got a mistake in his records and the described situation could not have taken place.In the first test sample there are two Spyke calls between secretaries: secretary 2 and secretary 4, secretary 3 and secretary 5.In the second test sample the described situation is impossible as conferences aren't allowed.D: Must A + BBy Lw【Description】As a ACMer., you may meet a lot of problem about a + b; maybe you will think it is so boring,but you should know, every cow man’s ACM road may start form here.I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.To make the problem easier, I promise that the length of each integer will not exceed 1000.【Input Format】The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.【Output Format】For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation.If all the case are tested, output a blank line.E: Count numbersBy Htf【Description】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。