国家集训队论文平衡规划

浅析一类平衡思想在信息学竞赛中的应用1平衡规划——浅析一类平衡思想在信息学竞赛中的应用福建省福州市第八中学郑暾【目录】摘要2关键字2正文2引言2应用平衡思想的几类问题3经典算法的非典型实现3例题一、警卫安排问题3例题二、Jackpot6效果优秀的非完美算法8例题三、追捕盗贼8复杂问题的简单化构造12例题四、数列维护12例题五、树的维护14总结17感谢18参考文献18附录18浅析一类平衡思想在信息学竞赛中的应用2【摘要】应用计算机解题的核心是算法设计。但算法设计方面涉及的领域十分丰富。我们不能奢求能完美地应用所有的算法，所以我们关注的通常是如何合理运用已学知识，并在所掌握算法间构建一种平衡，在限定的时间内尽可能多地解决问题。本文尝试讨论一类平衡思想应用于算法构造、算法实现的模式。【关键字】平衡思想、平衡点、时空效率、编程复杂度【正文】一、引言平衡通常指物体或系统的一种状态。处于平衡状态的物体或系统，除非受到外界的影响，它本身不会有任何自发的变化。多种状态达到平衡通常是我们所追求的目标。平衡思想是一种奇妙的思想，它的应用十分广泛。在算法设计，数据结构设计甚至程序设计中都能发现它的身影。计算机竞赛就是一场博弈，寻找这场博弈中的平衡点，合理应用平衡思想辅助算法设计与程序实现，往往能起到化腐朽为神奇的作用。在信息学竞赛中，平衡思想通常有以下几个方面的运用：1、博弈问题。有许多博弈类问题都可以转化成寻找平衡点的问题。2、数据结构的构建。每种数据结构都能以优秀的性能支持某些操作，合理选择应用数据结构，往往能通过略微提高一些操作的复杂度，降低大多数操作的复杂度，在不同操作的效率之间构建一种平衡，以达到优化的目的。3、时间效率vs空间效率。这类问题是我们经常遇到的问题。这类问题通常有这样的特性，我们能找到时间效率（或空间效率）十分优秀的算法，但代价是空间效率（或时间效率）极端低下。如何合理设计算法，组织数据，平衡二者的关系是解决这类问题的重点。4、时空效率vs其他。如果面对难题难以设计出优美的算法，又或者设计浅析一类平衡思想在信息学竞赛中的应用3了优秀效率的算法，却无法实现或难以实现，就会出现非常尴尬的局面。合理应用平衡规划解决这类问题，往往能收到意想不到的效果。而这类问题也正是本文所要重点探讨的问题。下文将试图论述运用平衡思想解决这类问题中的三种常见模式：经典算法的非典型实现，效果优秀的非完美算法，以及复杂问题的简单化构造。二、应用平衡思想的几类问题1、经典算法的非典型实现。大多数经典算法通常是为很多人所熟知，并且能够熟悉运用。经典算法通常也有很多不同的实现方法。例如拓扑排序，如果数据范围比较大，通常使用算法复杂度为O(n)的程序，但是如果范围比较小，一个不超过10行的)(2nO的程序可以使代码看起来更为简洁。而不同的实现方法中，哪怕只是细微的不同，实现后的性能与效率也可能有很大的差别。更进一步，有些算法虽然堪称经典，但是无论是思考复杂度还是实现复杂度都相对颇高，在考场上来说，使用一些相对简单实用的方法无疑是一种不错的选择。例题一、警卫安排问题(ural1099)题目描述：给定若干警卫间搭档关系，要求成对给警卫安排保卫工作，求能够安排警卫的最大值。（警卫人数不超过222）初步分析：题目描述很简单，稍加分析后我们很容易看出来，这题的本质其实是要求我们求出任意图的最大匹配。任意图的最大匹配的经典算法是应用带花匈牙利树，时间复杂度为)(3nO，对付这道题来说是绰绰有余的。但是带花树本身比较复杂，思维复杂度与编程复杂度较高，而且实现起来很容易退化，考场上有限的时间内难以完成。于是我们尝试考虑替代算法予以解决。解法分析：浅析一类平衡思想在信息学竞赛中的应用434521678图一解决二分图最大匹配的时候，主要过程是不断寻找交错增广树来调整。那么这么做对于任意图是否可行？答案是否定的。考察右边这张图（图一）。图中粗线表示当前状态下已匹配边，虚线表示未匹配边。若我们当前找的增广树如图二所示，那么我们就无法找到一条增广路。但实际上，存这样的一条增广路：876321。为了找到增广路，我们可以采用搜索的方法，但这样寻找增广路复杂度过高。我们注意到，采用调整增广轨的方法，如果一个点之前已经被匹配到，则之后无论如何调整，这个点始终能被匹配到。因此，对于一个待匹配点，是否能找到一条以它为起点的增广路是优化解的关键。而是否能找到一棵增广树又很大程度上依赖于之前找寻的情况，若要设计数据使得无法找到增广树通常又依赖于特定的扩展顺序。这启发我们采用随机扩展顺序的方法来尽量避免形成类似图一的特殊局面。笔者的程序中生成了两个随机序列，一个作为点的初次访问序，一个作为点的拓展顺序，然后直接使用一开始所说的寻找交错树的方法来扩展。同时，采用多次随机运行的方法提高最优解的出现概率。但是作为随机贪心算法，除了拿到AC之外，我们更应该关注这个程序通常的运行情况如何。上述算法中，在ural点数限制仅仅为222以下的情况下，通常运行次数却要设定为20至50才能基本上保证AC。相对于数据本身，这个运行次数还是比较大，说明算法本身具有比较大的不确定因素，以及出最优解概率并不是很高。所以我们需要进一步优化以提高一次运行的最优解出现概率。进一步优化上述解法中曾提到，采用调整增广轨的方法，如果一个点之前已经被匹配到，则之后无论如何调整，这个点始终能被匹配到。它带来的另一个信息是，若一个点之前未被匹配到，那么在本轮搜索中，这个点最终将很可能保持未匹配的状态。因此影响最终结果的，往往是某个本应该被匹配到的点因为之前增广树的查找失3452167图二浅析一类平衡思想在信息学竞赛中的应用5败而被放弃匹配。初始算法解决这个问题的方法是全局重新搜索，所以常常出现为了一个点而全部重来的尴尬场面。其实这是舍近求远。我们完全可以换一个扩展顺序，对于当前未找到交错树从而无法匹配的点，直接重新搜索一棵交错树！当然大部分的图都无法实现完美匹配，所以类似运行次数的限制，我们需要设置一个失败次数上限。当为一个未匹配点寻找匹配点时，只有失败次数超过了这个上限才放弃。那么失败上限次数应该设置为多少比较好？进一步的，这个方法实现起来究竟效果如何呢？为此笔者进行了一系列的实验，得到了如下的实验数据表：运行次数-失败上限5-55-1010-110-1020-120-1050-1Accepted90%100%0%90%60%0%100%Wronganswer10%0%100%10%40%0%0%Timelimitexceeded0%0%0%0%0%100%0%平均AC时间0.07610.1471--0.29600.0385--0.0795实验的运行平台是Ural1099的测试，时限是0.5秒。表头的N-M表示程序将重复运行N次，失败上限设置为M，例如5-5表示程序将重复运行5次，失败上限设置为5。实验表明，这个方法能显著地提高一次运行的最优解出现概率。从表中数据可以看出，初始算法直到20-1才有50%以上的AC率，而优化后的方法将失败上限设置为5就可以让仅仅重复运行5次的AC率达到了90%。当然，这种方法同样存在一定的随机因素，加之Ural1099的数据比较强大（从数量到质量），所以出现了如表中5-10是100%AC但是10-10却只有90%的AC率的情况。但正所谓有得必有失。优化后的方法有着极高的准确率，但同时时间效率并不高。实验中，5-5的时间已经逼近了50-1的时间。虽然相对于时限来说还是比较轻松，但是其增长还是较可观的（20-10的全部超时就可以说明这一点）。实际上，虽然理论上时间复杂度仅仅是多一个所设置的失败上限的常数，但由于将进一步优化中需要大量地使用了随机函数，而生成随机函数的常数比较大，造成了实际程序的常数较大，拖累了时间。所以，两种算法都有其各自的优缺点，这就需要我们根据题目的给出的信息，根据实际算法的需求来进行选择。进一步扩展：随机搜索序和设置失败上限的作用并不局限于此。浅析一类平衡思想在信息学竞赛中的应用6对于随机搜索序，表面上看是根据克制数据或克制情况的顺序依赖性1，应用随机的顺序来进行回避。其实其本质是：通过设置一些随机权值，以改变一个当前状态的属性，从而回避特殊情况的生成（例如本题是回避克制数据的生成）。我们常用的Treap，随机快排（随机选择比较变量），其本质也是如此。设置失败上限则是随机搜索序关于准确率的一个优化。随机算法不可避免还是有可能无法得到我们理想的状态或结果（例如本题依然可能找不到存在的增广路，又例如Treap并不完全平衡）。随机搜索序通常是全局重新运行来提高最优解的出现概率，而设置失败上限则是通过对于局部问题的精益求精来强化全局目标情况出现概率，常见的应用有大素数的测试等。小结：对于这道题，两种方法都可以比较轻松地通过。考虑到数据范围并不大，为了追求准确率可以增加参数上限，或者为了保证时间效率压缩参数上限，这需要我们根据实际情况合理平衡二者之间的关系。以准确率为代价我们得到了随机贪心算法，以时间复杂度为代价我们得到了准确率的进一步的优化，但不论是哪种方法，都能有效地降低了思维与编程复杂度，达到了二者之间的相对平衡。例题二、Jackpot（PKU2103）题目描述：等概率选择任意整数，若其能被p1,p2,p3...pn中至少一个数整除，那么称当前情况为胜利局面。给定p1,p2,p3...pn，（n=16）求得到胜利局面的概率（用最简分数表示）。初步分析：本题看起来十分复杂。题目作为参考，给了一个比较复杂的计算概率的式子。12limkSPkk其中P表示最后结果的概率，kS是-k到k之间至少能被给定的p1,p2...pn其中一个数整除的个数。但如果直接用这个式子比较复杂。所以我们设计了下述算法代替。注意题目1即特殊情况依赖于一定的顺序，例如本题是克制数据的生成依赖于一定的搜索顺序。浅析一类平衡思想在信息学竞赛中的应用7中涉及高精度计算，但本题时限卡的比较紧，如果用普通的高精度容易超时，巨大的常数无法忍受。如何合理优化常数成为了解决问题的关键。解法分析：本题其实是数学题。题目等价于求取数区间为1~lcm(p1,p2,p3...)的时候的概率，但由于1=pi=109，使得最小公倍数可能很大，直接扫描显然不现实。注意到给定的数最多只有16个，所以我们可以应用容斥原理求出区间中可以得到胜利局面的数的个数。由于题目涉及了许多求gcd，lcm的高精度，一个小技巧是开一个素数列表，当前状态以纪录素数的次数的方式记录，最后再还原成原来的整数。主算法的设计与实现并不困难。所以在主算法相同的情况下，高精度算法的实现优劣就成了左右程序效率的关键。本题涵盖了许多的高精度算法，而几乎每一次运算都要使用到高精度运算。其中使用最多的有高精度乘以单精度与高精度加减法。高精度运算有一个通用的优化：压位。在longint范围内通常是压4位（即万进制），在int64则可以压8位，而压位能有效地减少高精度数组的长度，从而提高效率。注意到程序实现时要大量使用div与mod运算，这两个运算的常数是比较大的。那么是否有办法绕开这两个运算呢？答案是肯定的。我们注意到，除法与取模的运算是为了进行压位处理的操作，（注意到若是高精度乘法，中间结果可能比较大，所以用while递减实现取模的效果更差）。但无论压位与否，我们的所采用的万进制等进行压位实质上还是沿用着通常的十进制的思维模式。但计算机处理二进制运算（位操作）显然要比十进制常数小。所以我们可以跳出思维惯性，采用二进制压位，这样，一些取模或者除法运算就能用位操作很好地实现。下面是两个程序主要部分的伪代码的对比。（高精度与单精度乘法）采用n10进制压位的乘法采用n2进制压位的乘法fori1toa[0]+1dobeginpa[i]*b+pdivn10;a[i]pmodn10;fori1toa[0]+1dobeginpa[i]*b+pshrn;a[i]pand(n2-1);end;浅析一类平衡思想在信息学竞赛中的应用