西安电子科技大学计算机学院 ACMICPC程序设计概述ppt课件

1、ACM/ICPC程序设计概述程序设计概述计算机学院计算机学院 张淑平张淑平AgendanACM/ICPC简介简介n标题例如标题例如n相关知识相关知识n相关网络资源相关网络资源n ACM/ICPC简介ACM/ICPC简介简介n由国际计算机界历史最悠久、最具权威性的组织由国际计算机界历史最悠久、最具权威性的组织ACM学会学会Association for Computer Machinery主办。目前，主办。目前，ACM国际大学生程序国际大学生程序设计大赛曾经成为参赛选手展现计算机人才的宽设计大赛曾经成为参赛选手展现计算机人才的宽广舞台，是著名大学计算机教育成果的直接表达，广舞台，是著名大学计算机

2、教育成果的直接表达，也是信息企业与世界顶尖计算机人才对话的最好也是信息企业与世界顶尖计算机人才对话的最好时机，因此，该赛事已逐渐演化成一项全球高校时机，因此，该赛事已逐渐演化成一项全球高校间计算机学科实力的竞赛。间计算机学科实力的竞赛。 ACM/ICPC简介简介nACM/ICPC竞赛标题难度大，更强调算法的效率，竞赛标题难度大，更强调算法的效率，竞赛时竞赛时3人协作，共用一台计算机，非常注重团人协作，共用一台计算机，非常注重团队协作精神；很多标题没有成熟的算法，旨在考队协作精神；很多标题没有成熟的算法，旨在考验参赛队员的创新才干；竞赛现场完全封锁，现验参赛队员的创新才干；竞赛现场完全封锁，现场

3、提交程序、现场评判，能客观、公正地展现参场提交程序、现场评判，能客观、公正地展现参赛学生的真实程度。赛学生的真实程度。 ACM/ICPC简介简介ACM/ICPC简介简介ACM/ICPC简介简介n常用环境常用环境nC+：gcc/g+、KylixnJava：jdk、eclipsen重点：言语的规范库重点：言语的规范库AgendanACM/ICPC简介简介n标题例如标题例如n相关知识相关知识n相关网络资源相关网络资源标题例如标题例如Machine ScheduleProblem G: Machine Scheduleinput file: machine.in As we all know, mac

4、hine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem. There are two mac

5、hines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, , mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, , mode_m-1. At the beginning they are both work at mode_0.Machine Schedulecont.For k jobs given, each of them can be processed in either

6、 For k jobs given, each of them can be processed in either one of the two machines in particular mode. For one of the two machines in particular mode. For example, job 0 can either be processed in machine A at example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, j

7、ob 1 can either be mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be mode_4, and so on. Thus, for job i, the constraint can be represe

8、nt as a triple represent as a triple i, x, yi, x, y, which means it can be , which means it can be processed either in machine A at mode_x, or in machine processed either in machine A at mode_x, or in machine B at mode_y.B at mode_y.Obviously, to accomplish all the jobs, we need to change Obviously,

9、 to accomplish all the jobs, we need to change the machines working mode from time to time, but the machines working mode from time to time, but unfortunately, the machines working mode can only be unfortunately, the machines working mode can only be changed by restarting it manually. By changing th

10、e changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize suitable machine, please write a program to minimize the times of restarting machines. the times

11、 of restarting machines. Machine Schedulecont.InputThe input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m n, m 100 and k k 1000. The following k lines give the constrains of the k jobs, each line is a triple: i,

12、x, y.The input will be terminated by a line containing a single zero.OutputThe output should be one integer per line, which means the minimal times of restarting machine. Sample inputSample output5 5 100 1 11 1 22 1 33 1 44 2 15 2 26 2 37 2 48 3 39 4 30 3A+B problemnusing C+:using C+:#include #inclu

13、de n int main int main n int a,b; int a,b; n while whilecin a bcin a b cout a+b cout a+b endl; endl; n 典型题例：最大子段和典型题例：最大子段和n问题：给定问题：给定n个整数能够但不全为负个整数能够但不全为负a1,a2,an, 求求i,j，使，使ai到到aj的和最大。的和最大。n例如：例如：6个数个数:-2，11，-4，13，-5，-2n最大和记做最大和记做msp,q，表示，表示ap到到aq这一段的最这一段的最大和。显然大和。显然ms1,6=20，i=2, j=4。最大子段和解法最大子段和解法

14、n最简单的是最简单的是3重循环：重循环：2重遍历，重遍历，1重求和。时间重求和。时间复杂度：复杂度：On3n改良方法之一：可以经过改良方法之一：可以经过sumi:j-1+aj来求来求sumi:j，代码见下页。时间复杂度：，代码见下页。时间复杂度：On2n改良方法之二：先计算改良方法之二：先计算psubk=sum1:k，然后然后sumi,j=psubj-psubi-1，代，代码略。时间复杂度码略。时间复杂度On2n改良方法之三：动态规划法！改良方法之三：动态规划法！典型题例：最大子段和典型题例：最大子段和int MaxSumint n, int a, int &besti, int &bestj

