程序设计竞赛课件

ACM程序设计大赛1ACM程序设计大赛2ACM：AssociationforComputingMachinery美国计算机协会ICPC：InternationalCollegiateProgrammingContest国际大学生程序设计竞赛ACM/ICPC由美国计算机协会主办的国际大学生程序设计竞赛ACM/ICPC是世界上公认的历史悠久、规模最大、水平最高的国际大学生程序设计竞赛。ACM程序设计大赛3ACM程序设计大赛4ACM程序设计大赛55赛事等级ACM/ICPC发展到目前已包括下列各等级的赛事本地赛各所大学选拔队伍的比赛预赛从各高校的代表队中选拔队伍参加区域赛区域赛在每年9至12月举行，选拔队伍参加世界总决赛世界决赛由来自世界各所高校的数十支队伍争夺世界总冠军ACM程序设计大赛66比赛形式1支队伍1台机器（提供打印服务）上机编程解决问题（可以携带诸如书、手册、程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具）实时测试，动态排名试题6-10题全英文（可以带字典）时间：持续5个小时；如何比赛？3人组队ACM程序设计大赛77支持语言：c/c++,java,pascal题目表达：英语时限：不公布，但通常为标程的3～5倍或更多内存限制：通常在此作特别的限制错误类型：与OnlineJudge相似输入输出：网络赛采用标准输入输出，现场赛多采用文本输入输出ACM程序设计大赛8OJ常见返回结果Accept(AC)：答案正确，被系统接受WrongAnswer(WA)：答案错误RuntimeError(RE)：运行时错误CompileError(CE)：编译错误PresentationError(PE)：答案格式错误TimeLimitExceeded(TLE)：超时MemoryLimitExceeded(MLE)：超内存OutputLimitExceeded(OLE)：超输出RestrictFunctionCall(RFC)：使用不允许的APISystemError：系统错误Queuing：排队等待系统测评Judging：评测中ACM程序设计大赛99首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。如何排名？ACM程序设计大赛1010ACM.vs.校程序设计竞赛ACM竞赛团队合作精神即时提交，通过所有数据才能得分全英文题目，题目考察范围广校程序设计竞赛个人编程能力的比拼中文，考察编程基本功ACM程序设计大赛1111ACM队队员的基本原则基本要求人品好愿意花时间在这项赛事上有团队合作精神能力要求程序设计数学ACM程序设计大赛1212开课目的为我校ACM代表队培养后备人才提高分析问题和应用计算机编程解决问题的能力培养必要的自学能力培养学生的协调和沟通能力体会学习编程的快乐ACM程序设计大赛13常见的OJ南京信息工程大学杭州电子科技大学北京大学福州大学华中科技大学ACM程序设计大赛14南京信息工程大学OJ使用指南在浏览器中输入网址172.16.102.75/nuistoj/home.phpACM程序设计大赛15登录与注册ACM程序设计大赛16题目ACM程序设计大赛17点击题目名称可以浏览相应的题目信息，需要仔细阅读ACM程序设计大赛18在本地编译，运行正确后，可以提交到服务器进行进一步验证ACM程序设计大赛19提交后直接跳到状态，用户可以在该页中看到自己提交题目的情况ACM程序设计大赛20学习目的：通过教学，使学生能掌握ACM竞赛的基本知识，强化计算机编程语言、掌握与了解高级数据结构、离散数学、初等数论、数值计算、计算机算法、人工智能、时空权衡、图算法、计算几何等等内容。并能综合运用这些知识，利用程序语言进行ACM竞赛题目的设计与编写。推荐学习资料：刘汝佳，黄亮著，算法艺术与信息学竞赛，清华大学出版社，2004年1月出版郭嵩山等著，《国际大学生程序设计竞赛辅导教程》，北京大学出版社，2001年12月第1版《组合数学》《计算几何》ACM程序设计大赛21相关的知识ACM程序设计大赛22ACM需要哪些数学知识1、离散数学作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、欧拉回路、最小生成树、最短路径、差分约束、二部图匹配和网络流等等。这部分的比重很大，往往也是竞赛中的难题所在。竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，但有一部分知识要先对代数结构中的群论有初步了解才能进行学习。ACM程序设计大赛232、数论以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但难度很高。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定解答过程之后，核心算法往往要涉及数论的内容。3、计算几何计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。4、线性代数、概率论、高等数学ACM程序设计大赛24最常见题型DynamicProgramming(动态规划)Greedy(贪心)CompleteSearch(穷举)FloodFill(种子填充)ShortestPath(最短路径)RecursiveSearchTechniques(回溯）MinimumSpanningTree（最小生成树）Knapsack（背包）ComputationalGeometry(计算几何)NetworkFlow(网络流)EulerianPath(欧拉回路)Two-DimensionalConvexHull(二维凸包)BigNums(大数)HeuristicSearch(启发式搜索)ApproximateSearch(近似搜索)AdHocProblems(杂题)ACM程序设计大赛25训练方法-OJOJ的多组输入:题目一:输入2个数ab,输出a+b的和.输入包括多组数据,处理至文件结束581369159312123ACM程序设计大赛26#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF){printf(%d\n,a+b);}return0;}ACM程序设计大赛27#includeiostreamusingnamespacestd;intmain(){inta,b;while(cinab){couta+bendl;}return0;}ACM程序设计大赛28输入输出•C:–scanf速度快–printf格式容易控制•C++:–cin使用简单,自动识别类型–cout格式控制较麻烦数据规模较大时,推荐(必须)使用scanf以避免超时(TLE)C和C++的输入输出混合使用ACM程序设计大赛2929输入输出同理,我们也可以用其它字符来扫描其它类型的无关输入比如,输入年月日的信息2007-08-03scanf(“%d-%d-%d”,&y,&m,&d);其它类似ACM程序设计大赛3030输入_第一类：输入不说明有多少个InputBlock,以EOF为结束标志。ProblemDescriptionYourtaskistoCalculatea+b.Tooeasy?!Ofcourse!IspeciallydesignedtheproblemforACMbeginners.Youmusthavefoundthatsomeproblemshavethesametitleswiththisone,yes,alltheseproblemsweredesignedforthesameaim.InputTheinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline.OutputForeachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwithonelineofoutputforeachlineininput.SampleInput151020SampleOutput630ACM程序设计大赛3131源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n,a+b);return0;}#includeiostreamusingnamespacestd;intmain(){inta,b;while(cinab)couta+bendl;return0;}ACM程序设计大赛3232本类输入解决方案：C语法：while(scanf(%d%d,&a,&b)!=EOF){....}C++语法：while(cinab){....}ACM程序设计大赛3333说明（1）：1.scanf函数返回值就是读出的变量个数，如：scanf(“%d%d”,&a,&b);如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。2.EOF是一个预定义的常量，等于-1。ACM程序设计大赛3434输入_第二类：输入一开始就会说有N个InputBlock,下面接着是N个InputProblemDescriptionYourtaskistoCalculatea+b.InputInputcontainsanintegerNinthefirstline,andthenNlinesfollow.Eachlineconsistsofapairofintegersaandb,separatedbyaspace,onepairofintegersperline.OutputForeachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwithonelineofoutputforeachlineininput.SampleInput2151020SampleOutput630ACM程序设计大赛3535源代码：#includestdio.hintmain(){intn,i,a,b;scanf(%d,&n);for(i=0;in;i++){scanf(%d%d,&a,&b);printf(%d\n,a+b);}return0;}#includeiostreamusingnamespacestd;intmain(){inta,b,n;cinn;while(n--)//for(i=0;in;i++){cinab;couta+bendl;}return0;}ACM程序设计大赛3636本类输入解决方案：C语法：scanf(%d,&n);for(i=0;in;i++){....}C++语法：cinn;for(i=0;in;i++)