算法合集之问题中的变和不变

《算法合集之问题中的变和不变》由会员分享，可在线阅读，更多相关《算法合集之问题中的变和不变（10页珍藏版）》请在装配图网上搜索。

1、问题中的变与不变 陈雪 长沙市雅礼中学 410007【摘要】 信息学竞赛中很多试题本质上都是对变量进行求解或者维护的过程。而有时候变量有很多种变化，单纯的维护变量往往导致时空复杂度的低下。而如果能在变量的变化里找出其中“不变”的常量，往往能将问题迎刃而解。本文简单的介绍了几种在变量中找出“不变”的技巧，使得问题得到简化。【关键字】变 变量 不变 常量 维护【引言】 变量在信息学中是最常见的，最基本的有循环变量，累计变量，决策变量。维护这些变量也是信息学中最基本的操作。信息学中关于变量的维护也有很多数据结构，像平衡二叉树，栈，队列等等。 然而有些问题规模很大，仅仅是所需要的变量进行维护的总操作数

2、就会达到无法承受的时空复杂度。于是我们就要对变量进行化简，找出其中的有用信息，从而使得维护这些变量的操作数更少，甚至将一些变量化成“常量”。下面就让我们具体看看这类技巧在信息学中的应用。【正文】 将有用的变量放在一起看成一个集合，利用特殊的性质，进行一系列的操作，比如加发，乘法，是将变量转化成常量的最常见的方法。下面我们就看这样的一道问题。例1：蚂蚁ants1一些蚂蚁以1cm/s的速度在长度为lcm的线段上爬行，爬到线段端点就会掉下去。当两只蚂蚁相遇，就会立刻掉头返回。已知l和一开始每只蚂蚁的位置，但不知道它们的方向，求它们最早何时全部掉落，最迟何时全部掉落。最多1,000,000只蚂蚁。分析

3、：蚂蚁一出来我们只知道位置，不知道方向。如果单纯枚举方向的话，光是各种方案的可能性就有21000000种，这个一个无法承受的数字。因此不可能去枚举每个蚂蚁的方向，不如先从简单的问题着手。假设我们已知了蚂蚁初始的方向后，接下来的任务就是模拟所有的蚂蚁相遇和掉落的过程，求出最后一个掉落的时间。在这个过程中，最复杂的变量就是每只蚂蚁的方向了，明显在最坏情况下相遇次数可能达到N2级别，仅仅是维护每只蚂蚁的方向和位置都是不能满足题目的时间复杂度的要求的。我们从细节开始考虑问题：首先考虑题目中最基本的一个操作也就是2只蚂蚁碰头的情况：假设一只蚂蚁A从左向右爬行，在X点的时候遇到了另一只从右向左的蚂蚁B后返

4、回。同时蚂蚁B也从X向右返回。 图1 2只蚂蚁相撞后的情况 将这2只蚂蚁有用的信息也就是速度 (是向量)和当前位置记录下来一起构成集合U，也就是。 在蚂蚁A和蚂蚁B相遇前瞬间一刻， 而在蚂蚁A和蚂蚁B相遇后瞬间一刻， 我们发现U=U，也就是说虽然对于每只蚂蚁，它的速度发生了改变，但是把这2只蚂蚁放在一个集合看的话，这个集合并没有发生变化。或者说，在同一个集合内的蚂蚁相遇，这个集合是不会变的。 于是把所有的蚂蚁看成一个大集合。 根据上面说提到的，在这个集合V内的任何相遇对于集合V都没有影响。 同时我们通过集合V可以知道，虽然每只蚂蚁掉落的时间Ti无法求出，但是所有的Ti所构成的集合T我们是可以求

5、出来的。 事实上就是T=第I只蚂蚁按初始方向走到一端点的时间|1iN。得到了这个有效的结论后，我们回到原来的问题：它们最早何时全部掉落，最迟何时全部掉落。先考虑最早何时全部掉落：根据T=第I只蚂蚁按初始方向走到一顶点的时间|1iN，我们贪心的让每只蚂蚁都朝离自己最近的端点爬行，即可保证T中最大值最小。同理最迟何时全部掉落的情况就是每只蚂蚁朝离自己最远的端点爬行，即可保证T中最大值最大。最终我们得到了一个时间复杂度为O(N)的算法了。这已经是理论的下限了。小结通过集合的概念，我们将原来要维护每个蚂蚁的方向,位置这些规模庞大的变量转化成一些“常量”。而通过这些“常量”不用维护就可以直接得出最终结果

