ACM入门 - 副本

设计好你的人生程序----软件学院ACM队员报名暨ACM程序设计入门软件学院冯永安2020/3/162ACM程序设计入门了解ACM/ICPCACM队员的基本原则ACM程序设计涉及的范围学习方法国内有名的OJ练习网站下学期工作和展望报名下学期的工作及展望2020/3/163一、了解ACM/ICPC1.ACM/ICPC2.ACM/ICPC在中国3.ACM/ICPC在我们学校4.如何比赛?5.比赛获奖2020/3/164ACM：AssociationforComputingMachinery美国计算机协会ICPC：InternationalCollegiateProgrammingContest国际大学生程序设计竞赛ACM/ICPC由美国计算机协会主办的国际大学生程序设计竞赛ACM/ICPC是世界上公认的历史悠久（1970年开始)、规模最大、水平最高的国际大学生程序设计竞赛。被称为“信息学中的奥林匹克”。现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。1.ACM/ICPC2020/3/1652.ACM/ICPC在中国中国大陆高校从1996年开始参加ACM/ICPC——前六届中国赛区设在上海，由上海大学承办；2002年由清华大学和西安交通大学承办；2003年由清华大学和中山大学承办。2004年由北京大学和上海交通大学承办。2005年由四川大学、北大和浙大承办。2006年由上海大学、清华和西电承办。2007年：北航、南航、吉大、西华2008年：哈工程、北交、合肥、杭电、西南民大2020/3/166目前国内基本形成五大赛站。目前基本比赛层次：网络赛-省决赛-赛区决赛-中国大陆决赛-亚洲区决赛-世界总决赛目前国内很多高校在校内组织形成周赛-月赛-季赛-校赛(选拔赛),投入大量精力，发展特别快。2020/3/167目前，在全校唯独我们学院参加过这样的比赛。从2009年开始接触比赛，到目前已经参加两届省赛和东北赛区的比赛。学校目前没有举办过类似的程序设计比赛3.ACM/ICPC在我们学校2020/3/1684.1比赛形式1支队伍1台机器，有3名队员组成上机编程解决问题（可带纸质资料,禁止存储设备和手机）基于WEB形式，在线评判(OnlineJudge)，动态排名试题8-10题(提供纸质试题)全英文（可以带字典）时间：持续5个小时(一般从上午9点到下午2点)4.如何比赛?2020/3/1692020/3/1610比赛实时排名2020/3/1611队员在答题2020/3/16124.如何比赛?4.2比赛使用的编程语言和工具目前一般提供支持C，C++，JAVA；GCC;VC++;codeblock;MinGWDeveloperStudioeclipse2020/3/16134.如何比赛?4.3比赛信息可能收到的反馈信息包括：CompileError;CERunTimeError;RETimeLimitExceeded;TEMemoryLimitExceeded;MEWrongAnswer;(最头疼的单词)WAPresentationErrorPEAccepted(最令人欣慰的单词)AC例子(测试北大)2020/3/16144.如何比赛?4.4如何排名？首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。例如：A、B两队都正确完成两道题目，其中A队提交这两题的时间分别是比赛开始后1:00和2:45，B队为1:20和2:00，但B队有一题提交了3次。这样A队的总用时为1:00+2:45=3:45，而B队为1:20+2:00+0:40=4:00，所以A队以总用时少而获胜。2020/3/1615如何能够减少惩罚时间首先在本机器编写程序调试，没问题后再在OJ上进行提交注：本机器能正确运行，一定能Accepted吗？答案不一定。这是一个必要非充分条件。2020/3/16165.比赛获奖颁发证书2020/3/16176.ACM程序设计带来的挑战团队合作精神压力承受能力算法设计和分析能力，数学基础能力个人编程能力编程基本功英语水平2020/3/1618二、ACM队员的基本原则基本要求人品好愿意花时间在这项赛事上有团队合作精神能力要求程序设计能力，基础扎实英语科技文献阅读(英语不好，问题不大)数学2020/3/1619三、ACM程序设计涉及的范围竞赛涵盖的范围很广，大致划分如下：Direct（简单题），ComputationalGeometry（计算几何），NumberTheory（数论），Combinatorics（组合数学），SearchTechniques（搜索技术）DynamicProgramming（动态规划）GraphTheory（图论），Other（其他）2020/3/1620最常见题型DynamicProgramming(动态规划)Greedy(贪心)CompleteSearch(穷举)FloodFill(种子填充)ShortestPath(最短路径)RecursiveSearchTechniques(回溯）MinimumSpanningTree（最小生成树）Knapsack（背包）ComputationalGeometry(计算几何)NetworkFlow(网络流)EulerianPath(欧拉回路)Two-DimensionalConvexHull(二维凸包)BigNums(大数)HeuristicSearch(启发式搜索)ApproximateSearch(近似搜索)AdHocProblems(杂题)2020/3/1621四、学习方法练习-总结-练习-总结-……1000道题==冠军团队合作，多向参加过比赛的老队员请教到一些论坛查阅2020/3/1622五、国内有名的OJ练习网站浙江大学：北京大学：同济大学：杭州电子科技大学哈工程哈尔滨工业大学：等等2020/3/1623相关资料2020/3/1624五、如何入门呢?由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题,因为数据输入不对，正确结果就不可能得到，看下面例子2020/3/16251.先看一个超级简单的题目：=1089Sampleinput:151020Sampleoutput:6302020/3/1626初学者很常见的一种写法：#includestdio.hvoidmain(){inta,b;scanf(“%d%d”,&a,&b);Printf(“%d”,a+b);}//思考会有什么问题呢？2020/3/1627这就是需要解决的输入输出问题，下面参考附录2020/3/16282.在实践中常常选择C++输入输出，容易处理有STL和很多常用算法，如排序等对字符串处理容易这里以刚才的例子说明在C++中输入输出简单，容易调试程序，提高效率。使用Java比较少(效率低,很容易超时)2020/3/1629六、下学期工作和展望定期指导模块进行训练举办校级ACM程序设计大赛更多需要队员自己多练习希望到时候能看到你们能获奖；同时也希望通过我们共同努力，在明年的省级以上的比赛中能取得更好的成绩2020/3/1630七、报名软件学院ACM群：118335655采用班级名+姓名申请加入以后我们会在群里共享一些学习资料,方便讨论2020/3/1631附录：程序基本输入和输出程序的输入输出是ACM程序设计的第一个门槛2020/3/16321.输入_第一类：输入不说明有多少个InputBlock,以EOF为结束标志。参考：=10892020/3/1633Hdoj_1089源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n,a+b);}2020/3/1634本类输入解决方案：C语法：while(scanf(%d%d,&a,&b)!=EOF){....}C++语法：while(cinab){....}2020/3/1635说明（1）：1.Scanf函数返回值就是读出的变量个数，如：scanf(“%d%d”,&a,&b);如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。2.EOF是一个预定义的常量，等于-1。返回2020/3/16362.输入_第二类：输入一开始就会说有N个InputBlock,下面接着是N个InputBlock。=10902020/3/16371090源代码：#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/3/1638本类输入解决方案：C语法：scanf(%d,&n);for(i=0;in;i++){....}C++语法：cinn;for(i=0;in;i++){....}2020/3/16393.输入_第三类：输入不说明有多少个InputBlock,但以某个特殊输入为结束标志。=10912020/3/16401091源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)&&(a!=0&&b!=0))printf(%d\n,a+b);}上面的程序有什么问题？2020/3/1641本类输入解决方案：C语法：while(scanf(%d,&n)&&n!=0){....}C++语法：while(cinn&&n!=0){....}2020/3/16424.输入_第四类：以上几种情况的组合=1092=1093=10942020/3/16435.输入_第五类：输入是一整行的字符串的=10482020/3/1644本类输入解决方案：C语法：charbuf[20];gets(buf);C++语法：如果用stringbuf;来保存：getline(cin,buf);如果用charbuf[255];来保存：cin.getline(buf,255);2020/3/1645说明1：scanf(“%s%s”,str1,str2)，在多个字