ACM 入门

ACM程序设计湘潭大学谢勇[e-mail]2020/5/102第一讲ACM入门(IntroductiontoACM)2020/5/103第一部分ACM简介2020/5/104ACM--(AssociationforComputingMachinery)成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织…WhatisACM?2020/5/105我们说的“ACM”是什么？2020/5/106ACM/ICPC：ACM主办的国际大学生程序设计竞赛(InternationalCollegiateProgrammingContest)，简称ACM/ICPC，自从1977年开始至今已经连续举办35届。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，让下一代IT天才可以接触到其今后工作中将要用到的各种软件。现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。（非官方）2020/5/107ACM/ICPCinChina中国大陆高校从1996年开始参加ACM/ICPC——前六届中国赛区设在上海，由上海大学承办；2002年：清华和西安交大；2003年：清华和中山；2004年：北大和上海交大；2005年：川大、北大和浙大；2006年：上海大学、清华和西电；2007年：北航、南航、吉大、西华；2008年：哈工程、北交、中科大、杭电、西南民大；2009年：哈工大、中科大、宁波理工、武大、东华；2010年：天津大学、福大、川大、哈工程、浙江理工；2011年：大连理工、北邮、复旦、东软职院（成都）、福建师大（福州）；2020/5/108ACMinXTU2004年，第一次参加亚洲区预选赛（网络预赛）2005～2011，每年10月左右——湖南省第1～6届大学生程序设计竞赛2004～2010，每年10~12月——第29～35届ACM国际大学生程序设计竞赛亚洲区预选赛2020/5/109预期赛事（今后每年）3月，举行校内比赛（个人）4~5月，各种邀请赛10月左右，参加湖南省程序设计比赛（4个队）10~11月，参加ACM/ICPC亚洲区比赛（至少参加4～5个赛区的比赛）另外，至少有三次队内选拔个人积分赛2020/5/1010如何比赛?3人组队可以携带诸如书、手册、程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具；可能收到的反馈信息包括：CompileError;RunTimeError;TimeLimitExceeded;WrongAnswer;PresentationErrorAccepted2020/5/1011首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。如何排名？2020/5/1012比赛形式1支队伍1台机器（提供打印服务）上机编程解决问题（可带纸质资料）实时测试，动态排名试题8-12题全英文（可以带字典）时间：持续5个小时2020/5/1013ACM.vs.校程序设计竞赛ACM竞赛团队合作精神即时提交，通过所有数据才能得分全英文题目，题目考察范围广校程序设计竞赛个人编程能力的比拼中文或者英文题目，考察编程基本功2020/5/1014ACM队队员的基本原则基本要求人品好愿意花时间在这项赛事上有团队合作精神能力要求程序设计英语科技文献阅读数学2020/5/1015开课目的为湘大ACM代表队培养后备人才提高分析问题和应用计算机编程解决问题的能力培养必要的自学能力培养学生的协调和沟通能力体会学习的快乐2020/5/1016如何入门呢?2020/5/1017ACM题目特点:由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。下面，分类介绍：2020/5/1018先看一个超级简单的题目：=1089Sampleinput:151020Sampleoutput:6302020/5/1019初学者很常见的一种写法：#includestdio.hvoidmain(){inta,b;scanf(“%d%d”,&a,&b);Printf(“%d”,a+b);}2020/5/1020有什么问题呢？这就是下面需要解决的问题2020/5/1021第二部分基本输入输出2020/5/1022输入_第一类：输入不说明有多少个InputBlock,以EOF为结束标志。参见：HDOJ_1089=10892020/5/1023Hdoj_1089源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n,a+b);}2020/5/1024本类输入解决方案：C语法：while(scanf(%d%d,&a,&b)!=EOF){....}C++语法：while(cinab){....}2020/5/1025说明（1）：1.Scanf函数返回值就是读出的变量个数，如：scanf(“%d%d”,&a,&b);如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。2.EOF是一个预定义的常量，等于-1。2020/5/1026输入_第二类：输入一开始就会说有N个InputBlock,下面接着是N个InputBlock。参见：HDOJ_1090=10902020/5/1027Hdoj_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/5/1028本类输入解决方案：C语法：scanf(%d,&n);for(i=0;in;i++){....}C++语法：cinn;for(i=0;in;i++){....}2020/5/1029输入_第三类：输入不说明有多少个InputBlock,但以某个特殊输入为结束标志。参见：HDOJ_1091=10912020/5/1030Hdoj_1091源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)&&(a!=0&&b!=0))printf(%d\n,a+b);}上面的程序有什么问题？2020/5/1031本类输入解决方案：C语法：while(scanf(%d,&n)&&n!=0){....}C++语法：while(cinn&&n!=0){....}2020/5/1032输入_第四类：以上几种情况的组合=1092=1093=10942020/5/1033输入_第五类：输入是一整行的字符串的参见：HDOJ_1048=10482020/5/1034本类输入解决方案：C语法：charbuf[20];gets(buf);C++语法：如果用stringbuf;来保存：getline(cin,buf);如果用charbuf[255];来保存：cin.getline(buf,255);2020/5/1035说明（5_1）：scanf(“%s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔；若使用gets函数，应为gets(str1);gets(str2);字符串之间用回车符作分隔。通常情况下，接受短字符用scanf函数，接受长字符用gets函数。而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。2020/5/1036说明(5_2)：cin.getline的用法：getline是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：istream&getline(charline[],intsize,charendchar='\n');不用管它的返回类型，来关心它的三个参数：charline[]：就是一个字符数组，用户输入的内容将存入在该数组内。intsize:最多接受几个字符？用户超过size的输入都将不被接受。charendchar:当用户输入endchar指定的字符时，自动结束。默认是回车符。2020/5/1037说明(5_2)续结合后两个参数，getline可以方便地实现：用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。charname[4];cin.getline(name,4,'\n');由于endchar默认已经是'\n'，所以后面那行也可以写成：cin.getline(name,4);2020/5/1038思考：以下题目属于哪一类输入？=1018=10132020/5/1039输出_第一类：一个InputBlock对应一个OutputBlock，OutputBlock之间没有空行。参见：HDOJ_1089=10892020/5/1040解决方案：C语法：{....printf(%d\n,ans);}C++语法：{...coutansendl;}2020/5/1041输出_第二类：一个InputBlock对应一个OutputBlock，每个OutputBlock之后都有空行。参见：HDOJ_1095=10952020/5/10421095源代码#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n\n,a+b);}2020/5/1043解决办法：C语法：{....printf(%d\n\n,ans);}C++语法：{...coutansendlendl;}2020/5/1044输出_第三类：一个InputBlock对应一个OutputBlock，OutputBlock之间有空行。参见：HDOJ_1096=10962020/5/10451096源代码#includestdio.hintmain(){inticase,n,i,j,a,sum;scan