null浙江林学院
ACM集训队阶段
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
浙江林学院
ACM集训队阶段总结
Write by Zhuangli(zjfc3) 图论
What is that?图论
What is that?什么是图论?什么是图论?图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若 干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
事物，用连接两点的线表示相应两个事物间具有这种关系 。
图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。
并查集及其拓展并查集及其拓展并查集是一种信息内聚很强的数据结构，它在判定图的连通性以及等价类划分的时空效率上有着不可替代的优势。但并查集的特殊应用也应该有所了解.
以下两类是并查集在实际问题中的特殊拓展，希望大家能够进行快速掌握.
1.集合计数问题
2.二分图识别集合计数问题集合计数问题HDU 1856 More is better
题意：
若A与B认识，B与C认识，则A与C认识，现给你一组人员的关系表，求在这样的不同群组内，拥有最多人数群组的人数。集合计数问题集合计数问题有什么想法？
并查后统计并查数组?
不可行 数据范围10000000 如果逐个统计必定TLE 不能如此暴力….
思路如何……想3分钟集合计数问题集合计数问题
联想到并查集的构造原理
构造rank数组,在并操作中入手！！
好,问题解决!! 二分图识别二分图识别HDU 1829 A Bug Of Life
题意：
假定两只飞虫(Bug)关系表，如A B表示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[],Dis[i]表示从源点出发到达i点的最短距离,Vist[i]表示i点是否已被访问，算法开始执行时令所有Dis[i]=w(start,i)[不可达为MAX],Vist[start]=true.
2.每次得到Dis[]数组中最小且未被访问过的点i，标记Vist[i]=true,遍历所有与i相关的边，若得到Dis[i]+w(i,j)
=(或<=)C（常数）,以此为模型构成的约束系统，称之为差分约束系统。差分约束初步差分约束初步首先我们回顾下松弛技术，在Bellman-Ford算法中，有一个十分关键的三角不等式Dis[i]+w(i,j)=（或<=）C，我们取<=情况研究,则要求xi-xj<=C，即xi<=xj+C!! 看出什么了么？
对！这就是以j为始点，i为末点，C为权，构造出带约束边的图，并以此求得最短路径的算法啊！数与图得到了完美的结合！！最大流问题最大流问题在带源点与汇点的带权连通网络G中，求得自源点出发，受各边容量限制最后到达汇点的流量的问题，称之为最大流问题。
最大流网络满足3大性质：
流守恒性 网络内流不增加不减少
容量限制 流量受边负载限制
反对称性 任意结点 流进多少 流出多少
解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
：FF方法Ford-Fulkerson方法Ford-Fulkerson方法这是种方法而非算法，在此种方法指导下的算法最坏上界完全相同，但最好下界却各有千秋。
增广路径：在残留网络中，从源点出发，可以通过该路径使得所经边残余流量减少，而通向汇点的流量增大。
最小割-最大流定理：网络流中，存在的最大流受限制于该网络的最小割。
E-K算法，此算法是最常用的最大流算法，以BFS为基础，每次选择残余网络中的结点数最少的可增广路径进行增广，直到无法进行下去，此算法的最大特点是最后一次保存的路径是该网络流的最小截集。二分匹配二分匹配对于图G，可以将顶点重构为两个集合，每个集合内的点不自交，则该图称之为二部图，对其求解最大匹配的过程称之为二分匹配。在普通二分匹配中，其最小路径覆盖为点数-最大匹配数。
不带权二分匹配（匈牙利算法）
带权二分匹配（KM算法）匈牙利算法匈牙利算法由匈牙利数学家提出的解决二分图匹配的算法。
本质是找增广路径。这里的增广路径定义为交错轨，即一端为已匹配点，另一端为未匹配点，如果通过任意顶点的遍历，能够找到这样的路径，则对其取反,必会使匹配数+1，如此迭代直到无法找到这样的路径为止。
对最大匹配的题目一般以最小路径覆盖的形式出现。KM算法KM算法 KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B [i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终 成立。KM算法的正确性基于以下定理：
若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。
算法的本质是对匈牙利算法的改进，但实际上却比匈牙利算法早发表几年，其核心仍然是寻找增广路径的过程。KM算法KM算法步骤
初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：
两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。
现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。
理解原理就行，在一般情况下KM算法的代码不会调整，因此只要会使用模版，一切不在话下，当然图论本身就是充满了建模的思想，只有好的模型才能有真正的效率！KM算法KM算法
效率 O（V*V*V）
KM算法的本质，对于N*N的矩阵每行每列只能取一个数，使其和为最大！！强连通分支强连通分支什么是强连通分支？
强连通分支就是任意两点均可达的有向子图。
理论：白色路径定理
求解：Tarjan算法强连通分支强连通分支什么是时间戳？
DFS进行时，访问到节点所花的时间
算法理论依据：DFS时，如果所达的下一个点i已经被访问，则从该点j出发，寻找父节点到i，其间所经过的所有点必为以i为代表的强连通分支上的点(并查实现)
如何判断是否是该次被访问？时间戳！强连通分支强连通分支步骤
对于每个顶点，设立Num、Low、Used、Alive四个属性，一个Stack保存当前正在被遍历的顶点；
每访问一个顶点，将它的Num和Low设立为当前时间戳，Used、Alive设为True，并将顶点入栈；
对于它的每条边，若边的终点未Used，则访问，而后用终点的Low值更新它的Low值，对于每个Used且Alive的终点，用它的Num值更新当前值；
访问完毕当前顶点后，若Low与Num相等，说明找到了一个强连通分量，它包括栈中所有在当前顶点上方的顶点，将它们出栈并记下Belong值，出栈的顶点的Alive要置为false。
扫描各点Belong值，其代表的点的个数便为强连通分支数！
强连通分支强连通分支应用
1、求解单纯问题 HDU 1269
2、缩图技术 (适用于多点多边的关系闭包求解)待研究的问题待研究的问题
次小生成树
最优比例生成树
最小树型图
弦图
稳定婚姻问题数论
It’s easy to learn!数论
It’s easy to learn!数论数论什么是数论？
数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以及数论函数等内容，统称初等数论（elementary number theory）。
初等数论的大部份内容早在古希腊欧几里德的《 几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法， 即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
中的「中国剩余定理」正是我国古代《孙子算经》中的下卷第26题，我国称之为 「孙子定理」。
近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。高斯还提出：「数学是科学的皇后，数论是数学中的皇冠」。可见高斯对数论的高度评价。
由于自20世纪以来引进了抽象数学和高等分析的 巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。
同余定理同余定理对于正整数a,b,c
(a%c+b%c)%c=(a+b)%c
(a*b)%c=(a%c*b%c)%c
注意对于除法与减法%运算为非封闭运算 需要进行数论变换才能继续进行下去同余定理同余定理大数求余
设大数R=a1*10^0+a2*10^1+….+an*10^n-1
则R%C=(a1*10^0%C+a2*10^1%C+….+an*10^n-1%C)%C
可以在O（logn）时间内解决大数求余问题
步骤：
以字符读入大数后，设置计数器sum=0
sum=(10*sum+key[i]-’0’)%C;
迭代后令sum=sum%C;GCDGCDGCD（最大公约数）的一般求解
欧几里德辗转相除法（必须掌握）
If(a%b==0) return b;
Else return gcd(b,a%b);
本过程具有收敛性质……扩展欧几里德扩展欧几里德在一些具体的题目中，我们还需要的到一组满足ax+by=gcd(a,b)的最小解，用以判断模方程是否有解，此时就要使用扩展欧几里德.
相比一般欧几里德方法，扩展欧几里德有一个对于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，期间必遍历该域中所有数！因子分解因子分解对于筛选大量数的因子分解工作，可以与筛选质数同时进行。
令len[i]记录数i的因子个数，则对于每个素数p的倍数及本身，插入因子p，并使len值增长，筛选完所有素数后就完成了因子分解素数判定素数判定对于一千万内素数的判定：
筛选法最优
对于一千万外素数的判定：
米勒测试筛选法筛选法给定辅助bool数组prime，首先全置true,使prime[0]=prime[1]=false;
遍历，当遇到prime[i]=true,将之小于n的所有倍数置false；
最后一次遍历，所有值为true的数即为素数！
时空效率 均摊相关伪线性复杂度米勒测试米勒测试
理论基础——费马定理
实践工具——二分求幂米勒测试米勒测试费马定理：
若p为素数----a^(p-1)%p==1
注意此定理只为充分 不为必要
米勒测试以概率的形式避免了误判的发生 从严格意义上来说米勒测试的意义并不科学 但是实际证明在可数范围内的伪素数十分之少 而且同时满足a=2,a=3,a=7的底的伪素数更是少得可怜，因此该测试从概率上满足了快速判定素数的需求。米勒测试米勒测试二分快速求幂模原理
对于res=a^b%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*p3…pn
E(n)=n*(1-1/p1)*(1-1/p2)…*(1-1/pn)
可以以容斥原理证明其正确性！
欧拉定理: a^(E(n))%n==1模线性方程求解模线性方程求解ax≡b(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
求解：
中国古代演算法
模线性方程代入中国剩余定理中国剩余定理应用
大整数表示
快速运算连分数逼近连分数逼近在数学中，连分数或繁分数即如上表达式.
这里的 a0 是某个整数而所有其他的数 an 都是正整数。可依样定义出更长的表达式。如果部分分子（partial numerator）和部分分母（partial denominator）允许假定任意的值，在某些上下文中可以包含函数，则最终的表达式是广义连分数。在需要把上述标准形式与广义连分数相区别的时候，可称它为简单或正规连分数，或称为是
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
形式的
一个数的连分数表示是有限的，当且仅当这个数是有理数。
“简单”有理数的连分数表示是简短的。
任何有理数的连分数表示是唯一的，如果它没有尾随的 1。（但是 [a0; a1, ... an, 1] = [a0; a1, ... an + 1]。）
无理数的连分数表示是唯一的。
连分数的项将会重复，当且仅当它是一个二次无理数（即整数系数的二次方程的实数解）的连分数表示。
数 x 的截断连分数表示很早产生 x 的在特定意义上“最佳可能”的有理数逼近。 连分数逼近连分数逼近意义
1、精度保留
2、避免浮点运算
3、无理数的表示唯一
4、研究连分数的动机源于想要有实数在“数学上纯粹”的表示。
求解
欧几里德变体！！连分数逼近连分数逼近 数据结构
Soul !!!数据结构
Soul !!!数据结构数据结构什么是数据结构?
数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。
数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解而有不同的表述方法：
Sartaj Sahni 在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。
Clifford A.Shaffer 在《数据结构与算法分析》一书中的定义是：“数据结构是 ADT（抽象数据类型 Abstract Data Type） 的物理实现。”
Lobert L.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、键——index
2、值——value
3、键值映射（index->value）O（1）
哈希数组哈希数组散列函数的选用
一般情况下我们使用哈希数组，采用的是开放散列策略，也就是说内存与键是一一对应，即hash[key]=value,在对于key值要求不大的情况下是很好的选择。
然而当要求的key很大时该怎么办，此时就应该选用一个好的映射函数使hash[f(key)]=value，且f(key)的值必定均匀分布在映射区间内。当然要找到这样的函数是十分困难的，我们无法了解到数据的具体信息，因此一般的f(key)为key%p，p为一个质数，结合数论知识，我们可以知道当gcd(key,p)=1时，key是一个循环群生成元，使用这个性质，我们可以少了许多因大多数冲突而引发避免策略造成的效率问题。哈希数组哈希数组HDU 2192
题意 ：
递增的序列组成一个集合 请问至少有几个？
思路？哈希数组哈希数组出现次数最多的数，决定了能分成的最少群落！
实现方式？？
哈希！！！
散列函数——如何刻画？思考！
根据问题的输入规模，最大10^4个数，因此选取大于10^4的质数作为散列函数的参数，令f(key)=key%p
还有什么问题？思考
出现冲突！！！！哈希数组哈希数组解决方案：
1、线性扫描法
2、二次线性扫描
3、桶链
问题完美解决，注意各个结点在不同解决方案下添加的相关变量。树状数组树状数组首先我们得知道一个问题,那就是线段树的作用并不只是用来存储线段的,也可以存储点的值等等.
对于静态的线段树,空间上需要的数组有:当前结点的数据值,左儿子编号,右儿子编号.至少这么三个数组.
而在时间上虽然是NlogN的复杂度,但是系数很大.
实现起来的时候编程复杂度大,空间复杂度大,时间效率也不是很理想.
null有!那就是树状数组!那么是否有更好的解决方法呢?树状数组树状数组先看一个例题:
数列操作:
给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.
树状数组树状数组如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上
null用线段树可以这样解:若要维护的序列范围是0..5,先构造下面的一棵线段树:树状数组树状数组可以看出,这棵树的构造用二分便可以实现.复杂度是2*N.
每个结点用数组a来表示该结点所表示范围内的数据之和.
修改一个位置上数字的值,就是修改一个叶子结点的值,而当程序由叶子结点返回根节点的同时顺便修改掉路径上的结点的a数组的值.
对于询问的回答,可以直接查找i..j范围内的值,遇到分叉时就兵分两路,最后在合起来.也可以先找出0..i-1的值和0..j的值,两个值减一减就行了.后者的实际操作次数比前者小一些.
这样修改与维护的复杂度是logN.询问的复杂度也是logN,对于M次询问,复杂度是MlogN.
树状数组树状数组用树状数组!!!然而不难发现,线段树的编程复杂度大,空间复杂度大,时间效率也不高.树状数组树状数组下图中的C数组就是树状数组,a数组是原数组先自己研究一下这个东西树状数组树状数组可以发现这些规律
C1=a1
C2=a1+a2
C3=a3
C4=a1+a2+a3+a4
C5=a5
……
C8=a1+a2+a3+a4+a5+a6+a7+a8
……
C2^n=a1+a2+….+a2^n
树状数组树状数组对于序列a，我们设一个数组C定义C[i] = a[i – 2^k + 1] + … + a[i]，k为i在二进制下末尾0的个数。
K的计算可以这样:
2^k=x and (x xor (x-1))
以6为例
(6)10=(0110)2
xor 6-1=(5)10=(0101)2
(0011)2
and (6)10=(0110)2
(0010)2
树状数组树状数组function Lowbit(x: Integer): Integer;
begin
Lowbit := x and (x xor (x – 1));
end;
若要修改a[i]的值,则C数组的修改
是:
Procedure change(k,delta:integer);
Begin
while k<=n do
begin
C[k]:=C[k]+delta;
k:=k+lowbit(k);
End;
End;
树状数组树状数组若要求I..j的元素和的值,则求出
1..I-1的值和1..j的值.
Function getsum(k:integer):integer;
Var t:integer;
Begin
t:=0;
while k>0 do
begin
t:=t+c[k];
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 输出查询成功，输出相关信息
x>y 从p向右移动到q的位置
x dist(right(A))，交换left(A) 和right(A)
最后，由于right(A) 的距离可能发生改变，我们必须更新A的距离：
dist(A) ← dist(right(A)) + 1
不难验证，经这样合并后的树C符合性质1和性质2，因此是一棵左偏树。至此左偏树的合并就完成了。左偏树左偏树合并操作都是一直沿着两棵左偏树的最右路径进行的。
一棵N个节点的左偏树，最右路径上最多有 log(N+1) 个节点。
因此，合并操作的时间复杂度为： O(log N1 + log N2) = O(log N)
合并操作的代码如下：
Function Merge(A, B)
If A = NULL Then return B
If B = NULL Then return A
If key(B) < key(A) Then swap(A, B)
right(A) ← Merge(right(A), B)
If dist(right(A)) > dist(left(A)) Then
swap(left(A), right(A))
If right(A) = NULL Then dist(A) ← 0
Else dist(A) ← dist(right(A)) + 1
return A
End Function
左偏树左偏树左偏树的特点：
时空效率高
编程复杂度低
左偏树的应用：
可并堆
优先队列左偏树左偏树HDU 1512
题意：
刚开始所有的猴子自成一群且互相都不认识，他们互相认识当且仅当他们各自群中最强的猴子互相打了一场，体力各减为一半。问最后这群猴子中体力最强猴子的体力是多少
思路如何？左偏树左偏树并查？
可行，但只能作为辅助手段。
优先队列+并查？
O（nlogn）的合并效率实在不敢恭维
很好。。。左偏树开始发挥了效力了！左偏树左偏树步骤：
使用并查集（这里其实准确来说应该是一种记录父结点编号的数组）记录各结点在各自堆中的父结点
查询两只猴子所在堆的根结点，如果两只猴子根结点相同，则不必打架，否则，取各自堆中最大元素（也就是根结点）打一场打架，此时先让各自堆中根的左右儿子指向本身，再对左右儿子进行合并生成新树（即pop操作）并适当修改父结点数组，令根结点值减半后与新树再次合并，并适时修改父结点数组（即push操作），再将两个堆中的根进行合并（即unition操作）。
是不是很简单的实现？斜堆斜堆如何对左偏树进行优化？
思考！！！
我们注意到在左偏树中必须要有距离的概念，但我们可以发现一个性质，如果每次合并都向右进行，每次完成后将右边的结点甩到左边，不正好符合了左偏的性质么？
很好去掉距离，提高效率，优化的王道！
不足（单次合并可能退化到O(n)，但实际效果上，两者都差不多）AC自动机AC自动机AC自动机是由Aho和Corasick提出的数据结构,是对Trie树的一种改造，是对find操作的修正，也是多模式串匹配的基本实现！
HDU 2222
题意
给你N个关键字,以及一句描述,问有多少个关键字在这句描述中出现?
思路???
AC自动机AC自动机采用普通方法？
O（Nnm）…
m=50,n=1000000,N=10000
黄花菜都凉了……
KMP?
O(N(m+n))?
就这点优化？塞牙缝都不够
那怎么办！！！
AC自动机！！
O（Nm+n）…强大！！！
AC自动机AC自动机步骤
将所有关键字塞入Trie
好了，现在我们已经有一棵Trie了，但这还不够，我们还要在Trie上引入一个很强大的东西：失败指针或者说shift数组或者说Next函数 …..你爱怎么叫怎么叫吧，反正就是KMP的精华所在，这也是我为什么叫你看KMP的原因。
KMP中我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符，当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。
Trie树上的失败指针与此类似。
AC自动机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自动机AC自动机一开始，Trie中有一个指针t1指向root，待匹配串(也就是“文章”)中有一个指针t2指向串头。
接下来的操作和KMP很相似：如果t2指向的字母，是Trie树中，t1指向的节点的儿子，那么t2+1,t1改为那个儿子的编号，否则t1顺这当前节点的失败指针向上找，直到t2是t1的一个儿子，或者t1指向根。如果t1路过了一个绿色的点，那么以这个点结尾的单词就算出现过了。或者如果t1所在的点可以顺着失败指针走到一个绿色点，那么以那个绿点结尾的单词就算出现过了。
本题要注意的是必须在描述串后面添加特殊符号，否则将忽略对完全匹配关键字的统计。
注意：BFS寻找失败指针的过程，是一个自我匹配的过程。AC自动机AC自动机特点：
多模式匹配的良方，一次自我适配后，对任意文章的匹配均是线性复杂度。
编程复杂度较低。
使用方便，居家旅行之必备！图图图的结构是树结构的拓展，但在实现基本以数组的形式进行，在本质上来说所有的数据结构都是互相渗透交融的，所谓大道行简，只有掌握了本质，才能以不变应万变！！！
基本表示：
邻接阵
邻接表
由于上部分内容已经有所涉猎，这里就不再提过了串串什么是串？
串是由字符所组成的有限序列，我们只关心串的字符属性，而不关心其数值属性。
串有着十分明显的逻辑结构，前驱后继都是固定的，不得随意更改！
关于字符串的处理一般而言都是ICPC的中档题目，如果使用模拟或者暴力方法，一般来说都是无效的。
应用结构：
后缀数组后缀数组后缀数组什么是后缀数组？
对于长度为len的字符串str，从位置i开始至len的所有字符序列称为i的后缀
后缀数组（SA）保存的就是这些后缀序列的排序后的开头位置.
Rank数组是SA的反函数，也就是说Rank[i]保存的是从位置i开始的后缀在所有后缀中的名次.后缀数组后缀数组如何利用这种结构性质？
我们还需要计算一个辅助的工具——最长公共前缀（Longest Common Prefix）!!
对两个字符串u,v 定义函数lcp(u,v)=max{i|u=iv}，也就是从头开始顺次比较u 和v 的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。
对正整数i,j 定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中
浙公网安备 33021202002483