搜索
2020/1/111ACM程序竞赛入门开课号：85019授课教师：王英姿2020/1/112第一讲快速入门2020/1/113ACM题目特点:严格的输入、输出格式；有偏差则不能AC；追求高效简洁的算法。即便算法是正确的，但策略过于复杂，会导致超时；测试数据庞大；即便算法是正确的，如果在程序实现时出现误差都会被严密的测试数据查出而把程序判定为错误的；强调解决实际问题的能力。赛题与实际应用的联系很紧密，很多试题被出题者描述成一个有趣的故事。因此，读题能力、分析能力相当重要。acm比赛看重的是算法，语言相关性相对较小；2020/1/114第一部分基本输入输出2020/1/115关于ACM题目的输入输出ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，有效处理题目的输入输出，是完成ACM竞赛题目的一项基本要求。这也是困扰初学者的一大问题。2020/1/116困惑：用C/C++的输入/输出？一般来说，差别不是太大，习惯就好；cin,cout使用方便；scanf,printf控制灵活，在效率上有优势；不要混用。千万不要把cout和printf混用，因为cout是带缓冲的而printf不带，所以会使得输出的数据顺序混乱。2020/1/117输入(1)：输入不说明有多少个InputBlock,以EOF为结束标志。参见：HDOJ_1089=10892020/1/118Theinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline.Foreachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwithonelineofoutputforeachlineininput.Sampleinput:151020Sampleoutput:6302020/1/119Hdoj_1089源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n,a+b);}2020/1/1110本类输入解决方案：C语法：while(scanf(%d%d,&a,&b)!=EOF){....}C++语法：while(cinab){....}2020/1/1111说明：1.Scanf函数返回值就是读出的变量个数，如：scanf(“%d%d”,&a,&b);如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。2.EOF是一个预定义的常量，等于-1。2020/1/1112输入(2)：输入一开始就会说有N个InputBlock,下面接着是N个InputBlock。参见：HDOJ_1090=10902020/1/1113SampleInput2151020SampleOutput6302020/1/1114Hdoj_1090源代码：#includestdio.hintmain(){intn,i,a,b;scanf(%d,&n);for(i=0;in;i++){scanf(%d%d,&a,&b);printf(%d\n,a+b);}}2020/1/1115本类输入解决方案：C语法：scanf(%d,&n);for(i=0;in;i++){....}C++语法：cinn;for(i=0;in;i++){....}2020/1/1116输入(3)：输入不说明有多少个InputBlock,但以某个特殊输入为结束标志。参见：本校OJ1000=10002020/1/1117Description:Calculatea+bInput:Theinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline,00meanstheendoftheinput,anddonotneedtooutput.Output:Foreachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwithonelineofoutputforeachlineininput.SampleInput:1500SampleOutput:62020/1/1118#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)){if(a==0&&b==0)break;elseprintf(%d\n,a+b);}#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)&&(a!=0||b!=0))printf(%d\n,a+b);}2020/1/1119本类输入解决方案：C语法：while(scanf(……..)){if(…..)break;....}C++语法：while(cinn&&n!=0){....}while(scanf(……..)&&……){....}2020/1/1120输入(4)：以上几种情况的组合=1092=1093=10942020/1/1121Inputcontainsmultipletestcases.EachtestcasecontainsaintegerN,andthenNintegersfollowinthesameline.Atestcasestartingwith0terminatestheinputandthistestcaseisnottobeprocessed.SampleInput412345123450SampleOutput10152020/1/1122#includestdio.hintmain(){inttotal,n,i,j,a,sum;scanf(%d,&total);for(i=0;itotal;i++){sum=0;scanf(%d,&n);for(j=0;jn;j++){scanf(%d,&a);sum+=a;}if(itotal-1)printf(%d\n\n,sum);elseprintf(%d\n,sum);}}2020/1/1123输入(5)：输入是一整行的字符串的参见：HDOJ_1048=10482020/1/1124本类输入解决方案：C语法：charbuf[20];gets(buf);C++语法：如果用stringbuf;来保存：getline(cin,buf);如果用charbuf[255];来保存：cin.getline(buf,255);2020/1/1125输出(1)：一个InputBlock对应一个OutputBlock，OutputBlock之间没有空行。参见：HDOJ_1089=10892020/1/1126输出(2)：一个InputBlock对应一个OutputBlock，每个OutputBlock之后都有空行。参见：HDOJ_1095=10952020/1/1127ProblemDescriptionYourtaskistoCalculatea+b.InputTheinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline.OutputForeachpairofinputintegersaandbyoushouldoutputthesumofaandb,andfollowedbyablankline.SampleInput151020SampleOutput6302020/1/1128输出(3)：一个InputBlock对应一个OutputBlock，OutputBlock之间有空行。参见：HDOJ_1096=1096和第二类的区别：最后一个输出不用加空行2020/1/1129第二部分初识数据结构和算法2020/1/1130编程中的一些小技巧C语言的输入输出比C++速度要快，当程序中有大量输入输出的话，用C语言的写法会比较好。宏定义#definePi3.141592654不如写成constdoublePi=3.141592654;,,&,|,~作用非常强大n=n/2或n/=2，效率不如n=12020/1/1131memset（一般为0，-1）对较大的结构体或数组进行清零操作(1)intdata[1000]={0},*data2;myStructs1={0},s2;memset(s,0,sizeof(myStruct));…….data2=newint[n];memset(data2,0,sizeof(int)*n);(2)intarray[M][N];memset(&array[0][0],0,sizeof(array));memset(&array[0][0],-1,sizeof(array));2020/1/1132*freopen函数的使用：在调式程序时，输入的样例数据很多，若每次都用手动输入速度太慢。用freopen函数把从标准输入设备读取数据改为从文件读取数据，提交程序时只把freopen函数去掉即可。freopen(“filename”,”r”,stdin);第一个参数为文件名，如”input.txt”，与代码文件同路径,其它参数不变。freopen需写在所有读入数据代码之前。2020/1/1133程序=数据结构+算法学习一种数据结构或了解一种算法思想都不是什么困难的事情；主要障碍在于：当碰到一个具体的问题，如何用合理的数据结构+算法来解决问题。2020/1/1134(1)去年选拔赛基本题1031Description:有一些字串，有些对称，有些不对称，请将对称的串按长度排列。SampleInput:123321123454321123321sdfsdfd121212\\dd\\SampleOutput:123321\\dd\\1234543212020/1/1135基本思路：对称串的判断？应该没有问题吧……串按长度排列？也没有问题吧……最朴素的思想：把所有的对称串全找出来，放到一起，然后进行排序？如何设计……2020/1/1136不要着急考虑好数据结构……一系列的串，如何存放？链表？数组？考虑好排序策略…..不同的排序思想在复杂度、稳定性方面有差异。2020/1/1137先来了解算法复杂度……符号О一个算法的复杂度О(n):运行时间的上限是c.n,c是一个不依赖于n的常量。一个算法的复杂度О(nlogn):运行时间的上限是c.nlogn所谓的时间，往往对应一个基本步。2020/1/1138算法复杂度的概念考虑小学生做乘法，把两个n位数的x和y相乘…….假设把x的1位和y的1位相乘计