浙江林学院ACM集训队阶段总结课件教学教材

《浙江林学院ACM集训队阶段总结课件教学教材》由会员分享，可在线阅读，更多相关《浙江林学院ACM集训队阶段总结课件教学教材（152页珍藏版）》请在金锄头文库上搜索。

1、浙江林学院ACM集训队阶段总结,Write by Zhuangli(zjfc3),图论What is that?,什么是图论?,图论Graph Theory是数学的一个分支。它以图为研究对象。图论中的图是由若 干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系 。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。,并查集及其拓展,并查集是一种信息内聚很强的数据结构，它在判定图的连通性

2、以及等价类划分的时空效率上有着不可替代的优势。但并查集的特殊应用也应该有所了解. 以下两类是并查集在实际问题中的特殊拓展，希望大家能够进行快速掌握. 1.集合计数问题 2.二分图识别,集合计数问题,有什么想法？ 并查后统计并查数组? 不可行 数据范围10000000 如果逐个统计必定TLE 不能如此暴力. 思路如何想3分钟,集合计数问题,联想到并查集的构造原理 构造rank数组,在并操作中入手！ 好,问题解决!,二分图识别,HDU 1829 A Bug Of Life 题意： 假定两只飞虫(Bug)关系表，如A B表示A仰慕B，问是否存在同性的飞虫互相仰慕（也就是同性恋问题）.,二分图识别,难

3、点：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操作,二分图识别,想想为什么？ 二分图的性质决定 更深入的二分识别(如统计最小单元集，如何进行 _ 课后思考!),最短路径问题,在一个网络图中求解一点到另一

4、点间最短距离及其路径的算法称之为最短路径问题。 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，则更

5、新Disj=Disi+w(i ,j). 3.如此循环直到所有点均被标记.,单源正权最短路径,Dijkstra的致命弱点：不能处理带负权的边 思考：Why? 问题出自贪心策略！若存在负权，则算法将不断更新负权边相关顶点的Dis值，从而导致答案错误!,单源带负权最短路径,如何处理Dijkstra的遗留问题？ 摈弃贪心策略 执行松弛技术-Bellman-ford算法,单源带负权最短路径,什么是松弛技术？ 日常生活中的例子（1+1猜想） 松弛技术的本质是首先给予一个物体很高的估价，在每次的迭代中对估价进行修正，在有限次的迭代后使估价与实际值吻合的技术。,单源带负权最短路径,思想：若存在N个点的网络，则

6、对于起点到终点最多经过N-1条边 策略：有限迭代下的松弛技术,单源带负权最短路径,步骤： 1、开辟辅助数组Dis,记录源点到点i的最小距离，初始时设所有Dis值为MAX，Disstart=0. 2、进行n-1次迭代，对于所有边，若满足DisiMAX 迭代后令sum=sum%C;,GCD,GCD（最大公约数）的一般求解 欧几里德辗转相除法（必须掌握） If(a%b=0) return b; Else return gcd(b,a%b); 本过程具有收敛性质,扩展欧几里德,在一些具体的题目中，我们还需要的到一组满足ax+by=gcd(a,b)的最小解，用以判断模方程是否有解，此时就要使用扩展欧几里

7、德. 相比一般欧几里德方法，扩展欧几里德有一个对于X，Y求解的递推过程。使用递归实现，递归条件为b=0时，X=1,Y=0;否则t=X; X=Y; Y=t-(a/b)*X;(递推求得)可以证明最后出来的X，Y必然是最小解. 应用：模线性方程的求解,循环群生成元,对于mod n域中的任意数a，若有gcd(m,n)=1，则m为该域的生成元，使得a+km可以为域中任意数. 证明十分简单，若gcd(m,n)=1，则lcm(m,n)=m*n,则对于a的mod n运算,需要n次的计算才能回到a，期间必遍历该域中所有数！,因子分解,对于筛选大量数的因子分解工作，可以与筛选质数同时进行。 令leni记录数i的因

8、子个数，则对于每个素数p的倍数及本身，插入因子p，并使len值增长，筛选完所有素数后就完成了因子分解,素数判定,对于一千万内素数的判定： 筛选法最优 对于一千万外素数的判定： 米勒测试,筛选法,给定辅助bool数组prime，首先全置true,使prime0=prime1=false; 遍历，当遇到primei=true,将之小于n的所有倍数置false； 最后一次遍历，所有值为true的数即为素数！ 时空效率 均摊相关伪线性复杂度,米勒测试,理论基础费马定理 实践工具二分求幂,米勒测试,费马定理： 若p为素数-a(p-1)%p=1 注意此定理只为充分 不为必要 米勒测试以概率的形式避免了误判

