算法合集之序的应用幻灯片.ppt

《算法合集之序的应用幻灯片.ppt》由会员分享，可在线阅读，更多相关《算法合集之序的应用幻灯片.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法合集之序的应用第1页，共26页，编辑于2022年，星期一基本的序4 12 31 24 43 25 344 12 24 25 31 34 43 大小序12345671 2 4 6 7 5 3DFS序1 2 4 7 5 3 6拓扑序序是数据之间隐藏的一种基本关系：第2页，共26页，编辑于2022年，星期一序的应用使得一个问题得到直接解决（大多是交互式问题）应用序，挖掘题目的深层性质，使得问题得到转化。第3页，共26页，编辑于2022年，星期一树的构造问题描述：一棵含有n个节点的树，所有的节点依次编号为1,2,3,n，每个节点i有一个权值s(i)，也分别是1,2,3,n，并且各不相同。对于编号为

2、v的节点，定义t(v)为v的后代中所有权值小于s(v)的节点个数。现在给出这棵树及t(1),t(2),t(n)，请你求出这棵树每个节点的权值。第4页，共26页，编辑于2022年，星期一树的构造已知T构造S426578193 S497821356426578193 T313100000为了理解题目我们来看一个实例：第5页，共26页，编辑于2022年，星期一树的构造我们来考虑这个树的DFS序列：4265781933310100001(3)2(1)4(0)5(0)7(0)3(3)6(1)8(0)9(0)DFS序列的重要性质：第6页，共26页，编辑于2022年，星期一树的构造由于权值分别是1,2,3,

3、n。我们不妨认为从左到右有N个格子，如果从左数第I个格子填入了节点J，则S(j)=i。4 2 5 1 7 8 639426578193313100000426578193497821356一组可行解左数第4个位置左数第7个位置第7页，共26页，编辑于2022年，星期一树的构造不能漏填，也不能冲突。每个格子的左边，都恰好有t(i)个格子填入了自己的子孙。不能超出1n的边界范围。如果我们按照DFS的顺序，依次填写节点。对于每个节点j的左边，则必须预留下至少t(j)个空格给权值比他小的子孙。看看“填”的时候的具体要求第8页，共26页，编辑于2022年，星期一树的构造依次按DFS序填写每个节点时，对于

4、节点J，给他的子孙恰好预留t(j)个空位，即j填在第t(j)+1个空格，就是可行解4251786394265781933131000001(3)2(1)4(0)5(0)7(0)3(3)6(1)8(0)9(0)426578193497821356可以假设节点个数N较小的情况下满足条件，并且解只会占用前N个空格。然后用数学归纳法对每一颗子树进行归纳证明。第9页，共26页，编辑于2022年，星期一树的构造已知一个一维线形结构最开始所有位置为空。根据DFS序列，每次插入一个元素j，到第t(j)+1个空位置求出最终状态借助线段树或树状数组等数据结构可以将问题在O(N log N)时间复杂度内解决，空间复

5、杂度为O(N)看看转化后的问题：第10页，共26页，编辑于2022年，星期一小结通过对题目特点的分析，借助DFS序列的性质，对原问题进行转化。合理的使用数据结构，最终完整解决问题。第11页，共26页，编辑于2022年，星期一问题描述：N个士兵在进行队列训练，从左至右有M个位置。每次将军可以下达一个命令，表示为Goto(L,S)1.若队列L位置上为空，则士兵S站在L上。2.若队列L位置上有士兵K，则士兵S站在L上，并执行Goto(L+1，K)将军依次下达N个命令，每个士兵被下达命令一次且仅一次。要你求出最后队列的状态。（有可能在命令执行过程中，士兵站的位置标号超过M）士兵排队就是把就是把L位置及

