第一讲 认识ACM.pptVIP

1、＃ 第一讲 认识ACM竞赛 信息学院计算机科学与技术系 李绍华 Mobile:sohually@163.com ACM：Association for Computing Machinery 美国计算机协会 ICPC：International Collegiate Programming Contest 国际大学生程序设计竞赛 ACM/ ICPC 由美国计算机协会主办的国际大学生程序设计竞赛 ACM/ICPC 是世界上公认的历史悠久、规模最大、水平最高的国际大学生程序设计竞赛。 ACM/ICPC的历史 发展 1970 Texas AM University 1977 ACM会议期间第一次总决赛 1997 IBM开始赞助 2004 全球840所大学的4109支队伍 2010 第35届，全球7600支队伍 格局 早期 北美一枝独秀 最近 亚欧争霸 冠军榜 (达到3次) Shanghai Jiaotong University Saint Petersburg State University ITMO Stanford University ACM/ICPC在中国大陆 ACM/ICPC在中国大陆（Conti.） 如何竞赛？ 如何竞赛？（Conti.） 相关的知识 ACM需要哪些数学知识 1、离散数学 作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。 图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、欧拉回路、最小生成树、最短路径、差分约束、二部图匹配和网络流等等。这部分的比重很大 ，往往也是竞赛中的难题所在。竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，但有一部分知识要先对代数结构中的群论有初步了解才能进行学习。 2、数论 以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但难度很高。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定解答过程之后，核心算法往往要涉及数论的内容。 3、计算几何 计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。 4、线性代数、概率论 、高等数学 最常见题型 Dynamic Programming(动态规划) Greedy(贪心) Complete Search(穷举) Flood Fill (种子填充) Shortest Path (最短路径) Recursive Search Techniques (回溯） Minimum Spanning Tree （最小生成树） Knapsack（背包） Computational Geometry(计算几何) Network Flow(网络流) Eulerian Path (欧拉回路) Two-Dimensional Convex Hull (二维凸包) BigNums (大数) Heuristic Search(启发式有哪些信誉好的足球投注网站) Approximate Search (近似有哪些信誉好的足球投注网站) Ad Hoc Problems(杂题) ACM 进阶之路 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功. 第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来。 1.最短路(Floyd、Dijstra,BellmanFord) 2.最小生成树(先写个prim,kruscal要用并查集，不好写) 3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简) 7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式. 8. 调用系统的qsort, 技巧很多，慢慢掌握. 9. 任意进制间的转换 ACM 进阶之路(Conti.) 第二阶段：练习复杂一点，但也较常用的算法。 如： 1. 二分图匹配（匈牙利），最小路径覆盖 2. 网络流，最小费用流。 3. 线段树. 4. 并查集。 5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分6