6、。 集合操作在这类变量转化成“常量”的问题有极广泛地运用，常常可以利用题目给定的条件，来构造集合，然后利用集合内元素之间的特殊性质来判断无解或者优化算法。 通过这道题目我们也能看到，仔细观察，从细节入手，寻找变量之间的联系，才能找到将变量转化成“常量”的方法。例2：Navigation Game2这里有一个N行M列的方阵，第N行象征着这里，第1行象征着海那边的彼岸。这中间的N-2行象征着你所期盼的大海。你的目标是，控制一艘船，从这里的任意一个停泊处（用“H”表示），经过最短的航行时间到达对岸的任意一个停泊处。只有这样，你才可以通过这个通道。你的船只能向左，向右或向上前进，一次一格，而且除非登陆

7、（这时你必须到达一个停泊处，从而结束你的游戏），你是不能驶向陆地的。记住，人生没有回头路。因此，一旦你离开一个格子，就永远也无法返回。向着目标航行永远是一件令人愉快的事情。因此向上航行只需要消耗一个单位的时间。但是，看似原地打转的左右方向的航行会让人厌倦。如果某次左右航行之前你已经连续进行了x次左右航行，你这次左右航行所消耗的时间就是x+1个时间单位。海上你可能会遇到：O：障碍物。障碍物占据的格子，你永远也不会到达。F：命运之轮。经过这里，你的命运会从此逆转。我了解你的命运有多么不幸。因此，你必须在航行途中经过奇数次命运之轮，才能安全到达彼岸。B：祝福石。走到这里是不需要时间的。S：暴风雨的咒

8、符。走到这里所需的时间是正常情况的两倍。1012132112311HHOBFFSOOOOOOOOOFOH 图2 例2的一个样例说明数据范围约定: N,M1000。分析：根据题目的要求，不能走回头路，同时只能向上或者向右或者向左，于是我们考虑使用动态规划：设表示从起点到(I,J)且走过的命运之轮的次数为T的最少的代价(T表示奇偶性)。设表示从(I+1,J)到(I,J)的代价。 于是得到状态转移方程:（其中表示从(I,K)移动到(I,J)按照题目所给要求的代价，且(I,K)到(I,J)之间没有障碍物,T=T xor (I,K)到(I,J)之间F个数）假设如果没有题目所限制O,S的限制，那么。首先我

9、们只考虑从左往右走。那么状态转移方程可以写成: 不妨另=,=。状态转移方程就变成了 考虑Ui的最优决策K，那么满足(ikl)： 另,。把,画在平面坐标轴上，根据上面的式子有(,)-(,)之间的斜率小于i的时候，决策k比决策L更优。事实上这是一个经典的斜率优化动态规划的模型3。根据一般性我们知道维护一个队列表示(,)的凸包中的下凸部分即可在均摊O(n)的时间内求出最优值。具体操作如下：用stack队列来表示这个凸包的下凸部分。同时设队首指针st和队尾指针en。根据Stack队列维护的是凸包的下凸部分，那么满足下面的性质2.1:1. 2. -的斜率 -的斜率. -的斜率具体操作如下：从小到大枚举I

10、。对于当前I，如果满足-的斜率k。显然，无论(I,J)-(I,K)之间无论是B或者S，变量都能表述成一个关于(J-K)的二次函数。不妨设。当然a和b都是需要维护的变量。先考虑如何维护。假设K已经固定，当前。下面观察。1.(I,J+1)上不是B也不是S: 有2.(I,J+1)上是B,不需要时间: 有3.(I,J+1)上是S,时间要加倍: 有根据上面所说，我们及时更新a,b就能得出新的。同时我们也能看到a的意义就是在(I,K+1)-(I,J)这一段中，。我们看另一种情况:如果J固定，而K发生变化的时候，的维护。重新扫描一遍肯定会导致算法效率低下。而且变量一共有O(n3)的级别，即使我们能在均摊O(

11、1)的时间内算出所有时间复杂度依然是O(n3)的。于是考虑优化算法，尽量在短时间内算出对我们有用的信息。假设当前已知，而且已知的a和b。下面我们要求。既然重新求没有太好的方法，我们干脆做一个大胆的猜想那就是希望改变一些变量值使得的a和b能直接满足的要求。把的代价分为2个部分，一部分表示从(I,K)出发在 (I,K)-(I,L)这一段的代价，另一部分表示在(I,L+1)-(I,J)这一段的代价。而第1部分的代价显然就是。第二部分当中既有对我们有用的代价,同时也有一部分的多余代价(从L出发比K节省的时间)。于是我们得到于是我们只要给就无需改变a和b。而这样做会不会对产生影响？我们分析由- 的过程，

12、就能知道这样做是没有任何影响的。而这样做的好处就是能把用一种更具体的形式给出。而不是一个虚拟的变量。实际上为了方便处理我们可以另。(b就是上文中的b,也可以看成是的最优决策k，中的那个b)这样原状态转移方程就可以写成(虽然a,b是变化的，但是对于单独的一个，a,b是固定的)。仿照没有B和S时的思路，设最优决策K，同时观察决策L。 另，。还是仿照上面的思路维护一个队列表示所构成的凸包的下凸部分。具体操作同没有B和S的情况类似，这里就不重复了。但是这样是否依然能保证正确性？ 每次J会增加1，而无论(I,J)上是B或者S，a只会发生1的变化。于是右边的改变量依然能保证是非负的。所以正确性显然。而从左

