《数据结构(noip)》由会员分享，可在线阅读，更多相关《数据结构(noip)（83页珍藏版）》请在金锄头文库上搜索。
1、数据结构专题赖国堃福建师大附中提纲简单数据结构的变种与高级应用栈队列高级数据结构入门并查集堆散列表（Hash表）栈特性：后进先出(LIFO)逻辑结构：只在一端操作的线性表进栈push出栈pop数组实现：元素 intstacksize栈顶指针 top栈的基本运算(1)入栈： Push(s，x)初始条件：栈s已存在 操作结果：在栈s的顶部插入一个新元素x， x成为新的栈顶元素。栈发生变化。push(s,x)top+;stop=x;return;栈的基本运算(2)出栈：Pop(s)初始条件：栈s存在且非空操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。Pos(s)if(top=0)
2、return;top-;return;音乐会的等待音乐会的等待 问题描述：问题描述：N个人排队，队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。计算出有多少对人可以互相看见。输入格式：输入格式：第一行包含一个整数N(1N500000),表示队伍中共有N个人。接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10-9米)为单位样例：样例：input72412251output10音乐会的等待针对序列8,8,6,4,2,3,7考虑前5人：音乐会的等待加入第6个人之后显然第6人可以看见3,4,5并且可以保证4，5不被6之后的人看见音乐会的等待
3、4，5不被6之后的人看见，将这种没希望被后面的人看见的人记为灰色音乐会的等待再加入第7位音乐会的等待显然3，6要被标上灰色音乐会的等待我们可以发现每次插入后，剩下的兰色标记序列是非递增的；每次插入前，标上灰色的人一定是兰色序列的最后几个。这让我们想起了一个常用的数据结构：栈栈这个栈是具备非递增特性的。音乐会的等待如何统计？第6位插入栈之前，可以看见3,4,5，并且4,5矮于第6位；所以元素在入栈之前，统计栈顶比他矮的人和恰比他高的人的人数就是这个人向前看向前看能看到的人数！ 音乐会的等待统计完，把栈顶比他矮的人（没希望的人）弹掉。（实际上我们可以一边统计一边弹）接着自己入栈。 音乐会的等待特别
4、地，恰比他高的人的人数大于1时我们不能把恰比他高的人给弹出栈，这样做就会统计错误；但若一一保存，统计起来就浪费时间。解决办法加权加权记录栈中相同身高的人数，就减少统计量。音乐会的等待由平摊分析得每个人进栈一次，出栈最多一次。所以时间复杂度为O(n).constmaxn=500000;varn,i,k,p,t:longint;push,num:array0.maxnoflongint;ans:int64;beginreadln(n);readln(k);p:=1;ans:=0;push1:=k;num1:=1;push0:=maxlongint;num0:=0;fori:=2tondobegin
5、readln(k);ifkpushpthenbegininc(ans);inc(p);pushp:=k;nump:=1;endinput 7 2 4 1 2 2 5 1 output 10elsebegint:=0;whilepushp=kdobegininc(t,nump);dec(p);end;ifp0theninc(t,1);inc(p);ifpushp=ktheninc(nump)elsebeginpushp:=k;nump:=1;end;inc(ans,t);end;end;writeln(ans);end.队队列列列列(queue)(queue)的的的的图图示示示示队列列const
6、 maxn = 1000;var queue:array1.maxn of integer; front,back,counter:integer; procedure push(x:integer); begin inc(counter); inc(back); /这样的话front,back初始化为1,0 queueback :=x;end;function pop():integer; begin pop:=queuefront; inc(front); dec(counter);end;队队列的列的列的列的实现样实现样例例例例PascalPascal代代代代码码队列列const int
7、 maxn=1000;int queuemaxn,counter=0, front=0,back= -1 ;void push(int x) queue+back=x;+counter;int pop() -counter; return queuefront+;队队列的列的列的列的实现样实现样例例例例C+C+代代代代码码队列列队列队列操作数组实现：元素queue0.maxn-1，队首front，队尾rear入队：inc(rear); queuerear := ele;出队：ele := queuefront; inc(front)队空条件：front rear问题：出队的元素还在数组里，不是
8、很浪费吗？循环队列把队列看成环行的，则入队：inc(rear); queuerear mod maxn := ele;出队：ele := queuefront mod maxn; inc(front)队空条件：front rear注意rear-frontmaxn队列的应用广度优先搜索单调队列双端队列PKU2823SlidingWindow给你一个长度为给你一个长度为 N的数组，一个长为的数组，一个长为 K的滑动的窗体从的滑动的窗体从最左移至最右端，你只能见到窗口的最左移至最右端，你只能见到窗口的K个数，每次窗体向个数，每次窗体向右移动一位，如下表：右移动一位，如下表： 任务：找出窗口在各位置时
9、的最小值与最大值任务：找出窗口在各位置时的最小值与最大值窗口位置窗口位置最小最小最大最大13-1-35367-1313-1-35367-3313-1-35367-3513-1-35367-3513-1-353673613-1-3536737PKU2823SlidingWindow样例：样例： window.in8313-1-35367window.out-1-3-3-333335567数据范围：数据范围： 20% n=500;50%n=100000;100%n=1000000;PKU2823SlidingWindow我们从最简单的问题开始：给定一个长度为N的整数数列a(i),i=0,1,.,N
10、-1和窗长度k.要求： f(i)=maxa(i-k+1),a(i-k+2),.,a(i)i=0,1,.,N-1问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。PKU2823SlidingWindow解法一：很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。那么有没有更快一点的算法呢？PKU2823SlidingWindow解法二：我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的
11、前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。单调队列单调递减队列是一个队列头元素一直是队列当中的最大值队列中的值是按照递减的顺序排列的一般来说，记录二元组支持两种操作操作1：从队列的末尾插入一个元素操作2：从队列的两端删除元素。单调队列1.插入元素：为了保证队列的递减性递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v，或队列为空，这个时候我们才将v插入到队尾。2.队尾的删
12、除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引小于i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index队首元素i-k+1时，将队首元素删除。假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3.那么我们构造一个长度为3的单调递减队列：首先，把8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：0：插入8，队列为：（8，0）1：插入7，队列为：（8，0），（7，1）2：插入12，队列为：（12，2）3：插入5，队列为：（12
13、，2），（5，3）4：插入16，队列为：（16，4）5：插入9，队列为：（16，4），（9，5）那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，PKU2823SlidingWindowPKU2823SlidingWindowhttp:/poj.org/problem?id=2823维护两个（最小和最大）双端队列，分别维护单调递降和单调递升即可。boolempty()if(h=t)return0;elsereturn1;voidmax_min(intflag)h=1;t=0;for(inti=1;ik)+h;/保持k个 if(flag)while(!empty()&(a
14、i=bt)t-;/删除不满足条件的队尾数值 b+t=ai;indext=i;if(i=k)if(ik)printf();printf(%d,bh);printf(n);小结通过维护栈和队列的单调性单调性解决一类统计问题另外，可以利用它们优化动规、贪心堆例题1：k路归并问题把k个有序表合并为一个有序表例如13689238910可以合并为12336889910k=2时，归并排序的二路归并操作堆分析每个表的元素都是从左到右移入新表把每个表的第一个元素组织成一个数据结构,每次删除最小值并放入新表中,然后加入此序列的下一个元素数据结构：快速取出最小值堆大根堆定义完全二叉树非叶子节点都比它的左右儿子（若存
15、在）大堆完全二叉树可以用数组表示i节点的左儿子i*2，右儿子i*2+1i节点的父亲i/2删除最小值元素三步法直接删除根将其改为maxlongint向下调整首先选取当前结点p的较大儿子. 如果比p大, 调整停止, 否则交换p和儿子, 继续调整向下调整插入元素和向上调整插入元素是先添加到末尾, 再向上调整向上调整: 比较当前结点p和父亲, 如果父亲比p小，停止; 否则交换父亲和p, 继续调整插入15建堆只需要一个一个插入堆中元素即可。堆排序大根堆每次出最大元素，放到数组的末尾堆排序堆排序例1k路归并问题每个表的元素都是从左到右移入新表把每个表的当前元素放入二叉堆二叉堆中,每次删除最小值并放入新表中
16、,然后加入此序列的下一个元素每次操作需要logk时间,因此总共需要nlogk的时间例2序列和的前n小元素给出两个长度为n的有序表A和B,在A和B中各任取一个,可以得到n2个和.求这些和最小的n个。例2可以把这些和看成n个有序表:A1+B1=A1+B2=A1+B3=A2+B1=A2+B2=A2+B3=An+B1=An+B2=An+B3=类似刚才的算法,每次O(logn),共取n次最小元素,共O(nlogn)例3丑数素因子都在集合2, 3, 5, 7的数称为ugly number求第n大的丑数思考题例3丑数初始：把1放入优先队列中每次从优先队列中取出一个元素k，把2k,3k,5k,7k放入优先队列
17、中从2开始，取出的第n个元素就是第n大丑数每取出一个数，插入4个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn)思考:如果集合元素个数m与n同阶,时间复杂度将变为怎样?如何优化?例4烽火台在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在（连续）（连续）m个烽火台中至少要有一个发出信号个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要话费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递。例如，有5个烽火台，它们发出的信号的代价依次为1、2、5、6、2，且m为3，则总共最少花费的代价为4
18、，即由第2个和第5个烽火台发出的信号。例4信息传递到i的最小代价fi只跟前面M个状态有关线性动态规划容易得出递归方程式如下：那么问题的解为：例4通过动态规划递归方程可以看出，min(optk)可以用一个m大小的堆维护复杂度降至O(nlgn)min(optk)是也是可以用单调队列来维护的复杂度降至O(n)堆的应用最小生成树的Prim算法最短路的Dijkstra算法哈夫曼树（NOIP2004的合并果子）并查集A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公
19、路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）并查集选出一个边集E，使得新图G=是一个连通图最小化：E中权值最大的边解法：瓶颈最小生成树Kruskal边集：按照权值从小到大排序依次加入往E中加入边，维护连通性并查集维护图的连通性的数据结构并查集并查集维护一些不相交集合S=S1,S2,Sr,每个集合Sr都有一个特殊元素repSi,称为集合代表.并查集支持的操作有合并两个集合，和查找某个节点属于那个集合。并查集一般来说我们用森林的结构实现并查集在森林中，每棵树代表一个集合。用树根来表示这个集合。对于每个元素我们需要一个数
20、组father来记录他的父亲。合并操作：两个集合S1、S2合并，将其中的一个树根作为另一个树根的子树即可。查找操作：对于一个元素u的查找，顺着u往上找，直到线索到根节点，也就确定了u所在的集合。并查集森林表示两个优化按秩合并： 在合并集合S1、S2的时候，我们让较小的树成为较大的树的子树。这里可以是深度、节点个数等启发函数来比较树的大小。路径压缩： 我们在查找完u至根节点的路径之后，一般将这条路径上的所有节点的父节点都设为根节点，这样可以大大减少之后的查找次数。合并小的合并到大的中路径压缩查找结束后顺便把父亲设置为根代码清单(只有路径压缩)Find(intx)if(fatherx=x)retu
21、rnx;fatherx=find(fatherx);return(fatherx);例题A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）例可爱的猴子(POI2003)树上挂着n只可爱的猴子，编号为1,n(2=n=200000)。猴子1的尾巴挂在树上，每只猴子有两只手，每只手可以最多抓住一只猴子的尾巴。所有的猴子都是悬空的，因此如果
22、一旦脱离了树，猴子会立刻掉到地上。第0,1,m(1=m=400000)秒钟每一秒都有某个猴子把它的某只手松开，因此常常有猴子掉到地上。现在请你根据这些信息，计算出每个猴子掉在地上的时间。例可爱的猴子(POI2003)如果把连在一起的猴子看成一个集合，每次松手就是断开了集合之间的某些联系或者直接将一个集合分离成两个。我们要求的是每只猴子第一次脱离猴子1所在集合的时间。“分查集”？例可爱的猴子(POI2003)我们不妨反过来想，如果时间从第m秒开始倒流，则出现的情形就是不断有某只猴子的手抓住另一只猴子。则我们要求的就转化成了：每只猴子最开始在什么时候合并到猴子1所在的集合。这样就可以应用并查集了。
23、例可爱的猴子(POI2003)设在第t秒钟，猴子i抓住（实际上是放开）了猴子j，那么此时就将i所在的集合与j所在的集合合并。如果需要合并，并且原先猴子i与猴子j在同一个集合，那么就将猴子j所在集合的所有猴子掉落的时刻都是t为了枚举某一个集合里的所有元素，我们还需要用一个链表结构与并查集共同维护猴子的集合。例可爱的猴子(POI2003)回顾我们的算法：并查集的操作时间复杂度为O(n(n)每个猴子只有唯一的掉落时间，所以链表中每个元素只枚举一遍，复杂度为O(n)所以算法的总时间复杂度是O(n(n)食物链食物链动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃
24、A。现有N个动物，以1N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1XY”，表示X和Y是同类。第二种说法是“2XY”，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1） 当前的话与前面的某些真的话冲突，就是假话；2） 当前的话中X或Y比N大，就是假话；3） 当前的话表示X吃X，就是假话。你的任务是根据给定的N（1N50,000）和K句话（0K100,000），输出假话的总数。并查集相关问题
25、单词方程(POI)假面舞会(NOI2008)Parity(Ural1003)Hash例题：给定一系列变换（不超过6种）如：abcceaeha求把某个串变成另一个串的一个最短变换步骤如：abc变成abhbcaabcabeaabhaaabhbca约定最短变换步数不超过10Hash字符串对应搜索树的一个节点普通的DFS、BFS存放在数组里判重但是字符串并不直接对应一个数组的下标解决办法：用Hash表来存放Hash表到Hash函数Hash的应用广泛一个好的Hash函数则显得尤为重要。在Hash函数的帮助下，Hash表可以处理各种各样的数据整数、实数、字符串、排列组合Hash函数优劣的评价解决冲突是Ha
26、sh表的关键冲突越少，Hash表的效率就越高数据分布越均匀，冲突越少Hash函数的随机性越好，数据分布越均匀整数的Hash函数Hash的方法有很多很多，没有什么固定的方法。我就介绍一下我使用hash函数，我最常用的方法就是进制运算和取mod。进制与mod的值最好是素数。我比较常用的是进制为131，mod 1000003比如一个整数324我可以利用(4*131+2*1312+3*1313)mod 1000003对于不是整数的其他类型的数据，我们也可以使用类似方法，比如字符串，我们可以利用其每一位的ascll编码值进行hash。当然还有很多更加优秀的hash算法，有兴趣的同学可以上网学习，这里就不一一列举了。方程的解数(NOI2001)已知一个n元高次方程：其中：x1,x2,xn是未知数，k1,k2,kn是系数，p1,p2,pn是指数。且方程中的所有数均为整数。假设未知数1xiM,i=1,n，求这个方程的整数解的个数。1 n 6；1 M 150方程的解数(NOI2001)1 n 6；1 M 1501xiM暴力枚举Mn但是Mn/2可以在1s内出解通过移项，把未知量均分到等号两侧Rabin-Karp算法在一个串中找另一个串第一次出现的位置c a ca ba b c a b ac a bO(NM)?谢谢
