ACM-ICPC知识体系.ppt

ACM-ICPC知识体系 应翔 天津大学软件学院2004级本科生 Email: yingxiangtju@ ACM-ICPC主要的知识体系 C语言库函数 递归与回溯 ACM-ICPC主要的知识体系 数据结构 初级：链表/栈/队列/二叉树/堆 高级：线段树/树状数组/SBT/后缀数组/前缀数组 算法 动态规划、贪心算法、图算法…… 数学 组合数学、计算数学、图论/数论/群论 其他 C/C++/Java语言基础等等 数据结构 合理地存储数据，以满足数据的插入/删除/查询操作的全局最优 所谓全局最优，就是要根据实际应用设计最合理的存储结构 示例：数组和链表 回忆一下上次课的内容： 数组的特点： 内存中的连续区域 常数时间访问和写入 插入和删除比较耗时 链表的特点 在内存中分布不连续，依靠指针联系 不能随机访问 插入和删除元素为常数时间 举例 存储学生的成绩，用数组好还是链表好？ 存储加油站等待加油的汽车，哪个好？ 示例 实际情况中的数据结构更为复杂 论坛中的文章、跟贴、用户之间复杂的关系，频繁的存储、删除和查询操作 百度、Google海量的数据处理 所以需要更为复杂的数据结构 算法 算法的核心问题：效率 时间效率 空间效率 时间和空间效率必须兼顾 首先，我们来看一个具体问题 在一个排好序的数组中查找某个值 a[20] = { 0,1,2,3,7, 8,9,10,21,22, 23,24,29,35,36, 37,38,45,47,49 } 查找该数组中是否存在：17，22，45 方法一：直接查找 方法改进： 方法二：二分查找 效率分析 第一种方法： 最坏要查询N次，平均要查询N/2次 第二种方法 最坏情况下大约Log2(N)次 当N非常大的时候…… 算法的力量！ 算法 算法的范畴非常大： 动态规划 贪心算法 图论 字符串匹配 …… 数学 数学是有趣的，也是枯燥的 主要涉及的内容： 组合数学：博弈问题，群论，四色问题，也包括图论内容 计算数学：高数中的很多东西 矩阵论 概率统计 计算几何 几个有趣的问题： Nim取子游戏： 桌上放着100个棋子，A,B二人轮流从中拿走1个或2个，A先拿，每次不能多拿也不能不拿，最后谁拿到最后一个棋子就是胜利者 假设两人都很聪明，请问：谁会赢？ Nim取子 A会赢： A先拿走一个，剩下99个 然后每次B若拿1个 ，B就拿2个，B若拿2个，A就拿1个，这样两人一个回合加起来总是拿3个 可见A一定能拿到最后一个棋子 其他数学问题 概率统计：赌博时最优决策 计算几何：平面、空间的计算 组合数学：非常非常多的稀奇古怪的问题 ………… 其他 当然，作为一个出色的ACM-ICPC选手，除了数据结构、算法、数学这些大的知识外，还应该学习很多东西 每一个知识点都是循序渐进的，既有很简单的小东西，也有最深奥的学术问题 代码功底是基础，至少应该熟练掌握C/C++/Java中的一种 * * int find (int t){ int i; for( i = 0; i 20; i++){ if(a[i] == t) return 1; } return 0; } … 24 23 22 21 10 9 8 7 3 2 1 0 对于每一次查询，我们都需要依次访问它前面的所有数 29 24 23 22 21 10 9 8 7 3 2 1 0 根据有序性，每一次都判断中间的数跟要找的数哪个大。如果中间的数比要找的数大，则我们只要查找左半边，反之，则只要查右半边 int find (int t){ int begin = 0, end = 19, mid; while(begin = end){ mid = (begin + end) / 2; if(a[mid] == t) return 1; else if(a[mid] t) end = mid - 1; else begin = mid + 1; } return 0; } *