资源描述：
《算法合集之《序的应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、序的应用长沙市雅礼中学龙凡基本的序41231244325344122425313443大小序12345671246753DFS序1247536拓扑序二分查找连通性问题动态规划序是数据之间隐藏的一种基本关系：序的应用使得一个问题得到直接解决（大多是交互式问题）应用序，挖掘题目的深层性质，使得问题得到转化。下面着重通过两个例子来探讨如何应用序来转化问题。树的构造问题描述：一棵含有n个节点的树，所有的节点依次编号为1,2,3,…,n，每个节点i有一个权值s(i)，也分别是1,2,3,…,n，并且各不相同。对于编号为v的节点，定义t(v)为v的后代中所有权值小于s(v)的节点个数
2、。现在给出这棵树及t(1),t(2),…,t(n)，请你求出这棵树每个节点的权值。树的构造已知T构造S426578193S497821356426578193T313100000为了理解题目我们来看一个实例：树的构造我们来考虑这个树的DFS序列：4265781933310100001(3)2(1)4(0)5(0)7(0)3(3)6(1)8(0)9(0)DFS序列的重要性质：所有的子孙都紧跟着该节点之后出现。树的构造由于权值分别是1,2,3…,n。我们不妨认为从左到右有N个格子，如果从左数第I个格子填入了节点J，则S(j)=i。42517863942657819331310
3、0000426578193497821356一组可行解左数第4个位置左数第7个位置树的构造不能漏填，也不能冲突。每个格子的左边，都恰好有t(i)个格子填入了自己的子孙。不能超出1…n的边界范围。如果我们按照DFS的顺序，依次填写节点。对于每个节点j的左边，则必须预留下至少t(j)个空格给权值比他小的子孙。所有的子孙都紧跟着该节点之后出现。看看“填”的时候的具体要求树的构造依次按DFS序填写每个节点时，对于节点J，给他的子孙恰好预留t(j)个空位，即j填在第t(j)+1个空格，就是可行解4251786394265781933131000001(3)2(1)4(0)5(0)7
4、(0)3(3)6(1)8(0)9(0)426578193497821356可以假设节点个数N较小的情况下满足条件，并且解只会占用前N个空格。然后用数学归纳法对每一颗子树进行归纳证明。树的构造已知一个一维线形结构最开始所有位置为空。根据DFS序列，每次插入一个元素j，到第t(j)+1个空位置求出最终状态借助线段树或树状数组等数据结构可以将问题在O(NlogN)时间复杂度内解决，空间复杂度为O(N)看看转化后的问题：小结通过对题目特点的分析，借助DFS序列的性质，对原问题进行转化。合理的使用数据结构，最终完整解决问题。问题描述：N个士兵在进行队列训练，从左至右有M个位置。每次
5、将军可以下达一个命令，表示为Goto(L,S)1.若队列L位置上为空，则士兵S站在L上。2.若队列L位置上有士兵K，则士兵S站在L上，并执行Goto(L+1，K)将军依次下达N个命令，每个士兵被下达命令一次且仅一次。要你求出最后队列的状态。（有可能在命令执行过程中，士兵站的位置标号超过M）士兵排队就是把L位置及其右方的一段士兵向右推移一格，为S腾出位置，然后S站在L上。士兵排队Goto(4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)123456N=6M=5一个简单的例子士兵排队直接模拟的最坏时间复杂度为O(N2)，效率十
6、分低下。使用平衡二叉树，可以得到一个O(Nlog(N+M))的算法。但平衡二叉树时间复杂度常数系数比较大，而且较难实现。不妨抛开纯粹模拟的思路，另辟蹊径。我们来进行一下初步分析：士兵排队先来看最基本的情况：Goto(2,1)Goto(2,2)12可见：如何高效处理插入带来的连锁移动是本题的关键！能不能通过特殊的处理来避免连锁移动呢？NewGoto(2,2)NewGoto(2,1)士兵排队注意到上面的例子中1因为2的插入而向右移动了一格。我们要避免连锁移动，就是希望通过一个规则，使得士兵1能够直接插入到3号位置。我们可以先插入士兵2而不是士兵1，然后再将士兵1插入到第2个空
7、位置中。具体地说，定义：newgoto(L,S)命令，将S士兵插入到第L个空位置中。12Goto(2,1)Goto(2,2)这就是上一题我们最后要实现的操作！事实上原Goto序列只要把(L,S)数对合理交换位置，就和NewGoto序列等价士兵排队12NewGoto(2,2)NewGoto(2,1)Goto(2,1)Goto(2,2)士兵排队复杂一点的情况：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
