高级数据结构及其应用.ppt

else begin t:=0; while push[p]=k do begin inc(t,num[p]); dec(p); end; if p0 then inc(t,1); inc(p); if push[p]=k then inc(num[p]) else begin push[p]:=k; num[p]:=1; end; inc(ans,t); end; end; writeln(ans); end. 例题 A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。 给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路） 食物链 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1 X Y”，表示X和Y是同类。第二种说法是“2 X Y”，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1） 当前的话与前面的某些真的话冲突，就是假话；2） 当前的话中X或Y比N大，就是假话；3） 当前的话表示X吃X，就是假话。你的任务是根据给定的N（1≤N≤50,000）和K句话（0≤K≤100,000），输出假话的总数。 对于不是整数的其他类型的数据，我们也可以使用类似方法，比如字符串，我们可以利用其每一位的ascll编码值进行hash。 当然还有很多更加优秀的hash算法，有兴趣的同学可以上网学习，这里就不一一列举了。 路径压缩 查找结束后顺便把父亲设置为根 代码清单(只有路径压缩) Find(int x) { if (father[x]==x) return x; father[x]=find(father[x]); return(father[x]); } 例 可爱的猴子(POI2003) 树上挂着n只可爱的猴子，编号为1,…,n (2=n=200 000)。猴子1的尾巴挂在树上，每只猴子有两只手，每只手可以最多抓住一只猴子的尾巴。所有的猴子都是悬空的，因此如果一旦脱离了树，猴子会立刻掉到地上。第0,1,…,m(1=m=400000)秒钟每一秒都有某个猴子把它的某只手松开，因此常常有猴子掉到地上。 现在请你根据这些信息，计算出每个猴子掉在地上的时间。 例 可爱的猴子(POI2003) 如果把连在一起的猴子看成一个集合，每次松手就是断开了集合之间的某些联系或者直接将一个集合分离成两个。 我们要求的是每只猴子第一次脱离猴子1所在集合的时间。 “分查集”？ 例 可爱的猴子(POI2003) 我们不妨反过来想，如果时间从第m秒开始倒流，则出现的情形就是不断有某只猴子的手抓住另一只猴子。 则我们要求的就转化成了：每只猴子最开始在什么时候合并到猴子1所在的集合。 这样就可以应用并查集了。 例 可爱的猴子(POI2003) 设在第t秒钟，猴子i抓住（实际上是放开）了猴子j，那么此时就将i所在的集合与j所在的集合合并。 如果需要合并，并且原先猴子i与猴子 j在同一个集合，那么就将猴子j所在集合的所有猴子掉落的时刻都是t 为了枚举某一个集合里的所有元素，我们还需要用一个链表结构与并查集共同维护猴子的集合。 例 可爱的猴子(POI2003) 回顾我们的算法： 并查集的操作时间复杂度为O(nα(n)) 每个猴子只有唯一的掉落时间，所以链表中每个元素只枚举一遍，复杂度为O(n) 所以算法的总时间复杂度是O(nα(n)) 并查集相关问题 单词方程(POI) 假面舞会(NOI2008) Parity(Ural1003) Hash 例题： 给定一系列变换（不超过6种） 如：a?bc c?ea e?ha 求把某个串变成另一个串的一个最短变换步骤 如：abc变成abhbca abc?abea?abhaa?abhbca 约定最短变换步数不超过10 Hash 字符串对应有哪些信誉好的足球投注网站树的一个节点 普通的DFS、BFS存放在数组里判重 但是字符串并不直接对应一个数组的下标 解决办法：用Hash表来存放 Hash表到Hash函数 Hash的应用广泛