9、的发生 从严格意义上来说米勒测试的意义并不科学 但是实际证明在可数范围内的伪素数十分之少 而且同时满足a=2,a=3,a=7的底的伪素数更是少得可怜，因此该测试从概率上满足了快速判定素数的需求。,米勒测试,二分快速求幂模原理 对于res=ab%c的求解 若b%2=0则res=(a(b/2)%c*(a(b/2)%c)%c 否则res=(a*(a(b/2)%c*(a(b/2)%c)%c,欧拉函数,设E(n)为n以内（不包括n）与n互质数的个数，则E(n)称为关于n的欧拉函数。 欧拉函数的求法，对于n=p1*p2*p3pn E(n)=n*(1-1/p1)*(1-1/p2)*(1-1/pn) 可以以容

10、斥原理证明其正确性！ 欧拉定理: a(E(n)%n=1,模线性方程求解,axb(mod n)有解，当且仅当b%gcd(a,n)=0 使用扩展欧几里德求得d=gcd(a,n),则aX+nY=d,x=(X*(b/d)%n Why? b/d=m a(X*m)+nY*m=b=x=(X*m)%n,中国剩余定理,设 n=n1*n2.nk, 其中因子两两互质.有: a-(a1,a2,.,ak), 其中ai = a mod ni, 则 a和(a1,a2,.,ak),关系是一一对应的.就是说可以由 a求出(a1,a2,.,ak), 也可以由(a1,a2,.,ak)求出a 求解： 中国古代演算法 模线性方程代入,

11、中国剩余定理,应用 大整数表示 快速运算,连分数逼近,在数学中，连分数或繁分数即如上表达式. 这里的 a0 是某个整数而所有其他的数 an 都是正整数。可依样定义出更长的表达式。如果部分分子（partial numerator）和部分分母（partial denominator）允许假定任意的值，在某些上下文中可以包含函数，则最终的表达式是广义连分数。在需要把上述标准形式与广义连分数相区别的时候，可称它为简单或正规连分数，或称为是规范形式的 一个数的连分数表示是有限的，当且仅当这个数是有理数。 “简单”有理数的连分数表示是简短的。 任何有理数的连分数表示是唯一的，如果它没有尾随的 1。（但是

12、a0; a1, . an, 1 = a0; a1, . an + 1。） 无理数的连分数表示是唯一的。 连分数的项将会重复，当且仅当它是一个二次无理数（即整数系数的二次方程的实数解）的连分数表示。 数 x 的截断连分数表示很早产生 x 的在特定意义上“最佳可能”的有理数逼近。,连分数逼近,意义 1、精度保留 2、避免浮点运算 3、无理数的表示唯一 4、研究连分数的动机源于想要有实数在“数学上纯粹”的表示。 求解 欧几里德变体！,连分数逼近,数据结构Soul !,数据结构,什么是数据结构? 数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。

13、数据结构往往同高效的检索算法和索引技术有关。 数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解而有不同的表述方法： Sartaj Sahni 在他的数据结构、算法与应用一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。 Clifford A.Shaffer 在数据结构与算法分析一书中的定义是：“数据结构是 ADT（抽象数据类型 Abstract Data Type） 的物理实现。” Lobert L.Kruse 在数据结构与程

14、序设计一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。,数据结构,为什么要使用数据结构? 1、便于理清结构，易于表示出一个实体的内部属性与外部联系。 2、更好利用实体特性，从而为算法高效铺路。 3、强有力的数据结构，能够取代算法的优势。,数据结构,数据结构的基本类型： 1、顺序表 2、链表 3、广义表 4、树 5、图 6、串,顺序表,顺序表是在内存上开辟的连续片段，每个元素单元拥有固定大小，以此组织形成的数据结构。 优点： 1、随机存取 2

15、、索引唯一 3、结构简单,顺序表,一般应用： 1、寄存数组（包括栈和队列） 2、哈希数组 3、树状数组,寄存数组,这是我们最常见的顺序表表现方式，一般的大数据量程序，如果不能有边读边处理的方法，就需要首先保留所有的输入，从而能够在而后的过程中进行处理。 主要应用： 1、各类算法的线性预处理 2、保留线性逻辑关系 3、记忆化辅助,寄存数组,优点： 1、静态 2、随机 3、高效 缺点： 1、插入与删除操作效率极度低下 2、内存分配不灵活 技巧： 1、满足递推与DP内存需求 滚动数组 2、满足图的快速判重 化行为数 状态压缩,哈希数组,什么是哈希？ 从广义上说哈希是一种键值对应的操作，是从数域到值域

16、的一一映射，也就是我们通常称其为哈希函数的由来。 为什么哈希表可以用数组实现？ 数组满足哈希的3个必要条件： 1、键index 2、值value 3、键值映射（index-value）O（1）,哈希数组,散列函数的选用 一般情况下我们使用哈希数组，采用的是开放散列策略，也就是说内存与键是一一对应，即hashkey=value,在对于key值要求不大的情况下是很好的选择。 然而当要求的key很大时该怎么办，此时就应该选用一个好的映射函数使hashf(key)=value，且f(key)的值必定均匀分布在映射区间内。当然要找到这样的函数是十分困难的，我们无法了解到数据的具体信息，因此一般的f(key)为key%p，p为一个质数，结合数论知识，我们可以知道当gcd(key,p)=1时，key是一个循环群生成元，使用这个性质，我们可以少了许多因大多数冲突而引发避免策略造成的效率问题。,哈希数组,HDU 2192 题意 ： 递增的序列组成一个集合 请问至少有几个？ 思路？,哈希数组,出现次数最