数据结构(noip)

《数据结构(noip)》由会员分享，可在线阅读，更多相关《数据结构(noip)（83页珍藏版）》请在装配图网上搜索。

1、数据结构专题赖国堃福建师大附中提纲 简单数据结构的变种与高级应用 栈 队列 高级数据结构入门 并查集 堆 散列表（Hash表）栈 特性：后进先出(LIFO) 逻辑结构：只在一端操作的线性表 进栈push 出栈pop 数组实现：元素 int stacksize 栈顶指针 top栈的基本运算(1) 入栈： Push(s，x)初始条件：栈s已存在 操作结果：在栈s的顶部插入一个新元素x， x成为新的栈顶元素。栈发生变化。 push(s,x) top+;stop=x;return ;栈的基本运算(2) 出栈：Pop(s)初始条件：栈s存在且非空操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发

2、生变化。Pos(s)if (top=0) return;top-;return; 音乐会音乐会的等待的等待 问题描述：问题描述：N个人排队，队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。计算出有多少对人可以互相看见。输入格式：输入格式：第一行包含一个整数N (1 N 500 000), 表示队伍中共有N个人。接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10-9米)为单位 样例：样例： input 7 2 4 1 2 2 5 1 output 10音乐会的等待 针对序列8,8,6,4,2,3,7 考虑前5人：音乐会的等待 加入第6

3、个人之后 显然第6人可以看见3,4,5 并且可以保证4，5不被6之后的人看见音乐会的等待 4，5不被6之后的人看见，将这种没希望被后面的人看见的人记为灰色音乐会的等待 再加入第7位音乐会的等待 显然3，6要被标上灰色音乐会的等待 我们可以发现 每次插入后，剩下的兰色标记序列是非递增的； 每次插入前，标上灰色的人一定是兰色序列的最后几个。 这让我们想起了一个常用的数据结构：栈栈 这个栈是具备非递增特性的。音乐会的等待 如何统计？ 第6位插入栈之前，可以看见3,4,5，并且4,5矮于第6位； 所以元素在入栈之前，统计栈顶比他矮的人和恰比他高的人的人数就是这个人向前看向前看能看到的人数！ 音乐会的等

4、待 统计完，把栈顶比他矮的人（没希望的人）弹掉。（实际上我们可以一边统计一边弹） 接着自己入栈。 音乐会的等待 特别地，恰比他高的人的人数大于1时 我们不能把恰比他高的人给弹出栈，这样做就会统计错误； 但若一一保存，统计起来就浪费时间。 解决办法加权加权 记录栈中相同身高的人数，就减少统计量。音乐会的等待 由平摊分析得 每个人进栈一次，出栈最多一次。 所以时间复杂度为O(n).const maxn=500000;var n,i,k,p,t :longint; push,num :array0.maxn of longint; ans :int64;begin readln(n); readln

5、(k); p:=1; ans:=0; push1:=k; num1:=1; push0:=maxlongint; num0:=0; for i:=2 to n do begin readln(k); if kpushp then begin inc(ans); inc(p); pushp:=k; nump:=1; end input 7 2 4 1 2 2 5 1 output 10else begin t:=0; while pushp=k do begin inc(t,nump); dec(p); end; if p0 then inc(t,1); inc(p); if pushp=k t

6、hen inc(nump) else begin pushp:=k; nump:=1; end; inc(ans,t); end; end; writeln(ans);end.队队列列(queue)的的图图示示队队列列const 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

7、():integer; begin pop:=queuefront; inc(front); dec(counter);end;队队列的列的实现样实现样例例Pascal代代码码队队列列const int maxn=1000;int queuemaxn,counter=0, front=0,back= -1 ;void push(int x) queue+back=x;+counter;int pop() -counter; return queuefront+;队队列的列的实现样实现样例例C+代代码码队队列列队列队列操作 数组实现：元素queue0.maxn-1，队首front，队尾rear