13、到右反过来考虑即可。总的时间复杂度:O(行数*(列数+队列的操作数)=O(NM)。小结 这道题目中，由于特殊的条件的约束，如果使用其他方法维护cost(I,K,J)中的a,b反而令问题更加复杂。于是大胆猜想，通过调整其他变量使a,b不变，从而在后面的问题中，利用队列和斜率将算法优化到O(NM)。例三：Circular Railway4在一条长度为L的环形轨道上有N个A类点，N个B类点。现在要你安排一种方案使得这N个A类点和N个B类点一一匹配。并且所有匹配点之间的最短距离（指在轨道上）和最小。数据范围: 1 n 50000, 2 L 109分析：首先将N个A类点按顺时针排序后设他们的坐标为,.。

14、 将N个B类点按顺时针排序后设他们的坐标为,.。(同时另) 显然问题实际上就是一个二分图的最小权匹配。但是最小权匹配最坏情况下是O(n4)的时间复杂度，对于题目的数据范围，肯定是不能满足要求的。 仔细分析我们就能发现最小权匹配时有一条重要的性质: 性质3.1: 2条匹配边肯定不会相交。 图3 性质3.1的证明 反证：如果出现了2条匹配边-和-相交，那么我们交换,的匹配使得-和-肯定可以让匹配的总权值最小。（如图3所示） 按照性质3.1，我们可以知道最小权匹配必然满足下面的条件： 不妨另匹配的点是，然后 (1 2. -L/2 2.当最优，此时和要满足条件：1. 2. -L/2 3当最优，此时和要

15、满足条件：1. -L/2 4当最优，此时和要满足条件：1. -L/2 通过上面的分析发现只与当前的和有关，既然关于变量无能为力，那么我们不妨把注意力放到和上来，不妨另。下面考虑对的影响，也就是函数。 根据上面的分析，我们知道当 1当-L/2有， 2当L/2-0有， 3当L/2-0有， 4当L/2-有， 我们把注意力放到变量上来，通过上面的讨论，可以知道虽然还是个变量，但是与相比，当j从1递增到N这个过程中最多有4种情况，事实上1,4不会同时出现，只有3种。也就是说可以看成是几乎不变的“常量”了。 同样的方法分析最多也只有4种变化。 现在我们从小到大枚举和A1匹配的点Bk后，其他的点按顺序一一匹

16、配，现在的总代价。 当k变化的时候，我们只看的变化，把放到一边。根据上面的分析，在我们从1到n枚举K的过程中，每一个,最多只会变4次。而我们可以通过预处理知道对于每个，变到是在K=变成K=+1时改变的，变到是在K=变成K=+1时改变的，变到是在K=变成K=+1时改变的。同理也可以通过预处理知道每个变量它发生改变的时间。不妨把,发生改变看成一次事件，可以知道事件总数肯定不会超过8n。假设我们已经通过预处理知道每件事件发生的时间（每次事件的时间x指事件是在k=x变成k=x+1发生的）。而通过这些事件我们就可以即时维护Sum。在Sum达到最小值时，就是我们要求的答案了。整个算法的流程如下： 1.将A

17、i和Bi排序。 2.预处理求出每个事件发生的时间。 3.从1到N枚举K，同时通过hash表找出哪些事件发生在这个时刻，同时维护Sum。 4.输出Sum的最小值。下面我们考虑预处理。预处理求，实际上就是要我们求对于每个Ai情况所对应的J的范围。而根据和的有序性，我们用指针就能维护情况所对应的J的范围。时间复杂度分析：O(排序复杂度+预处理+事件总数)=O(nlgn+n+8n)=O(nlgn) 回顾整个过程，我们发现只要牢牢把握住问题的实质，抓住最重要的变量总代价，进而把每项分开看成2个不相干的部分，对 2个“常”量,分别进行讨论求值，最终将算法优化到了一个满意的时间复杂度。【总结】 本文简要的举

18、出了3道例题，介绍了在信息学中，将变量化成“不变”的技巧。实际上，这种技巧在很多地方中都有建树。本文限于篇幅，介绍了三种比较典型的方法。从这些题目中也能看到，这种技巧的运用远不是简单的化简，有些变量之间的关系存在的很隐蔽，这就需要我们通过仔细观察，大胆猜想，深入分析才能找到合适的“常”量。 【参考文献】1 zju online judge 2376 ants. 2 pku online judge 2841 navigation game. 3 汤泽. 浅析队列在一类单调性问题中的应用.2006集训队论文.4 sgu online judge 313 circular railway. 5 刘汝佳,黄亮.算法艺术与信息学竞赛. 清华大学出版社.2003