资源描述：
《算法合集之《序的应用》68353》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、序的应用长沙市雅礼中学龙凡【摘要】信息学竞赛的本质是对数据进行挖掘，而“序”是隐藏在数据Z间的一种常见的但却难以发现的关系。如果能够在解题的过程屮找出题目屮隐藏的序关系，往往题目便可以迎刃而解。本文重点讨论如何在复杂的数据关系中发现和构造适当的序，使得问题获得简化和解决。【关键字】数据关系、序、树、DFS序列、图、拓扑序列【引言】信息学中序的应用很广泛，最基本的有基于大小序的二分查找算法、基于拓扑序的有向无环图的动态规划。而为了得到这些序，我们有相应的快速排序算法、和拓扑排序算法。图、树、线性以及集合等等，
2、这些不同的数据关系，有着与之对应的不同的序。而同一种数据关系，在不同的意义下，有着不同的序。比如有向图在遍历和深度优先的意义下冇DFS序，而在前后依赖关系的意义下冇着拓扑序。序本身并不一定是线性的，拓扑序就不是严格线性的序。在繁杂的数据屮，找到对我们有价值的序，并加以合理的应用，便是我们的课题。【正文】一.通过“序”使得问题解决的例了很多交互式题目，如果能够找到合适的序，根据序的特性来进行交互，往往能够使得问题得到很好地解决。我们来看这样一个例子：方格:有一个N*N(1〈二NU2003)的点阵,相邻点Z间会
3、有一条带整数权w的有向'_弧(l<=w<=500000)o并且,从左上角的点(v^).1.2.到某一点的所有路径的直度(途经的所有弧的•"权之和)都相等。23'每次可以提问某个点(x,y)到同行最右边1t*的点离他的距离,及同列最卜•边的点离他的距•2a.3*离。现在耍你找到一个点,使得左上点到他的~距离为给定的整数Ld<=L<=2000000000)o最542多允许提问6667次(你最开始仅仅已知N、L)°▼1▼1♦•——-•——一•我们首先可以否定一种最简单的想法，即把每条边的t度都通过询问+解方程计算
4、出来。因为边的总数是2(N-)N,而我们仅仅可以从“并且,从左上角的点(v,,})到某一点的所有路径的长度(途经的所有弧的权Z和）都相等。”这句话屮得到（N-1尸个方程（除了对于每个非左、上边缘之外的点存在一个其左上点到该点的两条路经相等，其他的都可以通过这些方程加减得出）也就是说至少还要询问2（N-1）N-（N-1尸="2-1次。而当N二2003的时候，6667仅仅相当于3N左右。这是不可能的！不妨从题目的耍求入手：题目仅仅要我们找到一个点，他到左上角点的距离为L。也就是说我们并不关心每条边的权值，而只
5、关心每个点的距离。我们不妨把每个点到左上角点的距离叫做每个点的权值。有一个很重要的事实即：每个点的权值,都比处在他右下方位的点的权值小。这是本题最基本的序，但是它并不是很好直接利用。但是它让我们不得不思考，既然左上到右下是依次变大，那么左下到右上乂有什么性质呢？从直观上感觉权值应该基木誉/多，那么我们是不是可以先找到一个最左下的权值接近L的点，然后依次沿着右上方向找过去呢？以上是一个非常含糊的思路。最左下的权值接近L的点，具体來说：我们先从最左边一列，向下找，找到一个点，他在最左边一列，且他的权值刚好小于L
6、。（即这个点的下方那个点就大于L了）然后顺着这个点往右找到最接近L的同排点S,这个点就是我们最初检查的点。我们来考察这个点的性质：m2-4亠亠一亠1.由基本的序，我们可知1区域内不存在解。2・由我们找的起始点的定义“且他的权值刚好小于L”,可以知道2,3区域内不存在解。也就是说：解只存在于4号区域中。那么我们来讨论红色点的权值和L的大小关系：1.相等：也就是说，这就是解。2.大于L：根据基木的序，我们可以知道所有原来在4区域，并且和红色点同行的都不可能是解（都在右方）。也就是说我们可以向上移动，转而检杳紫色
7、的点。3.小于L：根据基本的序，我们可以知道所有原来在4区域，并且和红色点同列的都不可能是解（都在上方）。也就是说我们可以向右移动，转而检查绿色的点。我们始终保持了仅在4号区域——也就是检查的点的右上方存在解的性质。并且不断把检杳的点向右上方移动，缩小范围，直到找到解。最开始找起始点的时候，使用两次二分法，那么最坏情况下总共需要检查的点的个数是：21og2n+2/?,当N最大吋也小于6667,可以满足题口要求。通过一个简单、基本的序，并针对它的特点大胆的设计算法的基木思路。使得我们成功地解决的这道题目。这也
8、捉示我们不要忽视一些题目内在简单、基本的性质。二、通过应用“序”简化问题的例子先看一道题目：树的构造:一棵含有n个节点的树,所有的节点依次编号为1,2,3,n,每个节点7冇一"权值s（v）,也分别是1,2,3,.小。对于编号为7的节点,定义为丫的后代中所有权值小于v的节点个数。现在给出这棵树及t⑴,t（2）,t（3）,…,tg,请你求出这棵树每个节点的权值。（多解任意输岀一组解）这道题目看似难以下手，但是只要抓住