8、入队：inc(rear); queuerear := ele; 出队：ele := queuefront; inc(front) 队空条件：front rear 问题：出队的元素还在数组里，不是很浪费吗？ 循环队列 把队列看成环行的，则 入队：inc(rear); queuerear mod maxn := ele; 出队：ele := queuefront mod maxn; inc(front) 队空条件：front rear 注意rear-frontmaxn队列的应用 广度优先搜索 单调队列双端队列PKU 2823 Sliding Window 给你一个长度为给你一个长度为 N 的数组，

9、一个长为的数组，一个长为 K 的滑动的窗体的滑动的窗体从最左移至最右端从最左移至最右端，你，你只能见到窗口的只能见到窗口的K个数，每次个数，每次窗体向右移动一位，如下表：窗体向右移动一位，如下表： 任务任务：找出找出窗口在各位置时窗口在各位置时的最小值与最大值的最小值与最大值窗口位置窗口位置最小最小最大最大 1 3 -1 -3 5 3 6 7 -131 3 -1 -3 5 3 6 7-331 3 -1 -3 5 3 6 7-351 3 -1 -3 5 3 6 7-351 3 -1 -3 5 3 6 7 361 3 -1 -3 5 3 6 7 37PKU 2823 Sliding Window

10、样例：样例： window.in 8 3 1 3 -1 -3 5 3 6 7 window.out -1 -3 -3 -3 3 3 3 3 5 5 6 7 数据数据范围：范围： 20% n=500; 50% n=100000; 100% n=1000000;PKU 2823 Sliding Window 我们从最简单的问题开始： 给定一个长度为N的整数数列a(i),i=0,1,.,N-1和窗长度k. 要求： f(i) = maxa(i-k+1),a(i-k+2),., a(i) i = 0,1,.,N-1 问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。PK

11、U 2823 Sliding Window 解法一： 很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。 这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。 那么有没有更快一点的算法呢？PKU 2823 Sliding Window 解法二： 我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。单调队列

12、 单调递减队列是一个队列头元素一直是队列当中的最大值队列中的值是按照递减的顺序排列的一般来说，记录二元组 支持两种操作操作1：从队列的末尾插入一个元素操作2：从队列的两端删除元素。单调队列 1.插入元素：为了保证队列的递减性递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v，或队列为空，这个时候我们才将v插入到队尾。 2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引小于i-k+1的时候，就说明队首的元素对于求f(i

13、)已经没有意义了，因为它已经不在窗里面了。所以当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，2），（5，3）4：插入16，队列为：（16，4）5：插入9，队列为：（16，4），（9，5）那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，1

14、6，PKU 2823 Sliding WindowPKU 2823 Sliding Window http:/poj.org/problem?id=2823 维护两个（最小和最大）双端队列，分别维护单调递降和单调递升即可。bool empty() if(h=t)return 0; else return 1;void max_min(int flag) h=1;t=0; for(int i=1;ik)+h;/ 保持k个 if(flag) while(!empty()&(ai=bt)t-;/ 删除不满足条件的队尾数值 b+t=ai; indext=i; if(i=k) if(ik)printf(

15、 ); printf(%d,bh); printf(n); 小结 通过维护栈和队列的单调性单调性 解决一类统计问题 另外，可以利用它们优化动规、贪心堆 例题1：k路归并问题 把k个有序表合并为一个有序表 例如 1 3 6 8 9 2 3 8 9 10 可以合并为1 2 3 3 6 8 8 9 9 10 k=2时，归并排序的二路归并操作堆 分析 每个表的元素都是从左到右移入新表 把每个表的第一个元素组织成一个数据结构, 每次删除最小值并放入新表中, 然后加入此序列的下一个元素 数据结构：快速取出最小值堆 大根堆定义 完全二叉树 非叶子节点都比它的左右儿子（若存在）大堆 完全二叉树可以用数组表示

16、i节点的左儿子 i*2，右儿子 i*2+1 i节点的父亲i/2删除最小值元素 三步法 直接删除根 将其改为maxlongint 向下调整 首先选取当前结点p的较大儿子. 如果比p大, 调整停止, 否则交换p和儿子, 继续调整向下调整插入元素和向上调整 插入元素是先添加到末尾, 再向上调整 向上调整: 比较当前结点p和父亲, 如果父亲比p小，停止; 否则交换父亲和p, 继续调整插入15建堆 只需要一个一个插入堆中元素即可。堆排序 大根堆 每次出最大元素，放到数组的末尾堆排序堆排序例1 k路归并问题 每个表的元素都是从左到右移入新表 把每个表的当前元素放入二叉堆二叉堆中, 每次删除最小值并放入新表

17、中, 然后加入此序列的下一个元素 每次操作需要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放入优先

18、队列中 每次从优先队列中取出一个元素k，把2k, 3k, 5k, 7k放入优先队列中 从2开始，取出的第n个元素就是第n大丑数 每取出一个数，插入4个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn) 思考: 如果集合元素个数m与n同阶, 时间复杂度将变为怎样? 如何优化?例4 烽火台 在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在（连续）（连续）m个烽火台中至少要有一个发出信号个烽火台中至少要有一个发出信号。 现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要话费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递。

