ACM-ICPC知识体系

1、ACM-ICPC知识体系Email: 1ACM-ICPC主要的知识体系C语言库函数递归与回溯2ACM-ICPC主要的知识体系数据结构初级：链表/栈/队列/二叉树/堆高级：线段树/树状数组/SBT/后缀数组/前缀数组算法动态规划、贪心算法、图算法数学组合数学、计算数学、图论/数论/群论其他C/C+/Java语言基础等等3数据结构合理地存储数据，以满足数据的插入/删除/查询操作的全局最优所谓全局最优，就是要根据实际应用设计最合理的存储结构4示例：数组和链表回忆一下上次课的内容：数组的特点：内存中的连续区域常数时间访问和写入插入和删除比较耗时链表的特点在内存中分布不连续，依靠指针联系不能随机访问插入

2、和删除元素为常数时间5举例存储学生的成绩，用数组好还是链表好？存储加油站等待加油的汽车，哪个好？6示例实际情况中的数据结构更为复杂论坛中的文章、跟贴、用户之间复杂的关系，频繁的存储、删除和查询操作百度、Google海量的数据处理所以需要更为复杂的数据结构7算法算法的核心问题：效率时间效率空间效率时间和空间效率必须兼顾首先，我们来看一个具体问题8在一个排好序的数组中查找某个值 a20 = 0,1,2,3,7,8,9,10,21,22,23,24,29,35,36,37,38,45,47,49 查找该数组中是否存在：17，22，459方法一：直接查找int find (int t)int i;fo

3、r( i = 0; i 20; i+)if(ai = t) return 1;return 0; 1001237891021222324对于每一次查询，我们都需要依次访问它前面的所有数11方法改进：0123789102122232429根据有序性，每一次都判断中间的数跟要找的数哪个大。如果中间的数比要找的数大，则我们只要查找左半边，反之，则只要查右半边12方法二：二分查找int find (int t)int begin = 0, end = 19, mid;while(begin = end)mid = (begin + end) / 2;if(amid = t) return 1;else

4、 if(amid t) end = mid - 1;else begin = mid + 1;return 0; 13效率分析第一种方法：最坏要查询N次，平均要查询N/2次第二种方法最坏情况下大约Log2(N)次当N非常大的时候算法的力量！14算法算法的范畴非常大：动态规划贪心算法图论字符串匹配15数学数学是有趣的，也是枯燥的主要涉及的内容：组合数学：博弈问题，群论，四色问题，也包括图论内容计算数学：高数中的很多东西矩阵论概率统计计算几何16几个有趣的问题：Nim取子游戏：桌上放着100个棋子，A,B二人轮流从中拿走1个或2个，A先拿，每次不能多拿也不能不拿，最后谁拿到最后一个棋子就是胜利者假设两人都很聪明，请问：谁会赢？17Nim取子A会赢：A先拿走一个，剩下99个然后每次B若拿1个 ，B就拿2个，B若拿2个，A就拿1个，这样两人一个回合加起来总是拿3个可见A一定能拿到最后一个棋子18其他数学问题概率统计：赌博时最优决策计算几何：平面、空间的计算组合数学：非常非常多的稀奇古怪的问题19其他当然，作为一个出色的ACM-ICPC选手，除了数据结构、算法、数学这些大的知识外，还