ACM中的数据结构课件

1、ACM竞赛数据结构 南阳理工学院 ACM集训队第1页，共57页。基本数据结构基础：队列、堆栈排序与检索：快速排序和归并排序的思想串的模式匹配：KMP, Trie(*)，AC自动机后缀树，后缀数组树：哈夫曼树，树状数组，线段树，(各种树)。字典：Hash、并查集(*)、可并优先队列，堆第2页，共57页。队列Queue特点：先进先出 FIFO入队O(1), 出队O(1)不能随机访问中间的元素实现方法：数组STL第3页，共57页。队列Queue#include using namespace std; /STL queue queue Q; Member Functions:第4页，共57页。堆栈S

2、tack特点：先进后出 FILO入队O(1), 出队O(1)不能随机访问中间的元素实现方法：链表数组STL第5页，共57页。排序排序快速排序 O(n*log(n)堆排序（稳定排序）O(n*log(n)选择排序,冒泡排序 O(n2)O(n)随机查找第k小元素第6页，共57页。std:sortSTL #includeusing namespace std;int aM,bM;sort(a,a+n); sort(a,a+n,cmp);bool cmp(const int x,const int y) return xy; /return bxby;第7页，共57页。随机查找第k小元素(快速排序思想)

3、随机第k小元素int select(int *a,int b,int e,int k)if(b=e) return ab;int x=ab+rand()%(e-b+1),i=b-1,j=e+1,tmp;while (ij) while(a+ix); if (ij) tmp=ai,ai=aj,aj=tmp;第8页，共57页。 if (j=e) j-;if (k=i) return select(a,b,j,k);else return select(a,j+1,e,k-i);第9页，共57页。串的模式匹配-KMP由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹

4、配算法简称为KMP算法朴素的串模式匹配的复杂度是O(m*n)长度为m的母串S, 匹配长度为n的子串A求母串S中有多少个子串A求母串S中第1个子串A的位置KMP算法的复杂度为O(m+n)总体思想O(n)线性时间预处理子串，求出前缀函数O(m)线性时间扫描母串求出匹配第10页，共57页。串的模式匹配-KMP/KMP 求前缀函数int failmaxlen;void makefail( char *t, int lt ) -t; for(int i=1,j=0;i0 & ti!=tj) j=failj; 第11页，共57页。串的模式匹配-KMPint kmp(char *s, int ls, cha

5、r *t, int lt, int i,int &longest,int &lp) longest = lp = 0; -s; -t; for(int j=1; i0 & si!=tj ) j=failj; if( jlongest ) longest = j; lp = i-j; if( j=lt ) return i-lt; return -1;第12页，共57页。练习 链接：/JudgeOnline/problem.php?pid=5 给出两个由0和1组成的字符串A和B，求串A在串B中出现了多少次？样例输入11100111011010111001001001000110101101000

6、10101011 样例输出303第13页，共57页。字典树 trieTrie结构基于关键码分解的数据结构，叫作Trie结构 “trie”这个词来源于“retrieval” 主要应用信息检索用来存储英文字符串，尤其大规模的英文词典 自然语言理解系统中经常用到第14页，共57页。Trie结构应用字典树存储字典里面的单词英文的单词是有26个字母组成的（简单起见，我们忽略大小写）英文字符树每一个内部结点都有26个子结点树的高度为最长字符串长度第15页，共57页。字典树 trie第16页，共57页。字典树的改进由于单词可能不等长，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息第17页

7、，共57页。字典树中的检索首先用待查关键码的第一个字符与树林的各个根的字符相比较，然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索，.，直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；若检索一直进行到树叶，那么就在树目录里找到了给定的关键码第18页，共57页。Trie树的插入首先根据插入纪录的关键码找到需要插入的结点位置如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录如果是内部结点，则在那个分支上

8、应该是空的，所以直接为该分支建立一个新的叶结点即可Trie树的删除根据插入纪录的关键码找到需要删除的结点位置如果一个被删除结点的父结点没有其他的儿子，那么就需要合并否则只需要将此分支设置为空即可第19页，共57页。练习 链接：/JudgeOnline/problem.php?pid=290 给出N(1= N = 4000000)个动物的名字，求出现次数最多的动物的名字与出现次数。动物名字用一个字符串表示。（字符串的长度不超过10,字符串全为小写字母）。 样例输入10boarpigsheepgazellesheepsheepalpacaalpacamarmotmole样例输出sheep 3第20

9、页，共57页。关于后缀树和后缀数组字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在ACM比赛中中后缀数组比后缀树要更为实用。 更多有关后缀树和后缀数组请参考：后缀树/view/117678.html 后缀数组/view/1240197.htm第21页，共57页。树状数组树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a1.n，那么查询a1 + + ai

10、 的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。 令这棵树的结点编号为C1，C2Cn。令每个结点的值为这棵树的值的总和，那么容易发现： C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 = A5 C6 = A5 + A6 C7 = A7 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A1

11、5 + A16第22页，共57页。树状数组 第23页，共57页。树状数组设节点编号为x，那么这个节点管辖的区间为2k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，所以很明显： Cn = A(n 2k + 1) + + An 算这个2k有一个快捷的办法，定义一个函数如下即可： int lowbit(int x) return x & (x (x 1); 第24页，共57页。树状数组当想要查询一个SUM(n)时，可依据如下算法即可：step1:令sum = 0，转第二步； step2:假如n = 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；

12、 step3: 令n = n lowbit(n)，转第二步。可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明： n = n lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。第25页，共57页。树状数组解决的常见问题插线问线插线问点第K大求逆序数第26页，共57页。算法实现第27页，共57页。练习 链接：/JudgeOnline/problem.php?pid=116描述南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。小工是南将军手下的军师，南将

13、军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。输入只有一组测试数据第一行是两个整数N,M，其中N表示士兵的个数(1N1000000)，M表示指令的条数。(1M100000)随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0=ai=100)随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1=I=N,1=A

14、=100),表示第I个士兵新增杀敌数为A.输出对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行第28页，共57页。样例输入5 61 2 3 4 5QUERY 1 3ADD 1 2QUERY 1 3ADD 2 3QUERY 1 2QUERY 1 5样例输出68820第29页，共57页。树状数组推广二维树状数组求suma1.m1.n维护和查询复杂度均为O(logm*logn)用于动态求子阵和,数组内容保存在sum.a中还可以进一步推广到三维树状数组第30页，共57页。练习 链接：/JudgeOnline/problem.php?pid=1089描述提供一个N*N的矩

15、阵，其中每一个格子中的数不是1就是0，初始时每一个格子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标(x1,y1)，以及右下角的坐标(x2, y2)，并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。T 100,N 1000 , Q 50000.输入Line1：给出一个T，表示组数Line2:给出两个数N，Q.矩阵大小，询问次数Line：3.3+Q: 输入C，则后又四个数(x1,y1),(x2,y2)输入Q，则后两个数(x,y)输出每次询问输出查询结果。第31页，共57页。样例输入12 10C 2 1 2 2

16、Q 2 2C 2 1 2 1Q 1 1C 1 1 2 1C 1 2 1 2C 1 1 2 2Q 1 1C 1 1 2 1Q 2 1样例输出1001第32页，共57页。线段树线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点a,b，它的左儿子表示的区间为a,(a+b)/2，右儿子表示的区间为(a+b)/2+1,b。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离

17、散化让空间压缩。参考论文：数据结构的选择与算法效率 从IOI98试题PICTURE谈起 第33页，共57页。线段树解决的基础问题1.数组数组能解决的所有问题（插点问线、插线问点、逆序数、第k大等）2.插线问线（lazy标记）3.各种区间更改、查询问题第34页，共57页。练习链接：/JudgeOnline/problem.php?pid=1068描述已知N（1=N=10005）个随机整数，对这些数可能有以下几种操作或询问：1. A a b c 表示给区间a到b内每个数都加上c；2. S a b 表示输出区间a到b内的和；3. Q a b 表示输出区间a到b内的奇数的个数；接下来有M（1=M=10

18、000，M为询问次数）次操作，对于操作2和3，输出结果。样例输入5 51 2 3 4 5Q 1 4S 1 5A 1 4 1S 1 5Q 2 5样例输出215193第35页，共57页。Hash散列Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 数学表述为：h = H(M) ，其中H( )-单向散列函数，M-任意长度明文，h-固定长度散列值 第36页，共57页。Hash散列当两个或

19、两个以上的关键字散列到同一个值的时候，发生冲突。解决方法：开散列和闭散列Hash冲突取决于Hash函数的选择散列空间的大小开闭散列输入数据第37页，共57页。字符串散列ELFHash函数/prime:3001,5003,10007,20011,50021,100003,150001,200003,500009,704447,901963,1009237, 1199993, 1500007,2000003,5000011int ELFhash(char *key) unsigned int g,h=0;while (*key) h=(h24; h&=g;return h%Size;/Size要用

20、大质数第38页，共57页。字符串散列SuperFastHash(1)#define get16bits(d) (unsigned int)(d)1)=2;for (;len0;len-)g+=get16bits(key);key+=2;h=(get16bits(key)11)g; key+=2;g=(g11;第39页，共57页。字符串散列SuperFastHash(2)switch(rem) case 3:g+=get16bits(key); g=g16; g=key211;break; case 2:g+=get16bits(key); g=g17; break; case 1: g+=*k

21、ey; g=g1; break; g=g5; g=g17; g=g6; return g%M;第40页，共57页。整数Hash函数常用平方取余数int IntegerHash(int key) unsigned int p=key*key; /溢出就溢出 return p%Size; /返回0.size-1第41页，共57页。集合set STL第42页，共57页。集合set STL第43页，共57页。集合multiset STL第44页，共57页。集合multiset STL第45页，共57页。并查集Disjoint Sets并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题。并查集

22、的主要操作有1合并两个不相交集合 Union(A,B)2判断两个元素是否属于同一个集合 Findroot(X) 第46页，共57页。Disjoint SetsFindroot(x)同BST一样，最坏情况为一条链，那么进行一次Find操作的时间复杂度为O(N)，代价太大。改进方法:1.启发式合并将结点少的树合并到结点多的树上。2.路径压缩当一条路找到根结点了以后，把所有处于路径中的结点的父亲指针直接指向该集合的父亲。第47页，共57页。算法实现int find(int x)/查找祖先 return fatherx = x ? x : fatherx = find(fatherx);void Un

23、ion(int x, int y) int a = find(x); int b = find(y); if (a = b) return; if (ranka = rankb) fatherb = a; ranka += rankb; else fathera = b; rankb += ranka; 第48页，共57页。练习 链接：/JudgeOnline/problem.php?pid=711描述异形卵潜伏在某区域的一个神经网络中。其网络共有N个神经元（编号为1,2,3,N），这些神经元由M条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动，但在神经网络中任一条通

24、道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大，否则它会很不舒服。现在异形卵聚居在神经元S点，想游动到神经元T点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线，也就是所谓最舒适的路线。输入第一行： K 表示有多少组测试数据。 接下来对每组测试数据：第1行: N M第2M+1行： Xi Yi Vi (i=1,.,M)表示神经元Xi 到神经元Yi之间通道的速度必须是Vi最后一行： S T ( S T )【约束条件】2K5 1N500 0M5000 1 Xi, Yi , S , T N 0 Vi 30000，Vi是整数。数据之间有一个空格。第49页

25、，共57页。输出对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。样例输入23 21 2 22 3 41 33 31 2 101 2 52 3 81 3样例输出25/4第50页，共57页。题目分析 枚举速度最大的边，找出能够从S到达T的最大速度，然后求出它们的比值，与已经求出的比值进行比较，如果比之前的比值小，则更新比值，记录此种情况下的最大速度和最小速度，直到枚举到从S不能到达T，跳出循环。求出最大速度和最小速度的比值即可。如果从S可以到达T，说明S和T属于同一个集合，因此可以利用并查集来判断从S是否可以到达T。第51页，共57页。STL heapmake_heap(a,a+n,cmp) 默认是最大堆化，即cmp为真时a做叶子pop_heap(a,a+n,cmp) 将堆顶元素移至an-1且a0:n-2仍为堆push_heap(a,a+n,cmp) 将an-1加入堆a0:n-2sort_heap(a,a+n,cmp) 将堆an-1化为排序好的数组an-1bool cmp(int x,int