15、int sum = 0;forint i=1; i = n; +iint thissum = 0;forint j=i; j sumsum = thissum;besti = i, bestj = j;return sum;最大子段和的最大子段和的DP解法解法n记记bj=maxsumi:j , 1ij, 那么那么maxbk,1 k n就是就是ms1,n，即所求，即所求的全局最大和。的全局最大和。bj=max bj-1+aj, aj , 1=j=nn根据上式容易设计出最大子段和的根据上式容易设计出最大子段和的DP算法，复杂算法，复杂度仅为度仅为On ，详见代码。，详见代码。最大子段和的最大子段和

16、的DP解法解法int MaxSumint n, int aint sum = 0, b = 0;forint i=1; i 0 b += ai;elseb = ai; if b sum sum = b;return sum;AgendanACM/ICPC简介简介n标题例如标题例如n相关知识相关知识n相关网络资源相关网络资源相关知识相关知识相关知识相关知识n根本数据构造根本数据构造n线性构造线性构造n数组数组n链表链表n栈和队列栈和队列nHash表表n串串n非线性构造非线性构造n树堆、二叉树等树堆、二叉树等n图图相关知识相关知识n根本算法设计战略根本算法设计战略n分治法分治法n贪婪法贪婪法n动态

17、规划动态规划n回溯法回溯法n分枝限界法分枝限界法n时间、空间复杂度分析方法时间、空间复杂度分析方法相关知识相关知识n图论相关知识图论相关知识n组合数学知识组合数学知识n计算几何知识计算几何知识n数论知识数论知识n程序设计言语程序设计言语n其它博弈、运筹学其它博弈、运筹学Beginners Guiden根据本人的实践情况补充根据本人的实践情况补充C+类的根本概念、类的根本概念、语法、开发环境的根本运用、语法、开发环境的根本运用、STL、数据构造、数据构造的根本知识。的根本知识。n听讲座：根本数据构造、根本算法分治、贪婪、听讲座：根本数据构造、根本算法分治、贪婪、DP、搜索。、搜索。n结合讲座内容

18、做一些标题。结合讲座内容做一些标题。n看书看书?适用算法的分析与程序设计适用算法的分析与程序设计?。n做做usaco上的上的step by step。n参考参考oibh上上?入门入门FAQ?AgendanACM/ICPC简介简介n标题例如标题例如n相关知识相关知识n相关网络资源相关网络资源相关网络资源相关网络资源相关网络资源相关网络资源nUsacoGate： ace.delos /usacogate nUsacoContest： ace.delos /contestgate nUSACO： / nUsacoGate 是全美计算机奥林匹克竞赛是全美计算机奥林匹克竞赛USACO的

19、一的一个训练网站，要参与个训练网站，要参与 USACO 就必需参与就必需参与 UsacoGate 的的训练。每年都有训练。每年都有 USACO Spring,Fall,Winter,以及以及 WinterCamp 的全美竞赛，并且提供网络竞赛。的全美竞赛，并且提供网络竞赛。 nUsacoGate 的难度由浅入深，分了假设干个专题，每个专的难度由浅入深，分了假设干个专题，每个专题都有一篇讲座以及道标题供练习提供在线即时题都有一篇讲座以及道标题供练习提供在线即时评测系统。个人以为，上面的有些标题比较经典，也有评测系统。个人以为，上面的有些标题比较经典，也有些标题不好，总的来说还是值得曾经熟习程序设

20、计言语但些标题不好，总的来说还是值得曾经熟习程序设计言语但是对算法和数据构造不太了解的学生去做的。每道标题后是对算法和数据构造不太了解的学生去做的。每道标题后面都有解答，附有面都有解答，附有 C+ 程序，建议初学者多看看他人的程序，建议初学者多看看他人的解答和程序。解答和程序。n wzioi.wzms /usaco/default.asp 上有上有USACO上的上的标题和标题和Text的翻译。的翻译。相关网络资源相关网络资源n /n浙大浙大n /JudgeOnlinen北大北大n n竞赛官方网址竞赛官方网址ACM/ICP

21、C程序中的输入输出程序中的输入输出输入输出的数据类型输入输出的数据类型n整数整数n实数实数n字符字符n字符串字符串n特别强调数据的格式C言语的输入输出函数言语的输入输出函数n规范规范I/OI/O设备的数据输入输出函数设备的数据输入输出函数n字符输入、输出函数字符输入、输出函数ngetchargetchar 、putcharputchar n格式输入、输出函数格式输入、输出函数nscanfscanf 、printfprintf n字符串输入、输出函数字符串输入、输出函数ngetsgets 、putsputs C言语的文件输入输出函数言语的文件输入输出函数n文件数据的输入输出文件数据的输入输出n翻

22、开、封锁文件翻开、封锁文件nfopenfopen 、fclosefclosen判别文件能否终了判别文件能否终了nfeoffeofn字符输入、输出函数字符输入、输出函数nfgetcfgetc 、fputcfputc 、getcgetc 、putcputc n格式输入、输出函数格式输入、输出函数nfscanffscanf 、fprintffprintf n字符串输入、输出函数字符串输入、输出函数nfgetsfgets 、fputsfputs A+B problemnusing C:using C:#include #include n int main int main n int a,b; in

