NOIP中常用的数据结构.ppt

NOIP中常用的数据结构,清华大学 钱桥,主要内容：,堆 单调队列 并查集,例：首先给你n个数，之后进行n次操作，操作有两种： 1、询问最小值，并将它删除 2、插入一个新的数x,堆,思路1：用数组存这些数 询问时，扫描一遍最小值，并将它删除 O(n) 插入时，将它放在数组最后 O(1) 总时间复杂度 O(n2),思路2：仍然用数组存这些数，排序！从小到大存储 询问时，第一个即最小值 O(1) 删除最小值时，标记前移 O(1) 插入时，可通过二分找到插入位置 O(LogN) 但插入这个数后，后面的数要整体平移 O(n) 时间复杂度 O(n2),思路3：用链表存这些数，从小到大有序存储 询问时，第一个即是最小值，并将它删除 O(1) 插入时，若找到位置，可直接插入 O(1) 但链表上无法二分查找，查找需整体扫描 O(n) 总时间复杂度 O(n2),例：首先给你n个数，之后进行n次操作，操作有两种： 1、询问最小值，并将它删除 2、插入一个新的数x,堆,堆闪亮登场！,插入一个数 O(LogN) 删除一个数 O(LogN) 查询最小值 O(1) 总时间复杂度 O(NLogN),堆,堆是一棵完全二叉树,深度为LogN！,给节点顺序标号1n,i,2*i,2*i+1,只需用数组A1An存储,堆,从根到每个叶节点的路径都是单调递增的,最小值是根！ O(1)查找最小值,接下来我们的任务是： 1、插入一个数，在O(LogN)时间内，把结构恢复成堆 2、删除最小值，在O(LogN)时间内，把结构恢复成堆 *3、删除一个指定元素，在O(LogN)时间内，把结构恢复成堆,堆,1、插入一个元素z,不关心大小，只关心位置,如何调整？,显然，xy,x,y,情况1：z=x,完美结束,z,情况2：zx,堆,1、插入一个元素z,不关心大小，只关心位置,如何调整？,显然，xy,z,y,情况1：z=x,完美结束,x,情况2：zx,将x和z互换位置，显然zy，以z为根的子树一定是堆,翻页继续！,1、插入一个元素z,x,y,z,堆,显然，uw,情况1：z=u,完美结束,情况2：zu,u,w,1、插入一个元素z,x,y,u,堆,显然，uw,情况1：z=u,完美结束,情况2：zu,将u和z互换位置，显然zw，以z为根的子树一定是堆,继续操作，直至某次“完美结束”或z被移动到根为止。,z,w,最多做LogN次！,堆,1、插入一个元素z 程序实现,n+; an=z; i = n; while (i1) if (ai ai/2) t = ai; ai = ai/2; ai/2 = t; i = i / 2; else break; ,n+; i =n while (i1) if (z 1) ai = ai 1; i = i 1; else break; ai = z;,堆,2、删除最小值,最小值是谁？,删除一个数后结构是什么样？,第一步：删除最小值 第二步：把下面的数z移动上来 第三部：调整！,堆,2、删除最小值,左子树A是一个堆 右子树B是一个堆,z,若z不和谐呢？,x,y,此时根据x和y的大小分类讨论 不妨设xy（反之对称）,若zx且zy，则整棵树是堆,A,B,堆,2、删除最小值,x,z,y,将x与z互换位置,B是堆，x比y小，x及右边满足堆性质,若A是堆，则整棵树是堆,左子树C是一个堆 右子树D是一个堆 目标：A变成堆,子问题！规模缩小！,每次交换深度减1 LogN次解决问题,A,B,C,D,堆,2、删除最小值 程序实现,n-; a1=an+1; i = 1; while (2*i aj) t = ai; ai = aj; aj = t; i = j; else break; ,z = an; n-; i = 1; while (2*i aj) ai = aj; i = j; else break; ai = z;,堆,3、删除一个指定元素,给出一个值k，让你把堆中等于k的数删除,k,等于k的数在左边？在右边？,不可做！,堆,3、删除一个指定元素,例：给你n份试卷，每份试卷上有两个信息：学号、分数。现进行n次操作，操作有三种： 1、新插入一份试卷，并告诉你这份试卷的学号及分数 2、请你输出分数最高的学号 3、给你一个学号，将他的试卷删除 数据保证没有两张试卷学号相同，保证没有两张试卷分数相同。 学号都为12*n的正整数，n=100000。,用a数组存分数，它是一个堆,backi表示堆中i号位置试卷的学号,映射,ranki表示i学号试卷在堆中的位置,堆,3、删除一个指定元素,删除x学号的试卷，即删除a中下标为rankx的元素,首先找到rankx 之后与删除最小值是一样的,维护rank和back？ Bx=backx; By=backy; Rankbx=y; Rankby=x; Backx=y; Banky:=x; T:=ax; ax:=ay; ay:=t;,堆,上午考试题：,Fi表示第i天的神奇药水最大的神奇度是多少 Fi=max(Fj)+ai 1=ji 且 j+Cj=i=j+Cj+Dj-1,j号药水进入兴奋状态,j号药水进入失活状态,对这一段的i，可以提供最大值,堆,第一步：整理所有事件每种药水进入兴奋状态、进入失活状态,第二步：做Dp,for (i=1; i=n; i+) 往堆中插入第i时刻变成兴奋状态的药水； 往堆中删除第i时刻变成失活状态的药水； Fi=堆中最大值+ai； ,每种药水最多只被插入一次、删除一次 事件复杂度O(NLogN),单调队列,功能：插入一个数 O(1) （均摊） 删除一个数 O(1) 查询最小值 O(1) 要求：对于任意两个数x、y，若x在y之前插入，则必须满足x在y之前删除,例：昨天讲过的水桶问题 给出一个长度为n的数列A 我们要询问1m、2m+1、3m+2、n-m+1n的最小值,单调队列,考虑两个数x和y，其中x在y之前插入,xy 当前x可能是最小值，但x删除后y可能是最小值,xy y可能是最小值，x不可能是最小值,对于两个数x、y，若x比y插入早且xy，则我们没有必要记录x,则我们记录的数中，任意两个x、y满足：若x比y早，则x比y小,按插入时间排序！ 数值单调递增！,单调队列,我们用队列a存储这些需要记录的数 队列中的数是按插入时间排序的 ai.t表示插入时间、ai.p表示数值 st为头指针、ed为尾指针，asted为队列的有效区间,当前单调队列中的最小值,ast,删除一个元素,ast,插入一个元素,插入在最后,数值不单调怎么办？,删！,均摊O(1),单调队列,查询最小值： Function minnum : longint; Begin exit(ast); End; 插入一个时间为t 数值为x的数 Procedure insert(t,x:longint); begin While (st=ed) and (x=aed.p) do Begin inc(ed); aed.p:=x; aed.t:=t; End; End;,删除一个数 Procedure delnum; Begin inc(st); End;,并查集,维护集合，快速实现“并”和“查”,有n个元素，编号1n，初始各自为一个集合。 现要进行n次操作，操作有两种： 1、询问x和y是否在同一集合 2、将x所在集合和y所在集合合并 请对每次询问给出答案,思路1：邻接矩阵 mapx,y=1 在同一个集合,询问O(1)，合并超慢,思路2：染色 colorx表示x元素的颜色 若两元素颜色相同，在同一集合,询问O(1)，合并O(n),并查集,把每个元素当做一个点 每个点恰好有一条从它出发的边 用fatheri表示i号点指向哪个点,定义“代表元素”： 每个集合恰好有一个代表元素 代表元素出发的边指向自己,跟代表元素a在同一个集合的点，与代表元素构成一棵树，代表元素为树根。,并查集,1、查找两个点x、y是否在同一个集合,只需沿着边走到根，判断代表元素是否相同,while (fatherx != x) x = fatherx; while (fathery != y) y = fathery; if (x = y) ,并查集,2、合并两个点x、y所在的集合,直接修改fatherx、fathery？,破坏原结构！,修改代表元素的father！,while (fatherx != x) x = fatherx; while (fathery != y) y = fathery; if (x != y) fatherx = y;,并查集,时间复杂度分析,仍然很高！,路径压缩！,当你寻找x的代表元素时，顺便把路径上的点的父亲直接改为代表元素，减小树的深度,P = x; While (x != fatherx) x=fatherx; While (p != x) t = fatherp; fatherp = x; p = t ; ,并查集,例：给出一个n个点m条边的无向图。 之后给你Q个操作，操作有两种： 1、添加一条从x到y的无向边 2、询问x和y点是否连通,例：给出一个n个点m条边的无向图。 之后给你Q个操作，操作有两种： 1、删除一条从x到y的无向边 2、询问x和y点是否连通,最小生成树问题,并查集,例：给出一个n个点m条边的无向图。每条边上有一个权值 之后给你Q个询问：只走权值小于W的边，是否能从x走到y 见Day1T1,哈希,功能：插入一个数k O(1) 删除一个数k O(1) 询问k是否存在 O(1) N=100000 k=109,P为n的五倍左右的质数 将所有的数按照(a mod p)分类,N=7 p=37 A=(2,3,5,10,37,39,73) A0 A1 A2 A3 A4 A5 A36 37 2 3 5 10 73 39,扩展欧几里得算法,例：求ax + by=1的一组解（a , b为整数，且互质） a , bb x=y1 y=x1 a / b * y1 问题转化为求x1,y1，利用式递归求解。 直到得到 1x + oy = gcd(1, 0) = 1，得到一组解。,扩展欧几里得算法,例：求ax mod p = 1的解（a , p为整数，且互质） a , p ax + py = 1 利用扩展欧几里得算法求解。,扩展欧几里得算法,转化为：求 mod p = ? (p为质数),x(n+1)-1 x-1,例：给出n、x、p三个正整数，问(x0+x1+x2+xn) 对p取模的结果。数据规模：n、x、p=109。,转化为：求(A/B) mod p = ? (p为质数),转化为：求(A*x) mod p =