《第一讲认识ACMppt课件》由会员分享，可在线阅读，更多相关《第一讲认识ACMppt课件（29页珍藏版）》请在金锄头文库上搜索。
1、 ACM ACM程序程序程序程序设计设计大大大大赛赛1 1第一第一讲 认识ACM竞赛信息学院计算机科学信息学院计算机科学信息学院计算机科学信息学院计算机科学与与与与技术系技术系技术系技术系李绍华李绍华李绍华李绍华Mobile: 15915726317Mobile: 15915726317sohually163sohually163 ACM ACM程序程序程序程序设计设计大大大大赛赛2 2ACMACM：Association for Computing Machinery Association for Computing Machinery 美国计算机协会美国计算机协会美国计算机协会美国计算机
2、协会 ICPCICPC：International Collegiate Programming Contest International Collegiate Programming Contest 国际大学生程序设计竞赛国际大学生程序设计竞赛国际大学生程序设计竞赛国际大学生程序设计竞赛 ACM/ ICPC ACM/ ICPC 由美国计算机协会主办的国际大学生程序设计竞赛由美国计算机协会主办的国际大学生程序设计竞赛由美国计算机协会主办的国际大学生程序设计竞赛由美国计算机协会主办的国际大学生程序设计竞赛ACM/ICPC ACM/ICPC 是世界上公认的历史悠久、规模最大、程度是世界上公认的历
3、史悠久、规模最大、程度是世界上公认的历史悠久、规模最大、程度是世界上公认的历史悠久、规模最大、程度最高的国际大学生程序设计竞赛。最高的国际大学生程序设计竞赛。最高的国际大学生程序设计竞赛。最高的国际大学生程序设计竞赛。 ACM ACM程序程序程序程序设计设计大大大大赛赛3 3ACM/ICPC的历史的历史开展开展1970TexasA&MUniversity1970TexasA&MUniversity1977ACM1977ACM会议期间第一次总决赛会议期间第一次总决赛1997IBM1997IBM开场资助开场资助20042004全球全球840840所大学的所大学的41094109支队伍支队伍2021
4、2021第第3535届，全球届，全球76007600支队伍支队伍格局格局早期早期 北美一枝独秀北美一枝独秀最近最近 亚欧争霸亚欧争霸冠军榜冠军榜( (到达到达3 3次次) )ShanghaiJiaotongUniversityShanghaiJiaotongUniversitySaintPetersburgStateUniversityITMOSaintPetersburgStateUniversityITMOStanfordUniversityStanfordUniversity ACM ACM程序程序程序程序设计设计大大大大赛赛4 4ACM/ICPC在中国大陆在中国大陆年份年份地点地点冠军
5、冠军国家国家20102010中国哈尔滨中国哈尔滨上海交通大学上海交通大学中国中国20092009瑞典斯德哥尔摩瑞典斯德哥尔摩圣彼得堡圣彼得堡ITMOITMO俄罗斯俄罗斯20082008加拿大班夫加拿大班夫圣彼得堡圣彼得堡ITMOITMO俄罗斯俄罗斯20072007日本东京日本东京华沙大学华沙大学波兰波兰20062006美国圣安东尼奥美国圣安东尼奥萨拉托夫大学萨拉托夫大学俄罗斯俄罗斯20052005中国上海中国上海上海交通大学上海交通大学中国中国20042004捷克布拉格捷克布拉格圣彼得堡圣彼得堡ITMOITMO俄罗斯俄罗斯20032003美国洛杉矶美国洛杉矶华沙大学华沙大学波兰波兰200220
6、02美国夏威夷美国夏威夷上海交通大学上海交通大学中国中国20012001加拿大温哥华加拿大温哥华圣彼得堡州立大学圣彼得堡州立大学俄罗斯俄罗斯20002000美国奥兰多美国奥兰多圣彼得堡州立大学圣彼得堡州立大学俄罗斯俄罗斯大陆高校从大陆高校从19961996年开场参与年开场参与. . ACM ACM程序程序程序程序设计设计大大大大赛赛5 5ACM/ICPC在中国大陆在中国大陆Conti.传统强校校第一集第一集团 (Final (Final 常客常客) )清清华大学、上海交通大学大学、上海交通大学北京大学、浙江大学、中山大学、复北京大学、浙江大学、中山大学、复旦大学旦大学第二集第二集团 (Regi
7、onal (Regional金牌金牌) )武武汉大学、大学、电子科大、国防科大子科大、国防科大北北师、天大、天大、华工、福大、杭工、福大、杭电、湖、湖南大学、川大、北交、北理南大学、川大、北交、北理 ACM ACM程序程序程序程序设计设计大大大大赛赛6 6如何竞赛？如何竞赛？选手手每支每支队伍伍3 3名名队员，共用，共用1 1台机器台机器方式方式上机上机编程程处理理问题可可带纸质资料料评判判提交程序，即提交程序，即时在在线评判，判，动态排名排名试题8-108-10道英文道英文试题，可，可带字典，每字典，每经过一一题获得一个得一个代表代表该题的气球的气球时间继续5 5个小个小时( (普通从上午普
8、通从上午9 9点到下午点到下午2 2点点) )，期，期间可休可休憩憩 ACM ACM程序程序程序程序设计设计大大大大赛赛7 7 ACM ACM程序程序程序程序设计设计大大大大赛赛8 8 ACM ACM程序程序程序程序设计设计大大大大赛赛9 9 ACM ACM程序程序程序程序设计设计大大大大赛赛1010 ACM ACM程序程序程序程序设计设计大大大大赛赛1111 ACM ACM程序程序程序程序设计设计大大大大赛赛1212 ACM ACM程序程序程序程序设计设计大大大大赛赛1313如何竞赛？如何竞赛？Conti.反馈信息反馈信息缩写缩写含义含义可能原因可能原因AcceptedAcceptedACA
9、C正确正确恭喜，此题通过恭喜，此题通过WrongAnswerWrongAnswerWAWA答案错误答案错误程序结果不正确程序结果不正确CompileErrorCompileErrorCECE编译错误编译错误程序未能通过编译程序未能通过编译RunTimeErrorRunTimeErrorRERE运行时错误运行时错误程序运行中除程序运行中除0 0，栈溢出等，栈溢出等MemoryLimitExceededMemoryLimitExceededMLEMLE内存越界内存越界程序空间复杂度过低程序空间复杂度过低TimeLimitExceededTimeLimitExceededTLETLE超时超时程序时间
10、复杂度过低程序时间复杂度过低PresentationErrorPresentationErrorPEPE格式错误格式错误结果正确，格式不合要求，空格！结果正确，格式不合要求，空格！OutputLimitExceededOutputLimitExceededOLEOLE输出输出输出过多内容输出过多内容QueuingQueuing排队等待中排队等待中提交很多，正在排队等待评判提交很多，正在排队等待评判SystemErrorSystemError系统错误系统错误评测网站挂了、服务器炸了等等评测网站挂了、服务器炸了等等 ACM ACM程序程序程序程序设计设计大大大大赛赛1414Whatsrequire
11、dWhatsrequired算法才干算法才干广度：熟广度：熟习各种算法各种算法深度：特深度：特别知知晓某几某几类算法算法编程才干程才干稳定的定的 coding ability coding ability快速的快速的 debug ability debug abilityC/C+/JAVAC/C+/JAVA数学程度数学程度数数论、图论、解析几何等、解析几何等团队精神精神默契的默契的团队配合，回配合，回绝个人英雄主个人英雄主义 ACM ACM程序程序程序程序设计设计大大大大赛赛1515AlgorithmsAlgorithms常见算法常见算法Direct Direct 简单题简单题Computat
12、ional Geometry Computational Geometry 计算几何计算几何Number Theory Number Theory 数论数论Combination Combination 组合数学组合数学Search Techniques Search Techniques 搜索技术搜索技术Dynamic Programming Dynamic Programming 动态规划动态规划Graph Theory Graph Theory 图论图论Simulation Simulation 模拟题模拟题String Management String Management 字符串处
13、置字符串处置Matching Matching 匹配匹配OtherOther ACM ACM程序程序程序程序设计设计大大大大赛赛1616相关的知识相关的知识 ACM ACM程序程序程序程序设计设计大大大大赛赛1717ACM需求哪些数学知识需求哪些数学知识1 1、离散数学、离散数学、离散数学、离散数学作为计算机学科的根底，离散数学是竞赛中涉及最多的作为计算机学科的根底，离散数学是竞赛中涉及最多的作为计算机学科的根底，离散数学是竞赛中涉及最多的作为计算机学科的根底，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。数学分支，其重中之重又在于图论和组合数学，尤其是图论。
14、数学分支，其重中之重又在于图论和组合数学，尤其是图论。数学分支，其重中之重又在于图论和组合数学，尤其是图论。图论之所以运用最多是由于它的变化最多，而且可以随便地图论之所以运用最多是由于它的变化最多，而且可以随便地图论之所以运用最多是由于它的变化最多，而且可以随便地图论之所以运用最多是由于它的变化最多，而且可以随便地结合根本数据构造和许多算法的根本思想，较多用到的知识结合根本数据构造和许多算法的根本思想，较多用到的知识结合根本数据构造和许多算法的根本思想，较多用到的知识结合根本数据构造和许多算法的根本思想，较多用到的知识包括连通性判别、包括连通性判别、包括连通性判别、包括连通性判别、DFSDFS
15、和和和和BFSBFS，关节点和关键途径、欧拉回，关节点和关键途径、欧拉回，关节点和关键途径、欧拉回，关节点和关键途径、欧拉回路、最小生成树、最短途径、差分约束、二部图匹配和网络路、最小生成树、最短途径、差分约束、二部图匹配和网络路、最小生成树、最短途径、差分约束、二部图匹配和网络路、最小生成树、最短途径、差分约束、二部图匹配和网络流等等。这部分的比重很大流等等。这部分的比重很大流等等。这部分的比重很大流等等。这部分的比重很大 ，往往也是竞赛中的难题所在。，往往也是竞赛中的难题所在。，往往也是竞赛中的难题所在。，往往也是竞赛中的难题所在。竞赛中设计的组合计数问题大都需求用组合数学来处理，组竞赛中
16、设计的组合计数问题大都需求用组合数学来处理，组竞赛中设计的组合计数问题大都需求用组合数学来处理，组竞赛中设计的组合计数问题大都需求用组合数学来处理，组合数学中的知识相比于图论要简单一些，但有一部分知识要合数学中的知识相比于图论要简单一些，但有一部分知识要合数学中的知识相比于图论要简单一些，但有一部分知识要合数学中的知识相比于图论要简单一些，但有一部分知识要先对代数构造中的群论有初步了解才干进展学习。先对代数构造中的群论有初步了解才干进展学习。先对代数构造中的群论有初步了解才干进展学习。先对代数构造中的群论有初步了解才干进展学习。 ACM ACM程序程序程序程序设计设计大大大大赛赛18182 2
17、、数、数、数、数论论以素数判以素数判以素数判以素数判别别和同余和同余和同余和同余为为模型构造出来的模型构造出来的模型构造出来的模型构造出来的标题标题往往需求往往需求往往需求往往需求较较多的数多的数多的数多的数论论知知知知识识来来来来处处理，理，理，理，这这部分在部分在部分在部分在竞赛竞赛中的比重并不大，但中的比重并不大，但中的比重并不大，但中的比重并不大，但难难度很高。度很高。度很高。度很高。素数判素数判素数判素数判别别和同余最常和同余最常和同余最常和同余最常见见的是在以密的是在以密的是在以密的是在以密码码学学学学为为背景的背景的背景的背景的标题标题中出中出中出中出现现，在运用密在运用密在运用
18、密在运用密码码学常学常学常学常识识确定解答确定解答确定解答确定解答过过程之后，中心算法往往要涉及程之后，中心算法往往要涉及程之后，中心算法往往要涉及程之后，中心算法往往要涉及数数数数论论的内容。的内容。的内容。的内容。 3 3、计计算几何算几何算几何算几何计计算几何相比于其它部分来算几何相比于其它部分来算几何相比于其它部分来算几何相比于其它部分来说说是比是比是比是比较较独立的，就是独立的，就是独立的，就是独立的，就是说说它和其它和其它和其它和其它的知它的知它的知它的知识识点很少有点很少有点很少有点很少有过过多的多的多的多的结结合，合，合，合，较较常用到的部分包括常用到的部分包括常用到的部分包括
19、常用到的部分包括线线段相交的判段相交的判段相交的判段相交的判别别、多、多、多、多边边形面形面形面形面积积的的的的计计算、内点外点的判算、内点外点的判算、内点外点的判算、内点外点的判别别、凸包、凸包、凸包、凸包等等。等等。等等。等等。4 4、线线性代数、概率性代数、概率性代数、概率性代数、概率论论 、高等数学、高等数学、高等数学、高等数学 ACM ACM程序程序程序程序设计设计大大大大赛赛1919最常见题型最常见题型Dynamic Programming(Dynamic Programming(动态规划动态规划动态规划动态规划) )Greedy(Greedy(贪婪贪婪贪婪贪婪) ) Comple
20、te Search(Complete Search(穷举穷举穷举穷举) ) Flood Fill (Flood Fill (种子填充种子填充种子填充种子填充) )Shortest Path (Shortest Path (最短途径最短途径最短途径最短途径) )Recursive Search Techniques (Recursive Search Techniques (回溯回溯回溯回溯Minimum Spanning Tree Minimum Spanning Tree 最小生成树最小生成树最小生成树最小生成树KnapsackKnapsack背包背包背包背包 Computational G
21、eometry(Computational Geometry(计算几何计算几何计算几何计算几何) ) Network Flow(Network Flow(网络流网络流网络流网络流) ) Eulerian Path (Eulerian Path (欧拉回路欧拉回路欧拉回路欧拉回路) )Two-Dimensional Convex Hull (Two-Dimensional Convex Hull (二维凸包二维凸包二维凸包二维凸包) )BigNums (BigNums (大数大数大数大数) )Heuristic Search(Heuristic Search(启发式搜索启发式搜索启发式搜索启发式
22、搜索) ) Approximate Search (Approximate Search (近似搜索近似搜索近似搜索近似搜索) )Ad Hoc Problems(Ad Hoc Problems(杂题杂题杂题杂题) ) ACM ACM程序程序程序程序设计设计大大大大赛赛2020 ACM ACM程序程序程序程序设计设计大大大大赛赛2121ACM 进阶之路进阶之路 普通要做到普通要做到普通要做到普通要做到5050行以内的程序不用调试、行以内的程序不用调试、行以内的程序不用调试、行以内的程序不用调试、100100行以内的二分钟内调试胜利行以内的二分钟内调试胜利行以内的二分钟内调试胜利行以内的二分钟内调
23、试胜利. . 第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时本第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时本第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时本第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时本人精简代码，由于太常用，所以要练到写时不用想，人精简代码，由于太常用，所以要练到写时不用想，人精简代码，由于太常用，所以要练到写时不用想，人精简代码，由于太常用，所以要练到写时不用想，10-1510-15分钟内打完，分钟内打完，分钟内打完，分钟内打完，甚至关掉显示器都可以把程序打出来。甚至关掉显示器都可以把程序打出来。甚
24、至关掉显示器都可以把程序打出来。甚至关掉显示器都可以把程序打出来。 1. 1.最短路最短路最短路最短路(Floyd(Floyd、Dijstra,BellmanFord) Dijstra,BellmanFord) 2.2.最小生成树最小生成树最小生成树最小生成树( (先写个先写个先写个先写个prim,kruscalprim,kruscal要用并查集，不好写要用并查集，不好写要用并查集，不好写要用并查集，不好写) ) 3.3.大数高精度加减乘除大数高精度加减乘除大数高精度加减乘除大数高精度加减乘除4.4.二分查找二分查找二分查找二分查找. (. (代码可在五行以内代码可在五行以内代码可在五行以内代
25、码可在五行以内) ) 5.5.叉乘、判线段相交、然后写个凸包叉乘、判线段相交、然后写个凸包叉乘、判线段相交、然后写个凸包叉乘、判线段相交、然后写个凸包. . 6.BFS6.BFS、DFS,DFS,同时熟练同时熟练同时熟练同时熟练hashhash表表表表( (要熟，要灵敏要熟，要灵敏要熟，要灵敏要熟，要灵敏, ,代码要简代码要简代码要简代码要简) ) 7.7.数学上的有：辗转相除两行内，线段交点、多角形面积公式数学上的有：辗转相除两行内，线段交点、多角形面积公式数学上的有：辗转相除两行内，线段交点、多角形面积公式数学上的有：辗转相除两行内，线段交点、多角形面积公式. . 8. 8. 调用系统的调
26、用系统的调用系统的调用系统的qsort, qsort, 技巧很多，渐渐掌握技巧很多，渐渐掌握技巧很多，渐渐掌握技巧很多，渐渐掌握. . 9. 9. 恣意进制间的转换恣意进制间的转换恣意进制间的转换恣意进制间的转换 ACM ACM程序程序程序程序设计设计大大大大赛赛2222ACM 进阶之路进阶之路(Conti.) 第二阶段：练习复杂一点，但也较常用的算法。第二阶段：练习复杂一点，但也较常用的算法。第二阶段：练习复杂一点，但也较常用的算法。第二阶段：练习复杂一点，但也较常用的算法。 如：如：如：如： 1. 1. 二分图匹配匈牙利，最小途径覆盖二分图匹配匈牙利，最小途径覆盖二分图匹配匈牙利，最小途径
27、覆盖二分图匹配匈牙利，最小途径覆盖 2. 2. 网络流，最小费用流。网络流，最小费用流。网络流，最小费用流。网络流，最小费用流。 3. 3. 线段树线段树线段树线段树. . 4. 4. 并查集。并查集。并查集。并查集。 5. 5. 熟习动态规划的各个典型：熟习动态规划的各个典型：熟习动态规划的各个典型：熟习动态规划的各个典型：LCSLCS、最长递增子串、三角剖分、最长递增子串、三角剖分、最长递增子串、三角剖分、最长递增子串、三角剖分6.6.博弈类算法。博弈树，二进制法等。博弈类算法。博弈树，二进制法等。博弈类算法。博弈树，二进制法等。博弈类算法。博弈树，二进制法等。 7.7.最大团，最大独立集
28、。最大团，最大独立集。最大团，最大独立集。最大团，最大独立集。 8.8.判别点在多边形内。判别点在多边形内。判别点在多边形内。判别点在多边形内。 9. 9. 差分约束系统差分约束系统差分约束系统差分约束系统. . 10. 10. 双向广度搜索、双向广度搜索、双向广度搜索、双向广度搜索、A*A*算法，最小耗散优先算法，最小耗散优先算法，最小耗散优先算法，最小耗散优先. . ACM ACM程序程序程序程序设计设计大大大大赛赛2323小题练巧、大题练脑小题练巧、大题练脑例题例题例题例题1. 1. 三位数反转三位数反转三位数反转三位数反转输入一个三位数，分别出它的百位、十位和个位，反转后输出。输入一个
29、三位数，分别出它的百位、十位和个位，反转后输出。输入一个三位数，分别出它的百位、十位和个位，反转后输出。输入一个三位数，分别出它的百位、十位和个位，反转后输出。样例输入：样例输入：样例输入：样例输入：127127样例输出：样例输出：样例输出：样例输出：721721 ACM ACM程序程序程序程序设计设计大大大大赛赛2424细节决议成败细节决议成败例例例例题题1 1 三位数反三位数反三位数反三位数反转转输输入一个三位数，分入一个三位数，分入一个三位数，分入一个三位数，分别别出它的百位、十位和个位，反出它的百位、十位和个位，反出它的百位、十位和个位，反出它的百位、十位和个位，反转转后后后后输输出。
30、出。出。出。样样例例例例输输入：入：入：入：127127样样例例例例输输出：出：出：出：721721#include#includeint main()int main() int n; int n; scanf(%d, &n); scanf(%d, &n); printf(%d%d%dn, n%10, n/10%10, n/100); printf(%d%d%dn, n%10, n/10%10, n/100); return 0; return 0;输入是输入是输入是输入是520520，输出是输出是输出是输出是025025还还还还是是是是2525？ m=(n%10)*100+(n/10%10
31、)*m=(n%10)*100+(n/10%10)*10+(n/100);10+(n/100);Printf(“%dnPrintf(“%dn, m);/ 25, m);/ 25 Printf(“%03dn Printf(“%03dn, m);/ , m);/ 025025 ACM ACM程序程序程序程序设计设计大大大大赛赛2525小题练巧、大题练脑小题练巧、大题练脑(Conti.)例例例例题题2. 2. 阶阶乘之和乘之和乘之和乘之和输输入入入入n n，计计算算算算S=1!+2!+n!S=1!+2!+n!的未的未的未的未6 6位。位。位。位。样样例例例例输输入：入：入：入：1010样样例例例例输输
32、出：出：出：出：916800916800 ACM ACM程序程序程序程序设计设计大大大大赛赛2626细节决议成败细节决议成败细节细节细节细节1 1：当：当：当：当n=10n=10时，后时，后时，后时，后6 6位是位是位是位是037913037913，但程序只输入但程序只输入但程序只输入但程序只输入3791337913细节细节细节细节2 2：当：当：当：当n=100n=100时，输出时，输出时，输出时，输出-961703 -961703 即：除法溢出！即：除法溢出！即：除法溢出！即：除法溢出！#include#includeint main()int main() int i, j, n, S=
33、0; int i, j, n, S=0; scanf(%d, &n); scanf(%d, &n); for ( i=1; i=n; i+) int factorial=1; for ( i=1; i=n; i+) int factorial=1; for (j=1; j= i; j+) factorial *= j; for (j=1; j= i; j+) factorial *= j; S +=factorial; S +=factorial; printf(%dn, S%1000000); printf(%dn, S%1000000); return 0; return 0; ACM A
34、CM程序程序程序程序设计设计大大大大赛赛2727细节决议成败细节决议成败#include#includeint main() /int main() /处处理除溢出理除溢出理除溢出理除溢出问题问题 const int MOD=1000000; int i, j, n, S=0; const int MOD=1000000; int i, j, n, S=0; scanf(%d, &n); scanf(%d, &n); for ( i=1; i=n; i+) int fac=1; for ( i=1; i=n; i+) int fac=1; for (j=1; j= i; j+) fac= fa
35、c * j % MOD; for (j=1; j= i; j+) fac= fac * j % MOD; S = (S + factorial) % MOD; S = (S + factorial) % MOD; printf(%dn, S); printf(%dn, S); return 0; return 0;讨论：讨论：讨论：讨论：如何计算一个程序如何计算一个程序如何计算一个程序如何计算一个程序的运转时间？的运转时间？的运转时间？的运转时间？ ACM ACM程序程序程序程序设计设计大大大大赛赛2828程序运转时间程序运转时间#include#include#include #includ
36、e int main()int main() scanf(“%d scanf(“%d, &n), &n) printf(“Time used=%.21fn, printf(“Time used=%.21fn, (double)clock()/CLOCKS_PER_SEC); (double)clock()/CLOCKS_PER_SEC); return 0; return 0; 会把会把会把会把输输入所花的入所花的入所花的入所花的时间时间也也也也计计算算算算进进去！程序去！程序去！程序去！程序赋值赋值、数据文件！、数据文件！、数据文件！、数据文件！ ACM ACM程序程序程序程序设计设计大大大大赛赛2929本讲终了，谢谢大家！
