序的应用.docx

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