19、 例如，有5个烽火台，它们发出的信号的代价依次为1、2、5、6、2，且m为3，则总共最少花费的代价为4，即由第2个和第5个烽火台发出的信号。例4 信息传递到i的最小代价fi只跟前面M个状态有关 线性动态规划 容易得出递归方程式如下： 那么问题的解为：miivaluenimivaluekoptioptimik1,min1min1koptNMNk例4 通过动态规划递归方程可以看出，min(optk)可以用一个m大小的堆维护 复杂度降至O(nlgn) min(optk)是也是可以用单调队列来维护的 复杂度降至O(n)miivaluenimivaluekoptioptimik1,min1堆的应用 最小

20、生成树的Prim算法 最短路的Dijkstra算法 哈夫曼树（NOIP2004的合并果子）并查集A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）并查集 选出一个边集E，使得 新图G = 是一个连通图 最小化：E中权值最大的边 解法：瓶颈最小生成树 Kruskal 边集：按照权值从小到大排序 依次加入往E中加入边，维护连通性 并查集

21、维护图的连通性的数据结构并查集 并查集维护一些不相交集合S=S1, S2, , Sr, 每个集合Sr都有一个特殊元素repSi,称为集合代表. 并查集支持的操作有合并两个集合，和查找某个节点属于那个集合。并查集 一般来说我们用森林的结构实现并查集 在森林中，每棵树代表一个集合。用树根来表示这个集合。 对于每个元素我们需要一个数组father来记录他的父亲。 合并操作：两个集合S1、S2合并，将其中的一个树根作为另一个树根的子树即可。 查找操作：对于一个元素u的查找，顺着u往上找，直到线索到根节点，也就确定了u所在的集合。并查集 森林表示两个优化 按秩合并： 在合并集合S1、S2的时候，我们让较

22、小的树成为较大的树的子树。这里可以是深度、节点个数等启发函数来比较树的大小。 路径压缩： 我们在查找完u至根节点的路径之后，一般将这条路径上的所有节点的父节点都设为根节点，这样可以大大减少之后的查找次数。合并 小的合并到大的中路径压缩 查找结束后顺便把父亲设置为根代码清单(只有路径压缩) Find(int x) if (fatherx=x) return x; fatherx=find(fatherx); return(fatherx);例题 A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。 给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连

23、着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）例 可爱的猴子(POI2003) 树上挂着n只可爱的猴子，编号为1,n (2=n=200 000)。猴子1的尾巴挂在树上，每只猴子有两只手，每只手可以最多抓住一只猴子的尾巴。所有的猴子都是悬空的，因此如果一旦脱离了树，猴子会立刻掉到地上。第0,1,m(1=m=400000)秒钟每一秒都有某个猴子把它的某只手松开，因此常常有猴子掉到地上。 现在请你根据这些信息，计算出每个猴子掉在地上的时间。例 可爱的猴子(POI2003) 如果把连

