ACM所有算法总结

浙江林学院ACM集训队阶段总结,图论Whatisthat?,什么是图论?,图论GraphTheory是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。,并查集及其拓展,并查集是一种信息内聚很强的数据结构，它在判定图的连通性以及等价类划分的时空效率上有着不可替代的优势。但并查集的特殊应用也应该有所了解.以下两类是并查集在实际问题中的特殊拓展，希望大家能够进行快速掌握.1.集合计数问题2.二分图识别,集合计数问题,HDU1856Moreisbetter题意：若A与B认识，B与C认识，则A与C认识，现给你一组人员的关系表，求在这样的不同群组内，拥有最多人数群组的人数。,集合计数问题,有什么想法？并查后统计并查数组?不可行数据范围10000000如果逐个统计必定TLE不能如此暴力.思路如何想3分钟,集合计数问题,联想到并查集的构造原理构造rank数组,在并操作中入手！好,问题解决!,二分图识别,HDU1829ABugOfLife题意：假定两只飞虫(Bug)关系表，如AB表示A仰慕B，问是否存在同性的飞虫互相仰慕（也就是同性恋问题）.,二分图识别,难点：A与B的集合归属不定如何解决?思考！,二分图识别,非此即彼思想的运用构造数组opp，初始化为本身编号，若A与B有关，首先进行find(A),find(B)的操作，若根相同，则说明A与B属于同一集合，即同性恋，否则执行下面的操作，如果A的opp等于本身，说明A的opp未初始化，使之等于B，否则将A的opp与B进行Unition操作，类似的如果B的opp等于本身，说明B的opp未初始化，使之等于A，否则将B的opp与A进行Unition操作,二分图识别,想想为什么？二分图的性质决定更深入的二分识别(如统计最小单元集，如何进行_课后思考!),最短路径问题,在一个网络图中求解一点到另一点间最短距离及其路径的算法称之为最短路径问题。1、单源正权最短路径2、单源带负权最短路径3、多源最短路径,单源正权最短路径,求解单源最短路径的Dijkstra算法，状态转移与贪心准则的完美结合。思想：动态规划策略：贪心(O(Ve)步骤：1.构造辅助数组Dis,Vist,Disi表示从源点出发到达i点的最短距离,Visti表示i点是否已被访问，算法开始执行时令所有Disi=w(start,i)不可达为MAX,Viststart=true.2.每次得到Dis数组中最小且未被访问过的点i，标记Visti=true,遍历所有与i相关的边，若得到Disi+w(i,j)Disj，则更新Disj=Disi+w(i,j).3.如此循环直到所有点均被标记.,单源正权最短路径,Dijkstra的致命弱点：不能处理带负权的边思考：Why?问题出自贪心策略！若存在负权，则算法将不断更新负权边相关顶点的Dis值，从而导致答案错误!,单源带负权最短路径,如何处理Dijkstra的遗留问题？摈弃贪心策略执行松弛技术-Bellman-ford算法,单源带负权最短路径,什么是松弛技术？日常生活中的例子（1+1猜想）松弛技术的本质是首先给予一个物体很高的估价，在每次的迭代中对估价进行修正，在有限次的迭代后使估价与实际值吻合的技术。,单源带负权最短路径,思想：若存在N个点的网络，则对于起点到终点最多经过N-1条边策略：有限迭代下的松弛技术,单源带负权最短路径,步骤：1、开辟辅助数组Dis,记录源点到点i的最小距离，初始时设所有Dis值为MAX，Disstart=0.2、进行n-1次迭代，对于所有边，若满足Disix=(X*m)%n,中国剩余定理,设n=n1*n2.nk,其中因子两两互质.有:a-(a1,a2,.,ak),其中ai=amodni,则a和(a1,a2,.,ak),关系是一一对应的.就是说可以由a求出(a1,a2,.,ak),也可以由(a1,a2,.,ak)求出a求解：中国古代演算法模线性方程代入,中国剩余定理,应用大整数表示快速运算,连分数逼近,在数学中，连分数或繁分数即如上表达式.这里的a0是某个整数而所有其他的数an都是正整数。可依样定义出更长的表达式。如果部分分子（partialnumerator）和部分分母（partialdenominator）允许假定任意的值，在某些上下文中可以包含函数，则最终的表达式是广义连分数。在需要把上述标准形式与广义连分数相区别的时候，可称它为简单或正规连分数，或称为是规范形式的一个数的连分数表示是有限的，当且仅当这个数是有理数。“简单”有理数的连分数表示是简短的。任何有理数的连分数表示是唯一的，如果它没有尾随的1。（但是a0;a1,.an,1=a0;a1,.an+1。）无理数的连分数表示是唯一的。连分数的项将会重复，当且仅当它是一个二次无理数（即整数系数的二次方程的实数解）的连分数表示。数x的截断连分数表示很早产生x的在特定意义上“最佳可能”的有理数逼近。,连分数逼近,意义1、精度保留2、避免浮点运算3、无理数的表示唯一4、研究连分数的动机源于想要有实数在“数学上纯粹”的表示。求解欧几里德变体！,连分数逼近,数据结构Soul!,数据结构,什么是数据结构?数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解而有不同的表述方法：SartajSahni在他的数据结构、算法与应用一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（dataobject）定义为“一个数据对象是实例或值的集合”。CliffordA.Shaffer在数据结构与算法分析一书中的定义是：“数据结构是ADT（抽象数据类型AbstractDataType）的物理实现。”LobertL.Kruse在数据结构与程序设计一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。,数据结构,为什么要使用数据结构?1、便于理清结构，易于表示出一个实体的内部属性与外部联系。2、更好利用实体特性，从而为算法高效铺路。3、强有力的数据结构，能够取代算法的优势。,数据结构,数据结构的基本类型：1、顺序表2、链表3、广义表4、树5、图6、串,顺序表,顺序表是在内存上开辟的连续片段，每个元素单元拥有固定大小，以此组织形成的数据结构。优点：1、随机存取2、索引唯一3、结构简单,顺序表,一般应用：1、寄存数组（包括栈和队列）2、哈希数组3、树状数组,寄存数组,这是我们最常见的顺序表表现方式，一般的大数据量程序，如果不能有边读边处理的方法，就需要首先保留所有的输入，从而能够在而后的过程中进行处理。主要应用：1、各类算法的线性预处理2、保留线性逻辑关系3、记忆化辅助,寄存数组,优点：1、静态2、随机3、高效缺点：1、插入与删除操作效率极度低下2、内存分配不灵活技巧：1、满足递推与DP内存需求滚动数组2、满足图的快速判重化行为数状态压缩,哈希数组,什么是哈希？从广义上说哈希是一种键值对应的操作，是从数域到值域的一一映射，也就是我们通常称其为哈希函数的由来。为什么哈希表可以用数组实现？数组满足哈希的3个必要条件：1、键index2、值value3、键值映射（index-value）O（1）,哈希数组,散列函数的选用一般情况下我们使用哈希数组，采用的是开放散列策略，也就是说内存与键是一一对应，即hashkey=value,在对于key值要求不大的情况下是很好的选择。然而当要求的key很大时该怎么办，此时就应该选用一个好的映射函数使hashf(key)=value，且f(key)的值必定均匀分布在映射区间内。当然要找到这样的函数是十分困难的，我们无法了解到数据的具体信息，因此一般的f(key)为key%p，p为一个质数，结合数论知识，我们可以知道当gcd(key,p)=1时，key是一个循环群生成元，使用这个性质，我们可以少了许多因大多数冲突而引发避免策略造成的效率问题。,哈希数组,HDU2192题意：递增的序列组成一个集合请问至少有几个？思路？,哈希数组,出现次数最多的数，决定了能分成的最少群落！实现方式？哈希！散列函数如何刻画？思考！根据问题的输入规模，最大104个数，因此选取大于104的质数作为散列函数的参数，令f(key)=key%p还有什么问题？思考出现冲突！,哈希数组,解决方案：1、线性扫描法2、二次线性扫描3、桶链问题完美解决，注意各个结点在不同解决方案下添加的相关变量。,树状数组,首先我们得知道一个问题,那就是线段树的作用并不只是用来存储线段的,也可以存储点的值等等.对于静态的线段树,空间上需要的数组有:当前结点的数据值,左儿子编号,右儿子编号.至少这么三个数组.而在时间上虽然是NlogN的复杂度,但是系数很大.实现起来的时候编程复杂度大,空间复杂度大,时间效率也不是很理想.,有!,那就是树状数组!,那么是否有更好的解决方法呢?,树状数组,先看一个例题:数列操作:给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.,树状数组,如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上,用线段树可以这样解:,若要维护的序列范围是0.5,先构造下面的一棵线段树:,树状数组,可以看出,这棵树的构造用二分便可以实现.复杂度是2*N.每个结点用数组a来表示该结点所表示范围内的数据之和.修改一个位置上数字的值,就是修改一个叶子结点的值,而当程序由叶子结点返回根节点的同时顺便修改掉路径上的结点的a数组的值.对于询问的回答,可以直接查找i.j范围内的值,遇到分叉时就兵分两路,最后在合起来.也可以先找出0.i-1的值和0.j的值,两个值减一减就行了.后者的实际操作次数比前者小一些.这样修改与维护的复杂度是logN.询问的复杂度也是logN,对于M次询问,复杂度是MlogN.,树状数组,用树状数组!,然而不难发现,线段树的编程复杂度大,空间复杂度大,时间效率也不高.,怎么办,树状数组,下图中的C数组就是树状数组,a数组是原数组,先自己研究一下这个东西,树状数组,可以发现这些规律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5C8=a1+a2+a3+a4+a5+a6+a7+a8C2n=a1+a2+.+a2n,树状数组,对于序列a，我们设一个数组C定义Ci=ai2k+1+ai，k为i在二进制下末尾0的个数。K的计算可以这样:2k=xand(xxor(x-1)以6为例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2,树状数组,functionLowbit(x:Integer):Integer;beginLowbit:=xand(xxor(x1);end;若要修改ai的值,则C数组的修改是:Procedurechange(k,delta:integer);Beginwhilek0dobegint:=t+ck;k:=k-lowbit(k);end;getsum:=t;End;,树状数组,对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.在很多的情况下,线段树都可以用树状数组实现.凡是能用树状数组的一定能用线段树.当题目不满足减法原则的时候,就只能用线段树,不能用树状数组.例如数列操作如果让我们求出一段数字中最大或者最小的数字,就不能用树状数组了.,链表,链表是内存中不连续块链接而成的数据结构，本着使用多少分配多少的原则，极大地节约和利用了内存，是一种十分基础的数据结构。优势：1、动态分配2、快速删除与插入3、节省空间,链表,缺点：1、查找效率低下2、动态分配结点调用操作系统实现，导致空间分配效率消耗一种对空间的优化：内存静态化！一般应用1、桶2、跳跃表,桶,一般用做哈希的冲突避免策略，使用桶结构存储在同一冲突域下的数据，作为键值的扩展。基数数排序的辅助结构。,跳跃表,可以看做是链表结构最优秀的应用，使用跳跃表有着令人震撼的效率，对查询、删除和添加的操作均为O（logn）的复杂度。利用了链表自身的特点，以较小的空间代价提升了自身的性能。使用了概率算法，使效率堪与AVL、RB-Tree等BST相媲美。相比而言，极低的编程复杂度！有什么理由可以不去掌握呢？,跳跃表,跳跃表由多条链构成（S0，S1，S2，Sh），且满足如下三个条件：每条链必须包含两个特殊元素：+和-S0包含所有的元素，并且所有链中的元素按照升序排列。每条链中的元素集合必须包含于序数较小的链的元素集合，即：,跳跃表之查找,目的：在跳跃表中查找一个元素x在跳跃表中查找一个元素x，按照如下几个步骤进行：从最上层的链（Sh）的开头开始假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较x=y输出查询成功，输出相关信息xy从p向右移动到q的位置xy从p向下移动一格如果当前位置在最底层的链中（S0），且还要往下移动的话，则输出查询失败,查询元素53的全过程,S0,S1,S2,S3,查找成功！,跳跃表之插入,目的：在跳跃表中插入一个元素x插入操作由两部分组成：查找插入的位置和插入对应元素。为了确定插入的“列高”，我们引入一个随机决策模块：产生一个0到1的随机数rrrandom()如果r小于一个概率因子P，则执行方案A，ifrdist(right(A)，交换left(A)和right(A)最后，由于right(A)的距离可能发生改变，我们必须更新A的距离：dist(A)dist(right(A)+1不难验证，经这样合并后的树C符合性质1和性质2，因此是一棵左偏树。至此左偏树的合并就完成了。,左偏树,合并操作都是一直沿着两棵左偏树的最右路径进行的。一棵N个节点的左偏树，最右路径上最多有log(N+1)个节点。因此，合并操作的时间复杂度为：O(logN1+logN2)=O(logN)合并操作的代码如下：FunctionMerge(A,B)IfA=NULLThenreturnBIfB=NULLThenreturnAIfkey(B)dist(left(A)Thenswap(left(A),right(A)Ifright(A)=NULLThendist(A)0Elsedist(A)dist(right(A)+1returnAEndFunction,左偏树,左偏树的特点：时空效率高编程复杂度低左偏树的应用：可并堆优先队列,左偏树,HDU1512题意：刚开始所有的猴子自成一群且互相都不认识，他们互相认识当且仅当他们各自群中最强的猴子互相打了一场，体力各减为一半。问最后这群猴子中体力最强猴子的体力是多少思路如何？,左偏树,并查？可行，但只能作为辅助手段。优先队列+并查？O（nlogn）的合并效率实在不敢恭维很好。左偏树开始发挥了效力了！,左偏树,步骤：使用并查集（这里其实准确来说应该是一种记录父结点编号的数组）记录各结点在各自堆中的父结点查询两只猴子所在堆的根结点，如果两只猴子根结点相同，则不必打架，否则，取各自堆中最大元素（也就是根结点）打一场打架，此时先让各自堆中根的左右儿子指向本身，再对左右儿子进行合并生成新树（即pop操作）并适当修改父结点数组，令根结点值减半后与新树再次合并，并适时修改父结点数组（即push操作），再将两个堆中的根进行合并（即unition操作）。是不是很简单的实现？,斜堆,如何对左偏树进行优化？思考！我们注意到在左偏树中必须要有距离的概念，但我们可以发现一个性质，如果每次合并都向右进行，每次完成后将右边的结点甩到左边，不正好符合了左偏的性质么？很好去掉距离，提高效率，优化的王道！不足（单次合并可能退化到O(n)，但实际效果上，两者都差不多）,AC自动机,AC自动机是由Aho和Corasick提出的数据结构,是对Trie树的一种改造，是对find操作的修正，也是多模式串匹配的基本实现！HDU2222题意给你N个关键字,以及一句描述,问有多少个关键字在这句描述中出现?思路?,AC自动机,采用普通方法？O（Nnm）m=50,n=1000000,N=10000黄花菜都凉了KMP?O(N(m+n)?就这点优化？塞牙缝都不够那怎么办！AC自动机！O（Nm+n）强大！,AC自动机,步骤将所有关键字塞入Trie好了，现在我们已经有一棵Trie了，但这还不够，我们还要在Trie上引入一个很强大的东西：失败指针或者说shift数组或者说Next函数.你爱怎么叫怎么叫吧，反正就是KMP的精华所在，这也是我为什么叫你看KMP的原因。KMP中我们用两个指针i和j分别表示，Ai-j+1.i与B1.j完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以Ai结尾的长度为j的字符串正好匹配B串的前j个字符，当Ai+1Bj+1，KMP的策略是调整j的位置（减小j值）使得Ai-j+1.i与B1.j保持匹配且新的Bj+1恰好与Ai+1匹配（从而使得i和j能继续增加）。Trie树上的失败指针与此类似。,AC自动机,假设有一个节点k，他的失败指针指向j。那么k,j满足这个性质：设root到j的距离为n，则从k之上的第n个节点到k所组成的长度为n的单词，与从root到j所组成的单词相同。那么我们要怎样构建这个东西呢？其实我们可以用一个简单的BFS搞定这一切。对于每个节点，我们可以这样处理：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root最开始，我们把root加入队列(root的失败指针显然指向自己)，这以后我们每处理一个点，就把它的所有儿子加入队列，直到搞完。好了，现在我们有了一棵带失败指针的Trie了！可以开始进行AC自动机了！,AC自动机,一开始，Trie中有一个指针t1指向root，待匹配串(也就是“文章”)中有一个指针t2指向串头。接下来的操作和KMP很相似：如果t2指向的字母，是Trie树中，t1指向的节点的儿子，那么t2+1,t1改为那个儿子的编号，否则t1顺这当前节点的失败指针向上找，直到t2是t1的一个儿子，或者t1指向根。如果t1路过了一个绿色的点，那么以这个点结尾的单词就算出现过了。或者如果t1所在的点可以顺着失败指针走到一个绿色点，那么以那个绿点结尾的单词就算出现过了。本题要注意的是必须在描述串后面添加特殊符号，否则将忽略对完全匹配关键字的统计。注意：BFS寻找失败指针的过程，是一个自我匹配的过程。,AC自动机,特点：多模式匹配的良方，一次自我适配后，对任意文章的匹配均是线性复杂度。编程复杂度较低。使用方便，居家旅行之必备！,图,图的结构是树结构的拓展，但在实现基本以数组的形式进行，在本质上来说所有的数据结构都是互相渗透交融的，所谓大道行简，只有掌握了本质，才能以不变应万变！基本表示：邻接阵邻接表由于上部分内容已经有所涉猎，这里就不再提过了,串,什么是串？串是由字符所组成的有限序列，我们只关心串的字符属性，而不关心其数值属性。串有着十分明显的逻辑结构，前驱后继都是固定的，不得随意更改！关于字符串的处理一般而言都是ICPC的中档题目，如果使用模拟或者暴力方法，一般来说都是无效的。应用结构：后缀数组,后缀数组,什么是后缀数组？对于长度为len的字符串str，从位置i开始至len的所有字符序列称为i的后缀后缀数组（SA）保存的就是这些后缀序列的排序后的开头位置.Rank数组是SA的反函数，也就是说Ranki保存的是从位置i开始的后缀在所有后缀中的名次.,后缀数组,如何利用这种结构性质？我们还需要计算一个辅助的工具最长公共前缀（LongestCommonPrefix）!对两个字符串u,v定义函数lcp(u,v)=maxi|u=iv，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。对正整数i,j定义LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj)，其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。关于LCP有两个显而易见的性质：性质2.1LCP(i,j)=LCP(j,i)性质2.2LCP(i,i)=len(Suffix(SAi)=n-SAi+1这两个性质的用处在于，我们计算LCP(i,j)时只需要考虑ij时可交换i,j，i=j时可以直接输出结果n-SAi+1。,后缀数组,直接根据定义，用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的，时间复杂度为O(n)，所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。经过仔细分析，我们发现LCP函数有一个非常好的性质：设ij，则LCP(i,j)=minLCP(k-1,k)|i+1kj（LCPTheorem）根据LCPTheorem得出必然的一个推论：LCPCorollary对ij1，一定有hihi-1-1。根据性质3，可以令i从1循环到n按照如下方法依次算出hi：若Ranki=1，则hi=0。字符比较次数为0。若i=1或者hi-11，则直接将Suffix(i)和Suffix(Ranki-1)从第一个字符开始依次比较直到有字符不相同，由此计算出hi。字符比较次数为hi+1，不超过hi-hi-1+2。否则，说明i1，Ranki1，hi-11，根据性质3，Suffix(i)和Suffix(Ranki-1)至少有前hi-1-1个字符是相同的，于是字符比较可以从hi-1开始，直到某个字符不相同，由此计算出hi。字符比较次数为hi-hi-1+2。设SA1=p，那么不难看出总的字符比较次数不超过4N.也就是说，整个算法的复杂度为O(n)。求出了h数组，根据关系式heighti=hSAi可以在O(n)时间内求出height数组，于是可以在O(n)时间内求出height数组。,后缀数组,结