论文--问题中的变与不变.doc

问题中的变与不变【摘要】信息学竞赛中很多试题本质上都是对变量进行求解或者维护的过程。而有时候变量有很多种变化,单纯的维护变量往往导致时空复杂度的低下。而如果能在变量的变化里找出其中“不变”的常量,往往能将问题迎刃而解。本文简单的介绍了几种在变量中找出“不变”的技巧,使得问题得到简化。【关键字】变变量不变常量维护【引言】变量在信息学中是最常见的,最基本的有循环变量,累计变量,决策变量。维护这些变量也是信息学中最基本的操作。信息学中关于变量的维护也有很多数据结构,像平衡二叉树,栈,队列等等。然而有些问题规模很大,仅仅是所需要的变量进行维护的总操作数就会达到无法承受的时空复杂度。于是我们就要对变量进行化简,找出其中的有用信息,从而使得维护这些变量的操作数更少,甚至将一些变量化成“常量”。下面就让我们具体看看这类技巧在信息学中的应用。【正文】将有用的变量放在一起看成一个集合,利用特殊的性质,进行一系列的操作,比如加发,乘法,是将变量转化成常量的最常见的方法。下面我们就看这样的一道问题。例1:蚂蚁ants[1]一些蚂蚁以1cm/s的速度在长度为lcm的线段上爬行,爬到线段端点就会掉下去。当两只蚂蚁相遇,就会立刻掉头返回。已知l和一开始每只蚂蚁的位置,但不知道它们的方向,求它们最早何时全部掉落,最迟何时全部掉落。最多1,000,000只蚂蚁。分析:蚂蚁一出来我们只知道位置,不知道方向。如果单纯枚举方向的话,光是各种方案的可能性就有21000000种,这个一个无法承受的数字。因此不可能去枚举每个蚂蚁的方向,不如先从简单的问题着手。假设我们已知了蚂蚁初始的方向后,接下来的任务就是模拟所有的蚂蚁相遇和掉落的过程,求出最后一个掉落的时间。在这个过程中,最复杂的变量就是每只蚂蚁的方向了,明显在最坏情况下相遇次数可能达到N2级别,仅仅是维护每只蚂蚁的方向和位置都是不能满足题目的时间复杂度的要求的。我们从细节开始考虑问题:首先考虑题目中最基本的一个操作也就是2只蚂蚁碰头的情况:假设一只蚂蚁A从左向右爬行,在X点的时候遇到了另一只从右向左的蚂蚁B后返回。同时蚂蚁B也从X向右返回。↓ ↓图12只蚂蚁相撞后的情况将这2只蚂蚁有用的信息也就是速度(是向量)和当前位置记录下来一起构成集合U,也就是。在蚂蚁A和蚂蚁B相遇前瞬间一刻,而在蚂蚁A和蚂蚁B相遇后瞬间一刻,我们发现U=U’,也就是说虽然对于每只蚂蚁,它的速度发生了改变,但是把这2只蚂蚁放在一个集合看的话,这个集合并没有发生变化。或者说,在同一个集合内的蚂蚁相遇,这个集合是不会变的。于是把所有的蚂蚁看成一个大集合。根据上面说提到的,在这个集合V内的任何相遇对于集合V都没有影响。同时我们通过集合V可以知道,虽然每只蚂蚁掉落的时间Ti无法求出,但是所有的Ti所构成的集合T我们是可以求出来的。事实上就是T={第I只蚂蚁按初始方向走到一端点的时间|1≤i≤N}。得到了这个有效的结论后,我们回到原来的问题:它们最早何时全部掉落,最迟何时全部掉落。先考虑最早何时全部掉落:根据T={第I只蚂蚁按初始方向走到一顶点的时间|1≤i≤N},我们贪心的让每只蚂蚁都朝离自己最近的端点爬行,即可保证T中最大值最小。同理最迟何时全部掉落的情况就是每只蚂蚁朝离自己最远的端点爬行,即可保证T中最大值最大。最终我们得到了一个时间复杂度为O(N)的算法了。这已经是理论的下限了。小结通过集合的概念,我们将原来要维护每个蚂蚁的方向,位置这些规模庞大的变量转化成一些“常量”。而通过这些“常量”不用维护就可以直接得出最终结果。集合操作在这类变量转化成“常量”的问题有极广泛地运用,常常可以利用题目给定的条件,来构造集合,然后利用集合内元素之间的特殊性质来判断无解或者优化算法。通过这道题目我们也能看到,仔细观察,从细节入手,寻找变量之间的联系,才能找到将变量转化成“常量”的方法。例2:NavigationGame[2]这里有一个N行M列的方阵,第N行象征着这里,第1行象征着海那边的彼岸。这中间的N-2行象征着你所期盼的大海。你的目标是,控制一艘船,从这里的任意一个停泊处(用“H”表示),经过最短的航行时间到达对岸的任意一个停泊处。只有这样,你才可以通过这个通道。你的船只能向左,向右或向上前进,一次一格,而且除非登陆(这时你必须到达一个停泊处,从而结束你的游戏),你是不能驶向陆地的。记住,人生没有回头路。因此,一旦你离开一个格子,就永远也无法返回。向着目标航行永远是一件令人愉快的事情。因此向上航行只需要消耗一个单位的时间。但是,看似原地打转的左右方向的航行会让人厌倦。如果某次左右航行之前你已经连续进行了x次左右航行,你这次左右航行所消耗的时间就是x+1个时间单位。海上你可能会遇到:O:障碍物。障碍物占据的格子,你永远也不会到达。F:命运之轮。经过这里,你的