6、其右方的一段士兵向右推移一格，为位置及其右方的一段士兵向右推移一格，为S腾出位腾出位置，然后置，然后S站在站在L上。上。第12页，共26页，编辑于2022年，星期一士兵排队Goto(4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)123456N=6 M=5一个简单的例子第13页，共26页，编辑于2022年，星期一士兵排队直接模拟的最坏时间复杂度为O(N2)，效率十分低下。使用平衡二叉树，可以得到一个O(N log(N+M)的算法。但平衡二叉树时间复杂度常数系数比较大，而且较难实现。不妨抛开纯粹模拟的思路，另辟蹊径。我们来进行一下初步分析：第14

7、页，共26页，编辑于2022年，星期一士兵排队先来看最基本的情况：Goto(2,1)Goto(2,2)12可见：如何高效处理插入带来的连锁移动是本题的关键！第15页，共26页，编辑于2022年，星期一NewGoto(2,2)NewGoto(2,1)士兵排队注意到上面的例子中1因为2的插入而向右移动了一格。我们要避免连锁移动，就是希望通过一个规则，使得士兵1能够直接插入到3号位置。我们可以先插入士兵2而不是士兵1，然后再将士兵1插入到第2个空位置空位置中。具体地说，定义：newgoto(L,S)命令，将S士兵插入到第L个空位置个空位置中。12Goto(2,1)Goto(2,2)第16页，共26页

8、，编辑于2022年，星期一事实上原Goto序列只要把(L,S)数对合理交换位置，就和NewGoto序列等价等价士兵排队12NewGoto(2,2)NewGoto(2,1)Goto(2,1)Goto(2,2)第17页，共26页，编辑于2022年，星期一士兵排队复杂一点的情况：Goto(4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)NewGoto(4,5)NewGoto(5,3)NewGoto(4,2)NewGoto(4,1)NewGoto(3,6)NewGoto(2,4)123456第18页，共26页，编辑于2022年，星期一B如果我们可以将G

9、oto序列的(L,S)数对，高效合理的改变顺序，转化为NewGoto序列，则模拟NewGoto命令就是上题最后转化成的一维线性填数问题。士兵排队有两条根本性的原则：如果A因B插入而被连锁移动。则和A,B有关的两条NewGoto命令，B要在A之前。如果A,B没有关联，而A最终位置在B之前，则NewGoto序列中，B要在A之前。B.AGoto(LA,A)Goto(LB,B)第LA个空位置.A第LA个空位置NewGoto(LB,B)NewGoto(LA,A).第19页，共26页，编辑于2022年，星期一士兵排队1234565 3 2 1 6 4 我们需要知道最终位置。我们需要知道谁被谁造成连锁移动。

10、我们无法直接构图。如果构造一个图，与A相关的NewGoto命令要在与B相关的之前，则A,B之间连一条边A-B，那么我们就是要获得这个图拓扑序。第20页，共26页，编辑于2022年，星期一3,4考虑利用两条基本性质，直接构造拓扑序。用并查集存储每个不相干的部分及单独构造单独构造(假设每个块互相不影响)的NewGoto序列。当两个块因为插入而要合并时，顺便将两个块的NewGoto序列合并。最后将所有未合并的部分的序列，根据位置位置在后的块序列上靠前的原则，合并完整的在后的块序列上靠前的原则，合并完整的NewGoto序列。序列。2 6 3 4 1 56士兵排队3214521,52,6,3,4NewG

11、oto(L1,1)NewGoto(L5,5)第21页，共26页，编辑于2022年，星期一士兵排队当士兵A直接插入到一个已经属于某一个块B的位置中时，就将与A相关的NewGoto命令插入B块的NewGoto命令序列首。当士兵A的插入引起了一个或者多个块相连时，则根据位置在后的块序列上靠前的原则位置在后的块序列上靠前的原则来对他们进行合并。用一个链表来存储单个部分的NewGoto序列，因为他只涉及插入到序列首，和首尾相接合并两个操作我们来具体讨论如何合并：.b1biABa1BakA,Ba1BakA63214521,53,42,6,3,4第22页，共26页，编辑于2022年，星期一士兵排队Goto(

12、4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)123456具体实现的例子：12,13,2,145,3,2,15,3,2,1,6,4第23页，共26页，编辑于2022年，星期一士兵排队根据Goto序列构造NewGoto序列。转化成前一题最终转化成的一维线性填数问题。使用线段树等工具在O(N log(N+M)时间内解决转化后问题。总时间复杂度O(N log(N+M)，空间复杂度O(N+M)。现在来整理整个算法：第24页，共26页，编辑于2022年，星期一总结通过适当的分析，应用不同的序，将两个截然不同的问题转化成了同一个问题。提示我们在平时做题时要充分挖掘题目的本质。同时大胆的尝试，去实现自己的想法。第25页，共26页，编辑于2022年，星期一第26页，共26页，编辑于2022年，星期一