24、在一起的猴子看成一个集合，每次松手就是断开了集合之间的某些联系或者直接将一个集合分离成两个。 我们要求的是每只猴子第一次脱离猴子1所在集合的时间。 “分查集”？例 可爱的猴子(POI2003) 我们不妨反过来想，如果时间从第m秒开始倒流，则出现的情形就是不断有某只猴子的手抓住另一只猴子。 则我们要求的就转化成了：每只猴子最开始在什么时候合并到猴子1所在的集合。 这样就可以应用并查集了。例 可爱的猴子(POI2003) 设在第t秒钟，猴子i抓住（实际上是放开）了猴子j，那么此时就将i所在的集合与j所在的集合合并。 如果需要合并，并且原先猴子i与猴子 j在同一个集合，那么就将猴子j所在集合的所有猴

25、子掉落的时刻都是t 为了枚举某一个集合里的所有元素，我们还需要用一个链表结构与并查集共同维护猴子的集合。例 可爱的猴子(POI2003) 回顾我们的算法： 并查集的操作时间复杂度为O(n(n) 每个猴子只有唯一的掉落时间，所以链表中每个元素只枚举一遍，复杂度为O(n) 所以算法的总时间复杂度是O(n(n)食物链食物链 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1 X Y”，表示X和Y是同

26、类。第二种说法是“2 X Y”，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1） 当前的话与前面的某些真的话冲突，就是假话；2） 当前的话中X或Y比N大，就是假话；3） 当前的话表示X吃X，就是假话。你的任务是根据给定的N（1N50,000）和K句话（0K100,000），输出假话的总数。并查集相关问题 单词方程(POI) 假面舞会(NOI2008) Parity(Ural1003)Hash 例题： 给定一系列变换（不超过6种） 如：abc cea eha 求把某个串变成另一个串的

27、一个最短变换步骤 如：abc变成abhbca abcabeaabhaaabhbca 约定最短变换步数不超过10Hash 字符串对应搜索树的一个节点 普通的DFS、BFS存放在数组里判重 但是字符串并不直接对应一个数组的下标 解决办法：用Hash表来存放Hash表到Hash函数 Hash的应用广泛 一个好的Hash函数则显得尤为重要。 在Hash函数的帮助下，Hash表可以处理各种各样的数据 整数、实数、字符串、排列组合Hash函数优劣的评价 解决冲突是Hash表的关键 冲突越少，Hash表的效率就越高 数据分布越均匀，冲突越少 Hash函数的随机性越好，数据分布越均匀NodeHeadNodeN

28、odeHeadHeadNodeHeadNodeHeadRootHeadNodeHeadHeadNodeNodeNodeNodeHeadHeadRoot整数的Hash函数 Hash的方法有很多很多，没有什么固定的方法。我就介绍一下我使用hash函数，我最常用的方法就是进制运算和取mod。 进制与mod的值最好是素数。 我比较常用的是进制为131，mod 1000003 比如一个整数324 我可以利用(4*131+2*1312+3*1313)mod 1000003 对于不是整数的其他类型的数据，我们也可以使用类似方法，比如字符串，我们可以利用其每一位的ascll编码值进行hash。 当然还有很多更

29、加优秀的hash算法，有兴趣的同学可以上网学习，这里就不一一列举了。方程的解数(NOI2001) 已知一个n元高次方程： 其中：x1, x2, ,xn是未知数，k1,k2,kn是系数，p1,p2,pn是指数。且方程中的所有数均为整数。 假设未知数1 xi M, i=1,n，求这个方程的整数解的个数。1 n 6；1 M 150121 122.0npppnnk xk xk x方程的解数(NOI2001) 1 n 6；1 M 150 1 xi M 暴力枚举Mn 但是Mn/2可以在1s内出解 通过移项，把未知量均分到等号两侧121 122.0npppnnk xk xk x)(666555444333222111pxkpxkpxkpxkpxkpxkRabin-Karp算法 在一个串中找另一个串第一次出现的位置c a ca ba b c a b ac a bO(NM)? 谢谢