acm常用算法

1,常用算法 &数据结构,浙江大学微软技术俱乐部 彭鹏,ACM竞赛,2,2、竞赛中常见的16种题型,1、ACM/ICPC简介,4、竞赛中基本的数据结构与算法,5、ZOJ入门,3、时空复杂度的分析,3,ACM Association for Computing Machinery 美国计算机学会 ICPC International Collegiate Programming Contest 国际大学生程序设计竞赛,ACM/ICPC简介,4,ACM,ACM (Association for Computing Machinery) 成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织，是推进信息技术专业人员和学生提高技巧的主要力量。ACM通过提供前沿技术信息和从理论到实践的转化，为其全球7.5万名成员服务，并已经成为信息科技领域的一个基本信息来源。,5,ICPC,ACM主办的国际大学生程序设计竞赛 (International Collegiate Programming Contest)，简称ACM / ICPC，自从1977年开始至今已经连续举办28届。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，并成为一个有效的途径，让下一代IT天才可以接触到其日后工作中将要用到的各种软件。 自1998年IBM成为该项竞赛的赞助商以来，大赛规模不断扩大。去年有71个国家1582所大学派出4109支队伍参加了30个赛点的分区赛，其中78支队伍参加今年4月在上海香格里拉酒店举办的世界总决赛。 现在，ACM / ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。,6,ICPC竞赛规则,三人组队 在46小时 编写C/C+或Java程序 解决610道题 完成题目数多的队伍优胜 完成题目数一样的队伍, 罚时少的优胜,7,ICPC log,A problem A thought A solution A balloon,8,中国各高校ACM开展情况,清华大学 上海交通大学,中山大学 复旦大学,北京大学 南京大学,浙江大学,9,浙江大学ACM集训队选拔标准,根据校内程序设计竞赛的结果，现拟定集训队具体选拔标准如下： 1. 曾参加过去年暑假集训的队员自愿入围； 未参加过集训，但满足下列条件者自愿入围： 2. 对ACM ICPC活动有极大热情，视练习题如游戏；并且 3. 校内程序设计竞赛前5名；或者 4. 校内程序设计竞赛第6-9名，并且7月1日前在ZOJ通过至少100 题；或者 5. 校内程序设计竞赛第10-15名，并且7月1日前在ZOJ通过至少 150题；或者 6. 7月1日前在ZOJ通过至少200题。,10,如何建立一支强队,个人的能力 理论(几何, 数论, 动态规划, 图论等) 技术(编程) 队员能力上的互补,某论坛，一无聊男yy的中国“梦之队” 钱文杰（？） 反应奇快，擅长随机化，贪心，NOI贪心王 刘汝佳or吴嘉之 见多识广，做过的题必别人见过的题多 赵爽 上海交大的“割题手”,11,Leader/Coordinato(协调比赛进程) Reader(发现题目隐讳的涵义) Thinker(逻辑能力强, 收集其他队员意见) Programmer/Debugger(反应快/稳,细心) Helper(协助比赛, 查错, 验证数据等),一支强队需要的角色,12,参考书籍,主要参考书籍 C+ Primer C+ 标准程序库 算法导论 算法艺术与信息学竞赛 组合数学 计算几何？ 历届国家集训队论文,13,网络资源,http:/acm.zju.edu.cn http:/acm.timus.ru http:/acm.sgu.ru http:/ace.delos.com/usacogate http:/www.google.com http:/www.oibh.org/bbs/index.php,14,时空复杂度的分析,时间复杂度的分析,空间复杂度的分析,15,函数增长和运行时间,16,常见题型,Dynamic Programming(动态规划) Greedy(贪心) Complete Search(穷举) Flood Fill (种子填充),17,常见题型,Shortest Path (最短路径) Recursive Search Techniques (回溯） Minimum Spanning Tree （最小生成树） Knapsack（背包）,18,常见题型,Computational Geometry(计算几何) Network Flow(网络流) Eulerian Path (欧拉回路) Two-Dimensional Convex Hull (二维凸包),19,常见题型,BigNums (大数) Heuristic Search(启发式搜索) Approximate Search (近似搜索) Ad Hoc Problems(杂题),20,21,枚举法,又叫穷举法，它利用了计算机计算速度快且准确的特点，是最为朴素和有效的一种算法。,不是办法的办法,但有时却是最好的办法,22,Pizza Anyone? （ZOJ 1219）,题目大意： 你需要为你和你的朋友们订一个皮萨。每个朋友都会告诉你他们想和不想放进皮萨里的东西。 你是否能订一个皮萨，让他满足每个人至少一个条件。 假设一共有16种东西可以放进皮萨。,23,24,贪心法(Greedy),矩阵胚理论（详情请参考算法导论）,枚举法的时间效率很低，贪心法恰恰与其相反。并且贪心法的程序也很好实现。,无数论文都指责贪心法往往得不到问题的最优解。,绝世高手与普通高手的差距所在。,25,栈和队列,栈：后进先出（LIFO） 队列：先进先出（FIFO）,26,字符串的输入与输出, 或 ,char s100;scanf(“%s“,s); string a(s);,String a; cin a;,C+常用头文件,字符串的读入,27,排序,排序的种类： 交换排序，选择排序，插入排序，堆排序 希尔排序，快速排序，归并排序，桶排序,28,用C+实现排序,#include 数组 a sort( a , a + 5 ); vector a sort( a. begin() , a. end() );,29,并查集,并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。,并查集的主要操作有,1合并两个不相交集合,2判断两个元素是否属于同一个集合,3路径压缩,30,Parity(ceoi99),有一个01序列,长度=1000000000,现在有n条信息,每条信息的形式是a b even/odd。表示第a位到第b位元素之间的元素总和是偶数/奇数。 你的任务是对于这些给定的信息，输出第一个不正确的信息所在位置-1。信息的数目不超过5000。 如果信息全部正确，即可以找到一个满足要求的01序列，那么输出n。,31,Parity(ceoi99),从整个01序列肯定是无法入手的，因为它的长度高达109。 从范围比较小的n入手。也就是说我们需要对信息进行一些特殊的处理。 a b even/odd，那么将元素b指向a-1，边的权值是even/odd。 下面我们由样例来说明一下这个处理方法。,32,Parity(ceoi99)（肖天）,建立sum数组，sumi表示从1到i之和是奇（true）还是偶（false），sum0=false。这样题目中给的任意问题（a,b）的答案都可以用sumb xor suma-1表示。 开始我们并不知道sum1n的值，不妨设为false，这时任意suma,sumb都是独立的。对于每对问答(a,b,c)，都可以知道sumb xor suma-1=c,由此把sumb和suma-1联系起来。这步操作可以用并查集完成，对于问答（a,b,c）如果suma-1,sumb不属于一个集合就把它们并起来，否则如果suma-1 xor sumb不等于c则说明出现矛盾，输出总句数，退出。 对于不出现矛盾的sum数组，对于每个集合分为两个部分，我们指定其中一个部分为true，另一个部分为false，则可以确定sum数组，利用sumi xor sumi-1可以求出第i位的数字，由于不同集合之间没有问答出现，所以此数列是一可行解，证明算法正确。,33,堆(优先队列),优点：,实现简单,动态维护一组数据中最小（大）的一个,数组维护,34,例题: 积水,一个长方形网格包含了n*m块地，每块地上面有1个长方体。每一个长方形盖住了一块地，地的面积是1平方英寸。相邻的地上的长方体之间没有空隙。一场大雨降临了这个建筑物，在建筑物的某些区域有积水产生。 给各方格高度, 求积水总量,35,分析,定义每块地上的 长方体的高度称为原始高度 积满水时的水面高度称为积水高度（高于积水高度的水一定会流走，低于积水高度的水一定流不走） 积水高度与原始高度之差为积水深度 如果一个长方体上不可能有积水，那么它的积水高度就等于它的原始高度。 最外圈不能积水，积水高度等于原始高度,36,分析,由外而内计算。每次选取外围的格子中积水高度最低的一个格子x，考虑它周围所有在网格内部的格子y 想象不断的往x和y里注水，但是x的积水高度固定（想象该高度处有一个小孔），因此 如果y的原始高度不小于x的积水高度，那么它的积水高度就是它的原始高度 如果y的原始高度小于x的积水高度，那么它的积水高度就等于x的积水高度 每次用堆取出x进行计算，O(mnlogmn)。,37,哈希表(Hash),理论上查找速度最快的数据结构之一 缺点： 需要大量的内存 需要构造Key,38,Hash表的实现,数组 冲突解决法 开散列法 闭散列法 C+ sgi stl 实现,39,Hash Key的选取,数值： 方法一：直接取余数（一般选取质数M最为除数） 方法二：平方取中法，即计算关键值的平方，再取中间r位形成一个大小为 的表,40,字符串：,int ELFhash( char* key ) unsigned int h = 0; while( *key ) h = ( h 24; h ,方法二：ELFhash函数,方法一： 折叠法：即把所有字符的ASCII码加起来,41,二分搜索树,普通的二分搜索树,时间复杂度：,缺点：,容易出现不平衡的情况,AVL Tree ， Splay tree , 红黑树,42,树堆(Treap),Treap = Tree + heap,每次插入/删除结点的时候，给结点随机分配一个优先级，让Treap关于优先级形成一个堆的同时，关于关键码形成BST,跳跃表、B树,43,跳跃表（Skiplists）,44,线段树,在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。,45,46,Atlantis （ZOJ 1128）,一个平面被很多矩形覆盖，矩形之间会相互叠加。输出矩形覆盖的总面积。,47,Atlantis （ZOJ 1128）,线段树 矩形切割,48,矩形切割,49,字典树( Trie ),当关键字是串的时候，理论上查找最快的数据结构,定义：保存字符串用的树型数据结构(多叉树），其中每个节点表示一个公共前缀，单词信息保存在相应的页节点里面。,50,给如下几个单词，构造的单词树： An，Ant，All，Allot Alloy，Aloe，Are，Ate be,版权归浙江大学ACM领队徐串所有 转载需保留此字样,51,T9（ZOJ 1038）,题目描述：手机有智能英文输入法，他根据自己已有的词汇表，即使你每个数字只按一次也可以猜出你要按的是