23、t a,b;n while whilescanfscanf%d %d,&a, &b%d %d,&a, &b != EOF != EOFn printf printf%dn,a+b%dn,a+b; ; n 还可写成：scanf %d %d,&a, &b = 2A+B problem文件输入输出文件输入输出nusing C:using C:#include #include n FILE FILE * *fin,fin,* *fout;fout;n int main int main n int a,b; int a,b; n fin=fopen fin=fopen“input.in“input.

24、in, ,r r; ;n fout=fopen fout=fopen“output.out“output.out, ,w w; ;n while whilefscanffscanffin,%d %d,&a, &bfin,%d %d,&a, &b != EOF != EOFn fprintf fprintffout,%dn,a+bfout,%dn,a+b; ; n 写成：fin=stdin; fout=stdout;将等价于屏幕输入输出C+的规范输出流的规范输出流n规范输出流对象规范输出流对象coutcoutn字符、整数、实数、字符串等的输出都用字符、整数、实数、字符串等的输出都用coutcou

25、tncout cout cin 变量名变量名ncin.getcin.getncin.getlinecin.getlineA+B problemnusing C+:using C+:#include #include n int main int main n int a,b; int a,b; n while whilecin a bcin a b cout a+b cout a+b endl; endl; n C+的文件输入输出流的文件输入输出流n文件流文件流n输入文件流输入文件流ifstreamifstream、输出文件流、输出文件流ofstream ofstream 、输入、输入/ /输

26、出文件流输出文件流fstreamfstreamn创建并翻开文件流对象创建并翻开文件流对象n文件的读写文件的读写A+B problem文件输入输出文件输入输出nusing C+:using C+:#include #include n ifstream fin ifstream fin“input.in“input.in; ;n ofstream fout ofstream fout“output.out“output.out; ;n int main int main n int a,b; int a,b; n while whilefin a bfin a b fout a+b fout a

27、+b ab;例：例：C输出实数输出实数输出，保管输出，保管4位小数：位小数：C: double a; printf “%.4lfn,a;例：例：C+输出实数输出实数nC+:n #include n #include n int main n double a = 3.1415926535897932;n coutaendl;n cout.precision 7; coutaendl;n cout.setf ios:fixed; cout.precision 8;n coutaendl;n coutsetiosflags ios:fixedsetprecision 8aendl;n return

28、 0;n 例：例：C+输出实数输出实数nC+:n #include n #include n #include n int main n double a = 3.1415926535, b = acos -1;n cout.setf ios:fixed; cout.precision 15;n couta,bendl;n if a=b coutbendl;n else coutaendl;n if fabs a-b 1e-7 coutbendl;n else coutaendl;n return 0;n 例：例：C输入输出字符输入输出字符nC:n #include n int main n

29、char a;n FILE * fin = fopen input.txt,r;n while fscanf fin,%c,&a != EOFn printf %d,%cn,a,a;n n return 0;n input.txt:1+2 = 3 ; 4+5= 9例：例：C+输入输出字符输入输出字符nC+:n #include n #include n int main n char a;n ifstream fin input.txt;n while finan coutint a,aendl;n n return 0;n input.txt:1+2 = 3 ; 4+5= 9例：例：C+输入

30、输出字符输入输出字符nC+:n #include n #include n int main n char a;n ifstream fin input.txt;n while fin.get an coutinta,aendl;n n return 0;n input.txt:1+2 = 3 ; 4+5= 9例：例：C输入输出字符串输入输出字符串v读写字符串串以空格、回车分隔v #include v int main v char a100;v while scanf%s,a = 1v printf %sn,a;v return 0;v 例：例：C输入输出字符串续输入输出字符串续v读写字符串

31、串中有空格,串以回车分隔v#include v int main v char a100;v while gets a v printf %sn,a;v return 0;v 例：例：C+输入输出字符串输入输出字符串v读写字符串串以空格、回车分隔v #include v int main v char a100;v while cinav coutaendl;v return 0;v 例：例：C+读入一行字符串读入一行字符串 #include #include #include int main int b=0; std:string s; ifstream fin input.txt; wh

32、ile getline fin, s cout+b:sendl; return 0; input.txt:1+2 = 3 ; 4+5= 9例：例：C从文件读入字符串从文件读入字符串v从文件读字符串以回车分隔v int main v char a100;v int b=0;v FILE *fin=fopen input.txt,r;v while fgets a, 100, finv printf %d:%s, +b, a;v return 0;v input.txt:1+2 = 3 ; 4+5= 9例：例：C+从文件读入字符串从文件读入字符串v从文件读字符串以回车分隔v #include v #include v int main v char a100;v int b=0;v ifstream fin input.txt;v while fin.getline a, 100v cout+b:aendl;v return 0;v input.txt:1+2 = 3 ; 4+5= 9实例实例输入假