平衡规划
——浅析一类平衡思想在信息学竞赛中的应用
福建省福州市第八中学郑暾【目录】
●摘要 2 ●关键字 2 ●正文 2
◆引言 2
◆应用平衡思想的几类问题 3
●经典算法的非典型实现 3
?例题一、警卫安排问题 3
?例题二、Jackpot 6
●效果优秀的非完美算法 8
?例题三、追捕盗贼 8
●复杂问题的简单化构造 12
?例题四、数列维护 12
?例题五、树的维护 14
◆总结 17 ●感谢 18 ●参考文献 18 ●附录 18
【摘要】
应用计算机解题的核心是算法设计。但算法设计方面涉及的领域十分丰富。我们不能奢求能完美地应用所有的算法，所以我们关注的通常是如何合理运用已学知识，并在所掌握算法间构建一种平衡，在限定的时间内尽可能多地解决问题。本文尝试讨论一类平衡思想应用于算法构造、算法实现的模式。
【关键字】
平衡思想、平衡点、时空效率、编程复杂度
【正文】
一、引言
平衡通常指物体或系统的一种状态。处于平衡状态的物体或系统，除非受到外界的影响，它本身不会有任何自发的变化。多种状态达到平衡通常是我们所追求的目标。
平衡思想是一种奇妙的思想，它的应用十分广泛。在算法设计，数据结构设计甚至程序设计中都能发现它的身影。计算机竞赛就是一场博弈，寻找这场博弈中的平衡点，合理应用平衡思想辅助算法设计与程序实现，往往能起到化腐朽为神奇的作用。
在信息学竞赛中，平衡思想通常有以下几个方面的运用：
1、博弈问题。有许多博弈类问题都可以转化成寻找平衡点的问题。
2、数据结构的构建。每种数据结构都能以优秀的性能支持某些操作，合理选择应用数据结构，往往能通过略微提高一些操作的复杂度，降低大多数操作的复杂度，在不同操作的效率之间构建一种平衡，以达到优化的目的。
3、时间效率 vs 空间效率。这类问题是我们经常遇到的问题。这类问题通常有这样的特性，我们能找到时间效率（或空间效率）十分优秀的算法，但代价是空间效率（或时间效率）极端低下。如何合理设计算法，组织数据，平衡二者的关系是解决这类问题的重点。
4、时空效率 vs 其他。如果面对难题难以设计出优美的算法，又或者设计
了优秀效率的算法，却无法实现或难以实现，就会出现非常尴尬的局面。合理应用平衡规划解决这类问题，往往能收到意想不到的效果。而这类问题也正是本文所要重点探讨的问题。
下文将试图论述运用平衡思想解决这类问题中的三种常见模式：经典算法的非典型实现，效果优秀的非完美算法，以及复杂问题的简单化构造。
二、应用平衡思想的几类问题
1、经典算法的非典型实现。
大多数经典算法通常是为很多人所熟知，并且能够熟悉运用。经典算法通常也有很多不同的实现方法。例如拓扑排序，如果数据范围比较大，通常使用算法复杂度为O(n)的程序，但是如果范围比较小，一个不超过10行的)
O的程序
(2n
可以使代码看起来更为简洁。而不同的实现方法中，哪怕只是细微的不同，实现后的性能与效率也可能有很大的差别。更进一步，有些算法虽然堪称经典，但是无论是思考复杂度还是实现复杂度都相对颇高，在考场上来说，使用一些相对简单实用的方法无疑是一种不错的选择。
例题一、警卫安排问题(ural 1099)
题目描述：
给定若干警卫间搭档关系，要求成对给警卫安排保卫工作，求能够安排警卫的最大值。（警卫人数不超过222）
初步分析：
题目描述很简单，稍加分析后我们很容易看出来，这题的本质其实是要求我们求出任意图的最大匹配。
任意图的最大匹配的经典算法是应用带花匈牙利树，时间复杂度为)
O，
(3n
对付这道题来说是绰绰有余的。但是带花树本身比较复杂，思维复杂度与编程复杂度较高，而且实现起来很容易退化，考场上有限的时间内难以完成。于是我们尝试考虑替代算法予以解决。
解法分析：
3 4 5
2 1 6 7 8 图一 解决二分图最大匹配的时候，主要过程是不断寻找交错增广树来调整。那么这么做对于任意图是否可行？答案是否定的。
考察右边这张图（图一）。图中粗线表示当前状态下已匹配边，虚线表示未匹配边。若我们当前找的增广树如图二所示，那么
我们就无法找到一条增广路。但实际上，存这样的
一条增广路：876321→→→→→。为了找到
增广路，我们可以采用搜索的方法，但这样寻找增
广路复杂度过高。
我们注意到，采用调整增广轨的方法，如果一个点之前已经被匹配到，则之后无论如何调整，这个点始终能被
匹配到。因此，对于一个待匹配点，是否能找到一条以它为起点
的增广路是优化解的关键。而是否能找到一棵增广树又很大程度
上依赖于之前找寻的情况，若要设计数据使得无法找到增广树通
常又依赖于特定的扩展顺序。这启发我们采用随机扩展顺序的方
法来尽量避免形成类似图一的特殊局面。
笔者的程序中生成了两个随机序列，一个作为点的初次访问
序，一个作为点的拓展顺序，然后直接使用一开始所说的寻找交
错树的方法来扩展。同时，采用多次随机运行的方法提高最优解
的出现概率。
但是作为随机贪心算法，除了拿到AC 之外，我们更应该关注这个程序通常的运行情况如何。上述算法中，在ural 点数限制仅仅为222以下的情况下，通常运行次数却要设定为20至50才能基本上保证AC 。相对于数据本身，这个运行次数还是比较大，说明算法本身具有比较大的不确定因素，以及出最优解概率并不是很高。所以我们需要进一步优化以提高一次运行的最优解出现概率。
进一步优化
上述解法中曾提到，采用调整增广轨的方法，如果一个点之前已经被匹配到，则之后无论如何调整，这个点始终能被匹配到。它带来的另一个信息是，若一个点之前未被匹配到，那么在本轮搜索中，这个点最终将很可能保持未匹配的状态。因此影响最终结果的，往往是某个本应该被匹配到的点因为之前增广树的查找失3 4 5 2 1 6 7 图二
败而被放弃匹配。初始算法解决这个问题的方法是全局重新搜索，所以常常出现为了一个点而全部重来的尴尬场面。其实这是舍近求远。我们完全可以换一个扩展顺序，对于当前未找到交错树从而无法匹配的点，直接重新搜索一棵交错树！当然大部分的图都无法实现完美匹配，所以类似运行次数的限制，我们需要设置一个失败次数上限。当为一个未匹配点寻找匹配点时，只有失败次数超过了这个上限才放弃。
那么失败上限次数应该设置为多少比较好？进一步的，这个方法实现起来究竟效果如何呢？为此笔者进行了一系列的实验，得到了如下的实验数据表：
运行次数-失败上限5-5 5-10 10-1 10-10 20-1 20-10 50-1 Accepted 90% 100% 0% 90% 60% 0% 100% Wrong answer 10% 0% 100% 10% 40% 0% 0% Time limit exceeded 0% 0% 0% 0% 0% 100% 0% 平均AC时间0.0761 0.1471 -- 0.2960 0.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的全部超时就可以说明这一点）。实际上，虽然理论上时间复杂度仅仅是多一个所设置的失败上限的常数，但由于将进一步优化中需要大量地使用了随机函数，而生成随机函数的常数比较大，造成了实际程序的常数较大，拖累了时间。
所以，两种算法都有其各自的优缺点，这就需要我们根据题目的给出的信息，根据实际算法的需求来进行选择。
进一步扩展：
随机搜索序和设置失败上限的作用并不局限于此。
对于随机搜索序，表面上看是根据克制数据或克制情况的顺序依赖性1，应用随机的顺序来进行回避。其实其本质是：通过设置一些随机权值，以改变一个当前状态的属性，从而回避特殊情况的生成（例如本题是回避克制数据的生成）。我们常用的Treap ，随机快排（随机选择比较变量），其本质也是如此。
设置失败上限则是随机搜索序关于准确率的一个优化。随机算法不可避免还是有可能无法得到我们理想的状态或结果（例如本题依然可能找不到存在的增广路，又例如Treap 并不完全平衡）。随机搜索序通常是全局重新运行来提高最优解的出现概率，而设置失败上限则是通过对于局部问题的精益求精来强化全局目标情况出现概率，常见的应用有大素数的测试等。
小结：
对于这道题，两种方法都可以比较轻松地通过。考虑到数据范围并不大，为了追求准确率可以增加参数上限，或者为了保证时间效率压缩参数上限，这需要我们根据实际情况合理平衡二者之间的关系。以准确率为代价我们得到了随机贪心算法，以时间复杂度为代价我们得到了准确率的进一步的优化，但不论是哪种方法，都能有效地降低了思维与编程复杂度，达到了二者之间的相对平衡。
例题二、Jackpot （PKU2103）
题目描述：
等概率选择任意整数，若其能被p1,p2,p3...pn 中至少一个数整除，那么称当前情况为胜利局面。给定p1,p2,p3...pn ，（n<=16）求得到胜利局面的概率（用最简分数表示）。
初步分析：
本题看起来十分复杂。题目作为参考，给了一个比较复杂的计算概率的式子。
??
? ??+=∞→12lim k S P k k 其中P 表示最后结果的概率，k S 是 - k 到 k 之间至少能被给定的p 1,p 2...p n 其中一个数整除的个数。
但如果直接用这个式子比较复杂。所以我们设计了下述算法代替。注意题目 1 即特殊情况依赖于一定的顺序，例如本题是克制数据的生成依赖于一定的搜索顺序。
中涉及高精度计算，但本题时限卡的比较紧，如果用普通的高精度容易超时，巨大的常数无法忍受。如何合理优化常数成为了解决问题的关键。
解法分析：
本题其实是数学题。题目等价于求取数区间为1~lcm(p1,p2,p3...)的时候的概率，但由于1 <= p i <= 109，使得最小公倍数可能很大，直接扫描显然不现实。注意到给定的数最多只有16个，所以我们可以应用容斥原理求出区间中可以得到胜利局面的数的个数。由于题目涉及了许多求gcd ，lcm 的高精度，一个小技巧是开一个素数列表，当前状态以纪录素数的次数的方式记录，最后再还原成原来的整数。主算法的设计与实现并不困难。所以在主算法相同的情况下，高精度算法的实现优劣就成了左右程序效率的关键。
本题涵盖了许多的高精度算法，而几乎每一次运算都要使用到高精度运算。其中使用最多的有高精度乘以单精度与高精度加减法。
高精度运算有一个通用的优化：压位。在longint 范围内通常是压4位（即万进制），在int64则可以压8位，而压位能有效地减少高精度数组的长度，从而提高效率。注意到程序实现时要大量使用div 与mod 运算，这两个运算的常数是比较大的。那么是否有办法绕开这两个运算呢？
答案是肯定的。
我们注意到，除法与取模的运算是为了进行压位处理的操作，（注意到若是高精度乘法，中间结果可能比较大，所以用while 递减实现取模的效果更差）。但无论压位与否，我们的所采用的万进制等进行压位实质上还是沿用着通常的十进制的思维模式。但计算机处理二进制运算（位操作）显然要比十进制常数小。所以我们可以跳出思维惯性，采用二进制压位，这样，一些取模或者除法运算就能用位操作很好地实现。
下面是两个程序主要部分的伪代码的对比。（高精度与单精度乘法） 采用n 10进制压位的乘法
采用n 2进制压位的乘法 for i ← 1 to a[0] + 1 do
begin
p ← a[i] * b + p div n 10;
a[i] ← p mod n 10; for i ← 1 to a[0] + 1 do begin p ← a[i] * b + p shr n; a[i] ← p and (n 2-1);
end;
end;
可以发现，两者的程序几乎相同。但采用n2进制压位的乘法利用位运算代替了运算常数很高的div与mod，而同等情况下压位后数组长度与通常的压位差别不大（甚至稍优），所以实际应用时可以取得很好的效果。在本题中，笔者的程序应用了这个方法，在1秒内就通过了所有的数据。
当然有得必有失。这种优化因为采用n2进制进行压位，但通常答案都是要求输出10进制的结果，所以无法类似n
10那样直接输出。在输出时需要对其进行高精度计算对10取模。这里就不再赘述了。
小结：
例题在实现中跳出了典型实现的思维框架，创新地使用了二进制压位思想。虽然修改后在最后输出时的取模操作提高了输出的时间复杂度，但毕竟输出的次数通常不多，而程序中调用高精度运算的次数却可能很大（例如本题）。这里以提高输出的复杂度为代价，降低了运算的常数复杂度，实质上是构建了二者的算法复杂度之间的平衡，所以最后能取得相当不错的效果。
经典算法还有很多，也有一大部分无论设计与实现都存在一定的困难，很多细节的操作往往也能左右算法的效率。在这样一类问题中，本来是简化问题的经典算法却成为了程序实现的障碍。根据实际需求，合理改造算法，细心设计算法细节的实现，有效地平衡算法中不同部分的复杂度关系，建立各部分之间的平衡，往往是解决这类问题的利器。
2、效果优秀的非完美算法
在信息学竞赛的赛场上，遇到不会做的题目对大多数人来说是很平常的事情。但是如果就此放弃也未免太可惜了。毕竟一道题一百分往往能直接左右竞赛的结果。如果题目有部分分，又或者题目是要求我们求最优解或者构造最优方案时，采用些非完美算法或者近似算法往往能收到不错的效果（虽然不一定能满分）。如果类似下文能使用DP、贪心算法构造出“几乎是对”的算法的话，则能为我们节省下大量的思考时间，达到了得到的分数与所消耗时间的平衡，性价比
可谓是非常高。
例题三、追捕盗贼（NOI2007 Day2 catch)
题目描述：
Magic Land 由N 个城市，N-1 条公路彼此连接起来，任意两个城市间都可以通过若干条公路互达。大盗Frank 能够在公路上以任意速度移动。你的任务就是抓住大盗Frank 。但是你完全不知道Frank 躲在哪个城市，或者正在哪条公路上移动，所以需要制定一个周密的抓捕计划。每个单位时间你可以完成以下几个操作：1、在某个城市空降一位警探。2、把留在某个城市里的一位警探直接召回指挥部。3、让待在某个城市的一位警探沿着公路移动到另一个城市。若警探和大盗在同一城市或者同一条公路上移动则可以抓获大盗。请你制定一个使用人数最少的捕获计划，并且操作次数不能超过20000。
初步分析：
本题初看上去并不复杂，但却是这次比赛最难的一道题。事实上，这是一道论文题级别的题目1，涉及许多定理与推论，思维复杂度编程复杂度同时达到一定的高度。事实证明，考场上也没有人想出来标准做法。但这一百分也不能扔掉。考虑到这题的评分标准存在部分分，而且只要有一个可行解就有分，即使是简单的构造也能拿到一定的分数。所以各种骗分的算法蜂拥而至，也取得了一定的效果。但是这题的数据还是比较强大，寻常的骗分效果并不理想。于是经过一定的思考，我们可以发现一种比较不错的替代算法。
解法分析：
我们首先考察简单的样例数据。
城市与城市之间的连接关系如右图所示。一种可
行解是：始终在城市2驻扎一个警探，然后在城市1降
落1个警探并往城市2移动，到达城市2后收回，并对城
市3、4进行类似的操作。
样例虽然简单，但给我们提供了一种非常有用的构造思想。我们知道，树上 1 本题实质上是图论中的“Search Number ”问题，对于一般图，Search Number 问题是NPC 的。对于树上的特殊问题，可以在O(N)时间内求出Search Number ，在O(NlogN)时间内求出相应方案。有兴趣的同学可以查找相应的资料。 1 2 3 4
的任意一个点可以将树拆分成若干个无关的部分。对应于这道题目来说，在一个点上常驻一个警探可以使大盗无法从被这个点分隔开的一个部分进入另一个部分。显然，为了使我们之前的搜索过程没有浪费，进行分叉的搜索时，在分割点上驻一个警探可以保住之前的搜索成果。
这样，我们就可以每次选择一个点将图拆分成若干个不同的部分。每个部分就是一个缩小规模版本的题目。这不是神似我们常用的动态规划的解题构造法么？根据这个思路，我们能得到一个大概的转移方程式：
1))(max()(+=i V F V F
其中，)(V F 表示树的点集为V 时候的较优（最优）警探放置数量，)(i V F 表示第i 棵子树（点集为i V ）的情况。
但是子状态的情况并不好构造，如果构造不当，这样的结果并不一定很优。 最简单的方法，我们可以搜索每次拆分的点。但是这么做时间复杂度十分高，而且输出方案、程序实现也相对麻烦。同时我们考虑这样的情况，例如一个点将这棵树分成了若干个部分，如果我们搜索行动进行到了最后一部分时，原本驻扎的警探就可以沿路径前进，这样可以节省一个驻扎在分割点的警探，结果通常会更优。
而且，一棵子树的最优解情况并不容易转移到原树上。对于这种方法，子树的若干最优解如何选择，如何与整棵树的解进行衔接从而构造最终解，如何保证正确性最优性的兼并？这些都是我们需要考虑但又十分困难的问题。
但我们怎能就此放弃这道题？花时间考虑过于复杂的标准方法显然不现实。考虑到有部分分，我们完全可以修改上述方法使之能取得一个较优解。
上述方法有一个重点是考虑将树分解成了若干个小规模的问题，但同时产生一个问题，如何衔接子问题与总问题的构造？我们不妨将初始的分割点作为树的根，构建整棵树，子问题的分割点直接设置为子树的根。每次选取一个需求最多的子树作为最后扩展部分。采用这样的思路，一个新的近似构造方法产生了。 首先枚举初始分割点，将初始分割点作为树根建树。对这棵树进行类似树状动态规划的贪心构造。我们有如下状态转移方程。
()(){}(){}???? ?
?≠∈+∈=y z x son z z D x son y y D x D ],[1)(max ][)(max max 其中D(x)表示以x 为根节点的树的较优（最优）警探放置数量。son[x]表示
节点x 的儿子节点的集合。 构造具体解的时候，我们也完全可以按照转移来进行构造。整个过程是递归实现的。将两个警探驻扎在分割点上，派出一个警探移动向分割点的子节点，然后重复上述过程，探索完毕（即警探走到了叶子节点）就立刻将警探回收。对每一个分割点，最后探索需求警探数最大的子树，此时不用额外派遣警探，直接将分割点上警探移动到子节点，并重复上述过程直到整棵树探索完毕。
从实现方面来说，算法的主体部分无论计算还是构造，实现起来都相对比较轻松。但这个算法的最后效果如何呢？
上述算法主要弱点在于，我们除了初始的分割点是枚举的外，其余子树初始分割点直接定为子树的根。这样做虽然使得构造解
变得轻松，但有可能使得子树得到的解无法保证最
优，从而影响整体解的质量。例如下图的情况1，如
果按照上述的贪心算法，我们会得到最后的答案是
4，但是实际上最优解只需要3个警探就可以了。构
造方案如下，root 节点始终驻扎警探，分别派遣警
探a ，警探b 到节点5，6，并同时往节点2移动，回
收警探b ，让警探a 往节点1移动。派遣警探b 到root
节点并顺次移动到节点1，4，9。回收警探b ，派遣
a 往节点3移动并派遣警探
b 到节点3，之后警探a ，b 分别往节点7，8移动并回收。对于root 的其他子树采取类似的操作。
我们的贪心算法因为对于子树默认以根节点作为分割点，所以无法得到上述的构造方案。那么这个算法是否还有意义呢？
我们注意到影响到当前点解的质量只有2个因素，即子节点中需求警探数最大与次大的点。因此，其他子节点的解即使稍劣也不会影响最终结果。也就是说，实际的解给部分的解提供了一个弹性空间。同时，即使部分数据可以克制这个算 1 虚线与省略号部分表示节点root 还有不少于2个和“节点1所在的子树”相同的子树。实际上，若root 节点只有2个“节点1所在的子树”，那么这个贪心依然能得到3这个最优解。 1 5 6 8 9 …… 3 7 2 4 root
法，但由于小部分克制数据比较难以构造（上述反例也至少需要大约30个节点来“配合”），随着数据量加大，通常随机的数据即使生成了克制数据也几乎无法影响最后的解。而且，即使是给定顺序的分割点，得到的解通常也是较优解甚至最优解。而枚举第一个分割点虽然把时间复杂度提高到了O(N2)，但时间方面依然很宽裕，解的质量却有效地提高了。
笔者使用这个方法测试了1000组随机数据，结果表明，有百分之八十五左右的计算结果只需要5个警探，其余都是6个警探（极偶然出现过只需4个警探的情况）。对照得分规则，可以发现这样至少能获得60%的分数。（2个以下警探肯定能正确出解）。实践证明，这种方法对于考场的数据可以拿到96分的好成绩，只有一个数据点结果会比标准答案大1。
小结：
虽然没有AC掉这道题，但对于实质上属于论文难度级别的这道题，考场上能够做到96分已经足够了。考虑到这种构造法思维复杂度较低，实现起来十分轻松，时间复杂度中规中矩，时限范围内足够出解，而且解的质量相对较高。考场上，这样的程序能为我们省下大量的时间去解决其它问题。
在这道题目中，我们用解的质量为代价，极大地降低了程序思维复杂度与实现方面的难度，同时在基础的方案上，我们合理优化构造的方法，使得解的质量通常可以达到最优。
在这一类问题中，原本复杂的问题我们无法解决，一味追求AC往往得不偿失，而选择一些效果不错的近似算法就有着较高的性价比。这样实质上是通过些另类的途径，有效地建立了所得分数与所耗时间的平衡，以少量的代价取得了优秀的效果，也不失为一种优秀的解题策略。
3、复杂问题的简单化构造
当然，并不是每一道题都能够找到第二类问题那样的效果优秀的近似算法。而且如果是形如ACM之类的比赛，或者题目要求维护一系列操作时，近似算法的作用往往会被限制。此时，我们即使无法找到时空效率十分优美的算法，也需要沉着下来，仔细分析题目特征。一类常常使用的方法就是，在可行的时空限制下，
以时空效率为代价，降低思维复杂度，建立时空复杂度与思考实现复杂度的平衡，这就是复杂问题的简单化构造。
这类问题通常有一个特征。如果题目所给的条件再强大一些，把可能涉及的情况限制成某些特例时，我们能找到优秀的算法，但扩展之后却不能通用。如何有效应用特例提供的信息来简化模型，进一步地建立特例与一般的平衡，往往是解决问题的关键。
例题四、数列维护
题目描述：
给一个长度为n(n<=100000)的整数数列，要求维护以下几个操作。
1、数列第i项到第j项同时加上一个整数。
2、询问第i项到第j项中比整数c小的数有多少个。
最大操作数不超过10000。
初步分析：
本题要求我们应用数据结构维护关于序列区间的一些操作。由于同时涉及区间的比大小，询问，增减操作，我们的第一反应通常是用树套树的数据结构来解决这样的问题。但注意到题目中有变换区间序列的操作，简单地套用模型会使得区间合并的时候时间复杂度并不理想。再者，树套树有着复杂的代码量，调试起来也并不容易，如果不小心就可能造成巨大的损失。注意到题目中最大操作数仅10000，时限方面也并不紧张（5s），我们可以放弃树套树的思想，考虑采用实现简单、代码量低、调试方便的算法来代替。
解法分析：
对于区间操作，还有一种数据结构也常常为我们所用，那就是块状链表。不过，直接写普通的块状链表复杂度是)
O，但代码量依然巨大。但块状
m
log
(n
n
链表的思想可以为我们所用。我们注意到，题目中的区间操作仅局限于区间增减或者询问，并不会打乱数列的顺序，所以，我们不妨稍微改造下块状链表——块状数组。
块状数组是这样的一个数组，它直接对原数组进行划分，分为n个部分，
每个部分长度为n，每个部分开相应的域以记录类似增减的操作信息（当然也可以是一些统计的信息，但这不在本题考虑范围之内）。这样的结构实现起来十分简单（使用原数组即可），适合的操作包括一些区间大小询问，区间增减操作，但不支持区间插入删除操作，原因是块状数组适合这样的序列操作，序列项与项之间隐含着严格不变的次序关系。但本题所要求的操作正好能满足这个条件。
在这道题目中，我们需要维护的操作有两个：区间增减操作，区间询问操作。注意到增减操作时，如果完全覆盖了一个划分区间，那么这个操作就不会影响这个划分区间中数的大小关系。也就是说，对于一个区间增减操作，我们至多只需要更新“操作区间”的头尾所在的划分区间的序列关系。而值得注意的是，如果我们能保证时时维护划分区间使之有序，那么区间询问操作就可以应用二分法轻松完成。基于上述思想，我们可以设计出如下在线算法。
设数组A为原数组，令数组A
B=。预处理为：将数组B划分为n块，每块长度为n（块状数组）。对于数组B的每个部分，应用快速排序将其按从小到大排序，并开额外的域来记录区间增减情况。初始时所有额外域的数值为0。
对于操作1（数列第i项到第j项同时加上一个整数），用常数时间求出操作区间的连续部分。对于完全被操作区间覆盖的部分，只需修改相应的标记域值即可。对于未被完全覆盖的部分（只可能是头尾，最多两个部分），直接对该部分内相应数值进行修改。最多修改n个区间，头尾区间最多修改n个数值，修改后重排序代价为)
n
n
n=
=，所以该操作最坏情况下复杂
O
n
log
n
(
log
log n
5.0
度为)
n
O。
log
(n
对于操作2（询问第i项到第j项中比整数c小的数有多少个），方法是类似的。首先用常数时间求出操作区间的连续部分，对于完全被操作区间覆盖的部分。因为其中是有序的，可以使用二分法求出比c小的数的个数。对于头尾所在的两个区间，只需直接扫描一遍并统计即可。这样最多访问n个区间，每个区间询问复杂度为)
n
n
n
n=
=，头尾区间最多扫描n个数值，
O
log
n
log
(
log n
5.0
所以总的时间复杂度最坏为)
O。
n
log
(n
综上所述，总共m 个操作，时间复杂度最坏为)log (n n m O ，最坏情况复杂度在千万级别，足够通过所有数据。
小结：
实际上，本题虽然有采用树套树，时间复杂度为)log log (n n m O 的算法，但其思维复杂度比较高，实现也并不容易。考虑到题目的特殊性，我们可以发现序列中隐含的不变的次序关系，并根据数据范围和时限选择合适的算法。本题中，我们并没有硬性追求时间复杂度十分优美的算法。由于题设对操作的限制，使得我们能通过改造经典数据结构的实现方法，有效地降低了思维与编程复杂度，还在一定程度上优化了常数。这实质上正是在时间复杂度与思维复杂度之间找到了一个平衡点，并借此有效地解决了问题。
例题五、树的维护(PKU 3237)
题目描述：
给定一棵有N 个节点的树，点编号为1～N ，边按给定顺序编号为1～N-1，每一条边有一个边权。需要对这棵树维护三个操作：
1、将某一条边的权值修改为V 。
2、将点A 到B 的路径上的边权值取负号。
3、询问点A 到B 的路径上的权值最大值。
数据组数不超过20，点的个数不超过10000。
初步分析：
本题主要是对树上的路径进行操作，这类问题我们往往可以采用动态树来解决。并且对于这道题，动态树有“看着十分舒服”的对数级别复杂度。但问题并没有解决。首先，对这题使用动态树有种“大材小用”的感觉，因为动态树功能最强大的地方在于它能维护一棵不断改变形状的树，但本题中树的形状是固定的。其次，动态树实现起来比较复杂，巨大的常系数也不得不为我们所考虑。所以，我们尝试考虑一些其他算法来代替动态树，以便更有效地解决这个问题。 解法分析：
我们不妨先考虑题目的一种特例情况，即树退化成了一条链的情况。这个问
题便是我们常常见到一类应用线段树解决的问题。那么是否能将一条链推广成树的情况呢？
笔者首先考虑的情况，是将树按照某种规则（例如深搜序）进行遍历，将遍历时产生的访问序列当成一条链的情况来处理。遗憾的是，经过若干次尝试后，发现情况并没有想象中那么简单，故放弃了这种想法。
但上述想法也并非一无是处。其实上述想法的主要目的是将树的情况转化成链的情况。既然转化不成功，不如直接把树拆成一条一条的链来做。于是，下述算法产生了。
首先我们任选一点为根构建整棵树，并将每条边的权值下放到边连接的两点中的儿子节点上。（整棵树的根取值可以定为任意值，因为并不影响任何操作）对于任意一个节点x ，假设它的儿子们都属于一条自底向上，并且以自己为结尾的链上，那么我们选择其中最长的一条链连到x 上。这样树上的所有点都属于不同的链上（有些链只有一个节点），我们称这些链为拆分链。注意之前对边下放权值的好处这里就体现出来了——链与链之间断开的边不用作为单独的边而特殊考虑了。
例如右图的情况，我们就将这棵树拆成了如下
5条拆分链（图中用粗线表示拆分链的边）：
7631→→→，92→，4，5，8。 对于每条链，建立一棵线段树，由于取负操作
的存在，需要同时维护这条链中的最大边与最小
边。链与链的拆分关系可以用并查集存储。
对于操作1，直接修改存储该边权值的点的权
值，并维护该点所在线段树中的最大值与最小值。
复杂度为)(log m O 。显然m 的最大值为n 。
对于操作2，我们先求出点A 与B 的最近公共祖先root ，然后分别对A 到root ，B 到root 的两条链进行操作。每次操作就是依次访问他们之间的拆分链，在相应的线段树上进行取负操作。
对于操作3，类似操作2，求出A 与B 的最近公共祖先root ，分别求出A 到root ，B 到root 的两条路径的结果，取较大的输出。每次操作依然是依次查找当前路径8
2 7 1
3 6 9
4 5
所在的拆分链，然后对这一段在这条链的线段树上进行询问操作。
以上所有关于最近公共祖先，路径与拆分链的查找，都可以在常数时间内完成。所以这个算法复杂度的瓶颈就在于，操作2与操作3中最多可能访问的树的拆分链的个数。
从直观感觉上来说，我们的拆链方法对于普通的数据，都能使得很多的路径基本落在拆分链上，所以这个数通常并不会很大。
但这样总是不够保险。实际上，我们也可以估算出，操作2与操作3的复杂度最多不超过()n n O log 。
[引理]按照以上贪心思想对任意一棵n 个节点的树进行拆链，任意点x 到其任意祖先root 之间的拆分链数目不超过)(n O 条。
[证明]定义一个集合S ，它的元素是x 到root 之间所有的边。设S 中的边属于k 条拆分链，这些拆分链与路径公共部分的最上层节点为k P P P ?21,，其中root P k =。那么2P 必然连接着另外一条向下走的拆分链，这条拆分链除去属于S 的部分至少还有1个点；同时3P 也必然连接着另外一条向下走的拆分链，这条拆分链除去属于S 的部分至少还有2个点；……；同理k P 连接的向下走的拆分链除去属于S 的部分至少还有k-1个点。这样以root 为根的子树至少要有
(1)123...12k k k k +++++-+=个点。显然(1)2
k k +最大为n ，这时()
n O n k =-+=2118。引理得证。 [定理]理论上操作2与操作3的时间复杂度最坏为()n n O log 。
[证明]根据[引理]，我们知道每次操作2与操作3最多访问)(n O 条拆分链，而每次访问拆分链需要维护拆分链对应的线段树，维护的复杂度为()m O log ，其中m 最多不超过n 。所以操作2与操作3的时间复杂度最坏为()n n O log 。
以上我们证明了操作2与操作3的复杂度最多不超过()
n n O log 。从而对于一
组数据，整个算法的时间复杂度为()n
O log
log+，看起来时限有些吃紧。
n
n
n
q
但实际上这个上限是一个十分宽松的上限，而且程序实现的常数比较低，所以运行起来效果相当不错。PKU上，笔者的程序用了951MS就通过了所有的数据。
小结：
本题中，我们放弃了看上去十分优美的对数复杂度的动态树(复杂度为q
n
n
n
O+)，转而通过对树的拆链操作来完成题目要求的操作。我
)
log
log
log
(n
们通过对特例情况的考虑，寻找到了最后的解法，这实际上是建立了特例与推广的平衡，从而有效地解决了这个问题。虽然我们估计的最坏复杂度比较庞大，但是实际运行效果相当优秀，而且程序实现方面也相对简单。虽然没有精细地计算出时间复杂度的上限，但这并不妨碍这个算法的实用价值。
实际上，ural某次比赛中也曾出现过这题（ural1553)，在比赛中，笔者也正是用这种方法第一个AC此题，也正说明这种方法是行之有效的。
三、总结
我们知道有一个经典的木桶：一个木桶由许多块木板组成，如果组成木桶的这些木板长短不一，那么这个木桶的最大容量不取决于长的木板，而取决于最短的那块木板。如果把时间复杂度，空间复杂度等都看作是解决问题这个木桶的一个木板，那么我们常常忽略的便是思维与实现复杂度这块木板。为了增加容量，不妨截取较长的木板来拼接到短的木板上，所有木板长度相同时容量也达到了最大。平衡思想正是这样一种取长补短的思想。
应用平衡思想解决的问题有一个特征：存在瓶颈。这瓶颈通常是阻碍我们解决问题的主要障碍。本文就对可应用于这类的平衡思想作了一定的介绍，同时较深入地讨论了一类以其他方面为代价，降低问题的思维复杂度与程序的实现复杂度的模型。通过构建各方面复杂度的平衡，我们能有效地在有限的时间里尽可能多地解决问题。赛场上，我们不必追求最完美的时空复杂度，因为高分才是硬道理，AC才是硬道理！
外在看来，平衡规划更像是一种“骗分”思想。但笔者认为，解决信息学问题并不能只是单纯追求时间复杂度的完美，在有限的时间内要综合考虑各方面因
素所带来的问题，这也正是信息学竞赛的魅力所在。合理应用我们所学的知识并将他们有效结合，合理决策对问题的数学模型，算法各方面（包括设计，实现）的精力分配，才能有效地解决问题。当然，即使如此，也需要我们有扎实的基本功，才能在赛场上能有更多的选择。而且这类思想需要我们不断地练习才能较好地掌握，实践才是感悟这一类问题最有效的途径。毕竟，纸上得来终觉浅, 绝知此事要躬行。
四、感谢
感谢陈丹琦同学提供部分资料并对本文的实现与修改提出建议；
感谢董华星同学为本文的修改提出建议；
感谢刘弈同学为本文的修改提出建议；
感谢刘汝佳教练对本文的实现与修改提出建议；
感谢陈光老师为本文的修改提出建议；
感谢胡山立老师为本文的修改提出建议。
五、参考文献
[1]《算法艺术与信息学竞赛》刘汝佳黄亮著
[2]《
[3]《Catch题目分析》许智磊
六、附录
例一的原题：ural1099. Work scheduling
There is certain amount of night guards that are available to protect the local junkyard from possible junk robberies. These guards need to scheduled in pairs, so that each pair guards at different night. The junkyard CEO ordered you to write a program which given the guards characteristics determines the maximum amount of scheduled guards (the rest will be fired). Please note that each guard can be scheduled with only one of his colleagues and no guard can work alone.
Input
The first line of input contains one number N≤ 222 — this is the amount of night
guards. Unlimited number of lines consisting of unordered pairs (i, j) follow, each such pair means that guard #i and guard #j can work together, because it is possible to find uniforms that suit both of them (The junkyard uses different parts of uniforms for different guards i.e. helmets, pants, jackets. It is impossible to put small helmet on a guard with a big head or big shoes on guard with small feet). The input ends with Eof.
Output
You should output one possible optimal assignment. On the first line of the output write the even number C— the amount of scheduled guards. Then output C/2 lines, each containing 2 integers (i, j) that denote that i and j will work together. Sample
Input Output
3
1 2
2 3 1 32 1 2
Problem Author: Jivko Ganev
例二的原题：PKU2103 Jackpot
Description
The Great Dodgers company has recently developed a brand-new playing machine. You put a coin into the machine and pull the handle. After that it chooses some integer number. If the chosen number is zero you win a jackpot. In the other case the machine tries to divide the chosen number by the lucky numbers p1 , p2 , . . . , pn . If at least one of the remainders is zero --- you win.
Great Dodgers want to calculate the probability of winning on their machine. They
“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。
摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Pólya原理及其应用》 2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 - 周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Pólya计数法的应用》 数位问题 2009 - 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004 - 薛矛：《解决动态统计问题的两把利刃》 2007 - 余江伟：《如何解决动态统计问题》 博弈 2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》2007 - 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》 母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007 - 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005 - 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003 - 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题 2003 - 张宁：《猜数问题的研究:<聪明的学生>一题的推广》
2006 - 龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 - 何林：《数据关系的简化》 2006 - 朱晨光：《基本数据结构在信息学竞赛中的应用》 2007 - 何森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001 - 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 - 黄刚：《数据结构的联合》 块状链表 2005 - 蒋炎岩：《数据结构的联合——块状链表》 2008 - 苏煜《对块状链表的一点研究》 动态树 2006 - 陈首元：《维护森林连通性——动态树》 2007 - 袁昕颢：《动态树及其应用》 左偏树 2005 - 黄源河：《左偏树的特点及其应用》 跳表 2005 - 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009 - 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree》 线段树 2004 - 林涛：《线段树的应用》 单调队列 2006 - 汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 - 杨思雨：《伸展树的基本操作与应用》
动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。
左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (5) 3.1 左偏树的合并 (5) 3.2 插入新节点 (7) 3.3 删除最小节点 (8) 3.4 左偏树的构建 (8) 3.5 删除任意已知节点 (9) 3.6 小结 (12) 四、左偏树的应用 (13) 4.1 例——数字序列（Baltic 2004） (13) 五、左偏树与各种可并堆的比较 (15) 5.1 左偏树的变种——斜堆 (15) 5.2 左偏树与二叉堆的比较 (16) 5.3 左偏树与其他可并堆的比较 (16) 六、总结 (18)
【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。
1999年 陈宏- 数据结构的选择与算法效率——从IOI98试题PICTURE谈起 来煜坤- 把握本质，灵活运用——动态规划的深入探讨 齐鑫- 搜索方法中的剪枝优化 邵铮- 数学模型的建立、比较和应用 石润婷- 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性睢》?- 准确性、全面性、美观性——测试数据设计中的三要素 周咏基- 论随机化算法的原理与设计 2000年 陈彧- 信息学竞赛中的思维方法 方奇- 动态规划 高寒蕊- 递推关系的建立及在信息学竞赛中的应用 郭一- 数学模型及其在信息学竞赛中的应用 江鹏- 探索构造法解题模式 李刚- 动态规划的深入讨论 龙翀- 解决空间规模问题的几种常用的存储结构 骆骥- 数学模型的建立和选择 施遥- 人工智能在围棋程序中的应用 肖洲- 数据结构的在程序设计中的应用 谢婧- 规模化问题的解题策略 徐串- 论程序的调试技巧 徐静- 图论模型的建立与转化 杨江明- 论数学策略在信息学问题中的应用 杨培- 非最优化算法初探 张辰- 动态规划的特点及其应用 张力- 类比思想在解题中的应用 张一飞- 冗繁削尽留清瘦——浅谈信息的充分利用 2001年 高寒蕊- 从圆桌问题谈数据结构的综合运用 符文杰- Pólya原理及其应用 高岳- 中等硬度解题报告 江鹏- 从一道题目的解法试谈网络流的构造与算法 刘汝佳- 搬运工问题的启示 李益明- 计算几何的相关问题 李源- 树的枚举 骆骥- 由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性毛子青- 动态规划算法的优化技巧 俞玮- 基本动态规划问题的扩展 张一飞- 求N!的高精度算法 2002年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用
NOI国家集训队论文分类（至2008） 摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Polya原理及其应用》 2003 -许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 -周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Polya计数法的应用》 数位问题 2009 -高逸涵《数位计数问题解法研究》 2009 -刘聪《浅谈数位类统计问题》 动态统计 2004 -薛矛：《解决动态统计问题的两把利刃》 2007 -余江伟：《如何解决动态统计问题》 博弈 2002 -张一飞：《由感性认识到理性认识一一透析一类搏弈游戏的解答过程》2007 -王晓珂：《解析一类组合游戏》 2009 -曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 -方展鹏《浅谈如何解决不平等博弈问题》 2009 -贾志豪《组合游戏略述一一浅谈SG游戏的若干拓展及变形》母函数 2009 -毛杰明《母函数的性质及应用》 拟阵 2007 -刘雨辰：《对拟阵的初步研究》 线性规划 2007 -李宇骞：《浅谈信息学竞赛中的线性规划一一简洁高效的单纯形法实现与应用》 置换群 2005 -潘震皓：《置换群快速幕运算研究与探讨》 问答交互 2003 -高正宇：《答案只有一个一一浅谈问答式交互问题》 猜数问题 2003 -张宁：《猜数问题的研究：< 聪明的学生> 一题的推广》
2006 -龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 -何林：《数据关系的简化》 2006 -朱辰光:《基本数据结构在信息学竞赛中的应 用》 2007 -何森：《浅谈数据的合理组织》 2008 -曹钦翔《数据结构的提炼与压缩》 结构联合 2001 -高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 -黄刚：《数据结构的联合》 块状链表 2005 -蒋炎岩：《数据结构的联合——块状链表》 2008 -苏煜《对块状链表的一点研究》 动态树 2006 -陈首元：《维护森林连通性——动态树》 2007 -袁昕颢：《动态树及其应用》 左偏树 2005 -黄源河：《左偏树的特点及其应用》 跳表 2005 -魏冉：《让算法的效率跳起来”——浅谈跳跃表”的相关操作及其应用》2009 -李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Bala nee Tree 》 线段树 2004 -林涛：《线段树的应用》 单调队列 2006 -汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 -杨思雨：《伸展树的基本操作与应用》
置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得O(k*乘法)或是O(logk*乘法)的算法；而对于分数幂运算，则找不到较好的方法实现。 二、置换群的整幂运算 2.1 整幂运算的一个转化 在置换群中有一个定理：设e T k =， （T 为一置换，e 为单位置换（映射函数为x x f =)(的置换）），那么k 的最小正整数解是T 的拆分的所有循环长度的最小公倍数。 或者有个更一般的结论：设e T k =， （T 为一循环，e 为单位置换），那么k 的最小正整数解为T 的长度。 我们知道，单位置换就是若干个只含单个元素的循环．．．．．．．．．的并。也就是说，长度为l 的循环，l 次的幂，把所有元素都完全分裂了。这是为什么呢？ 我们来做一个试验：(下面的置换均以循环的连接表示) 设n=6，那么3 26 )(T T =。任取一T=(1 3 5 2 4 6)，来做一遍乘法： ()() 36 2 45 1 34 126565432134 1 2 6 51265431265436543211265436543211265436543212 =???? ??=???? ?????? ??=???? ?????? ??=T 分裂成了2份！而且这2份恰好是T 的奇数项和偶数项！（注意可以写成(1 5 4)(3 2 6)）
浅谈数位类统计问题 山东省青岛第二中学刘聪 【摘要】 在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。 【关键字】 数位区间统计递推树二进制 【正文】 在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。 【例题1】Amount of degrees (ural 1057) 题目大意： 求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意： 17 = 24+20， 18 = 24+21， 20 = 24+22。 输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。 输出：只包含一个整数，表示满足条件的数的个数。 数据规模：1 ≤ X ≤ Y ≤ 231?1，1 ≤ K ≤ 20，2 ≤ B ≤ 10。 分析： 所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。 很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。
线段树的应用 广西柳铁一中林涛 【摘要】 在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。 线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。 本文通过3个例子：《蛇》、《空心长方体》、《战场统计系统》，讲述线段树中基本的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维的推广。 关键字：线段树二分子树收缩叶子释放面积树 【正文】 1. 线段树的定义及特征 定义1：线段树 一棵二叉树，记为T (a,b)，参数a,b表示该节点表示区间[a,b]。区间的长度b-a记为L。递归定义T[a,b]： 若L>1 ：[a, (a+b) div 2]为T的左儿子 [(a+b) div 2,b]为T的右儿子。 若L=1 ：T为一个叶子节点。 表示区间[1, 10]的线段树表示如下： (以下取对数后均向上取整) 定理1：线段树把区间上的任意一条线段都分成不超过2log L条线段 证明：(1)在区间(a，b)中，对于线段(c，d)，如果(c<=a) 或(d>=b)，那么线段在(a，b)中被分为不超过log(b-a)。 用归纳法证明，如果是单位区间，最多被分为一段，成立。 如果区间(a，b)的左儿子与右儿子成立，那么如果当c<=a时， 1．若d<=(a+b)div2那么相当与其左儿子分该线段，所分该线段数树不超过log((a+b)div 2-a)，即不超过log(b-a),成立。
2．若d>(a+b) div 2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过1+log(b-(a+b) div 2),也不超过 log(b-a)，成立。 对于d>=b的情况证明类似，不再赘述。 (2)在区间(a,b)中，对于任意线段也用归纳法证明。 对于单位区间，最多分为一段，成立。 若(a，b)的左儿子与右儿子均成立，则对于线段(c，d) 1．若d<=(a+b)div 2 则该区间所分该线段等于其左儿子区间所分该线段，线段数小于log((a+b) div 2-a)<2log(b-a)，成立。 2．若c>(a+b) div 2 则该区间所分该线段等于其右儿子区间所分该线段，线段数小于log(b-(a+b) div 2)<2log(b-a)，成立。 3．若1、2均不成立，则此线段在左儿子区间分该线段满足d>V.Lson.b,分该线段数不超过log(b-(a+b) div 2)，而在右儿子区间分该线段满 足c<=V.Rson.a,分该线段不超过log((a+b) div 2-1)，所以在该区间 分该线段不超过2log(b-a)，成立。 这个结论为线段树能在O(log L)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据。 【例题一】蛇1 在平面上有N个点，现在要求一些线段，使其满足以下要求： a．这些线段必须闭合 b．线段的端点只能是这N个点 c．交于一点的两条线段成90度角 d．线段都必须平行于坐标轴 e．所有线段除在这N个点外不自交 f．所有线段的长度之和必须最短 如果存在这样的线段，则输出最小长度，否则输出0。 【问题分析】 从该题的要求入手，先构出符合要求的图，再解决线段长度之和最小的问题。1．题目显然要求一个以给定的N个点为顶点的N多边形。所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。 2．将所有点排序后发现，在同一水平线上的点中，设这些点为P1，P2，P3，P4……Pn，P1要有一条平行于X轴的线段与其相连，就必须连它右边的点——P2，而P3如果再连P2，P2就有两条平行于X轴的线段和它相连，所以P3只能连P4，P5只能连P6……，同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。 3．由于解是唯一的，而是否相连只要广度扩展就可以判断了，所以关键在于判断由上述方法所构出线段是否合法——满足线段不在N个点之外自交： 1Saratov State University Problem Archive, 1028, Snake. 本题考查了基本的插入、删除和查找
NOI 国家集训队论文分类（至2008） 摘抄自 C 博客 组合数学 计数与统计 2001- 符文杰：《Pólya 原理及其应用》 2003- 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007- 周冬：《生成树的计数及其应用》 2008- 陈瑜希《Pólya 计数法的应用》 数位问题 2009- 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004- 薛矛：《解决动态统计问题的两把利刃》 2007- 余江伟：《如何解决动态统计问题》博弈 2002- 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》 2007- 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG 游戏的若干拓展及变形》母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007- 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005- 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003- 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题
2003- 张宁：《猜数问题的研究:< 聪明的学生> 一题的推广》2006 - 龙《一类猜数问题的研究》 数据结 构 数据结 构 2005 - 何 林：《数据关系的简化》 2006 - 朱晨 光：《基本数据结构在信息学竞赛中的应用》 2007 - 何 森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001- 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005- 黄刚：《数据结构的联合》 块状链表 2005- 蒋炎岩：《数据结构的联合——块状链表》 2008- 苏煜《对块状链表的一点研究》动态树 2006- 陈首元：《维护森林连通性——动态树》 2007- 袁昕颢：《动态树及其应用》左偏树 2005- 黄源河：《左偏树的特点及其应用》 跳表 2005- 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009- 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree 》线段树 2004- 林涛：《线段树的应用》 单调队列 2006- 汤泽：《浅析队列在一类单调性问题中的应用》哈希表2005- 李羽修：《Hash 函数的设计优化》 2007- 杨弋：《Hash 在信息学竞赛中的一类应用》 Splay 2004- 杨思雨：《伸展树的基本操作与应用》 图论 图论 2005- 任恺：《图论的基本思想及方法》
伸展树的基本操作与应用 安徽省芜湖一中杨思雨 目录 【关键字】 (2) 【摘要】 (2) 【引言】 (2) 【伸展树的基本操作】 (2) 伸展操作Splay(x,S) (3) 伸展树的基本操作 (4) 时间复杂度分析 (5) 【伸展树的应用】 (7) 【总结】 (8) 【参考书目】 (9) 【附录】 (9)
【关键字】 伸展树基本操作应用 【摘要】 本文主要介绍了伸展树的基本操作以及其在解题中的应用。全文可以分为以下四个部分。 第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高，进而引出了在时间复杂度上更为优秀的伸展树。 第二部分介绍了伸展树的基本操作。并给出了对伸展树时间复杂度的分析和证明，指出伸展树的各种基本操作的平摊复杂度均为O(log n)，说明伸展树是一种较平衡的二叉查找树。 第三部分通过一个例子介绍了伸展树在解题中的应用，并将它与其它树状数据结构进行了对比。 第四部分指出了伸展树的优点，总结全文。 【引言】 二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。 作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n 各节点的完全二叉树，这些操作的最坏情况运行时间为O(log n)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为O(n)。而有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、A VL树等等。 本文将要介绍的伸展树（Splay Tree），也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。 【伸展树的基本操作】 伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。
论随机化算法的原理与设计 上海市控江中学周咏基 [关键字] 随机化算法，稳定性 [摘要] 本文提出了一种新的解决信息学问题的算法——随机化算法，并讨论了其原理与设计方法。论文首先给出随机化算法的定义，说明了由于“运气”的影响，必须对随机化算法的稳定性进行分析。然后分“随机不影响算法的执行结果”，“随机影响执行结果的正确性”，“随机影响执行结果的优劣”三种情况，以从基本算法到竞赛试题中用随机化算法有效解决问题的例子，详细分析了三种情况的随机化算法的原理与设计方法。最后总结出随机化算法的基本原理和共同性质，提出设计随机化算法的一般方法，并指出随机化算法的适用范围和一个有效的随机化算法应具备的特点。 [正文] 1．引论 在这篇论文中，我们将研究一种新概念的算法——随机化算法。顾名思义，随机化就是指使用了随机函数。这里的随机函数不妨是Borland Pascal(或Turbo Pascal)中的RANDOM(N)，其返回值为[0,N-1]中的某个整数，且返回每个整数都是等概率的[1]。 一个含有随机函数的算法很可能[2]受到不确定因素的支配。人们通常认为，一个受到不确定因素支配的算法肯定不是一个有效的算法——正是在这种思维方式的支配下，随机化算法一直被冷落——但是，在接下来的讨论中，我们将看到完全相反的事情发生：对于一些特定的问题，随机化算法恰恰成了十分有效的解题工具，有时甚至比一般的非随机化算法做得更好。 随机化算法的定义 随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或间接地影响了算法的执行流程或执行结果。 根据这个定义，并不是所有的用了随机函数的算法都可称为随机化算法。例如，某个算法包含 i RANDOM(N)，
浅谈几类背包题 浙江省温州中学徐持衡指导老师：舒春平 2008年12月
目录 摘要 (3) 关键字 (3) 正文 (4) 一、引言 (4) 二、背包的基本变换 (5) ①完全背包 (5) ②多次背包 (5) ③单调队列优化☆ (6) 三、其他几类背包问题 (8) ①树形依赖背包（获取学分）☆ (8) ②PKU3093☆ (11) 四、总结 (12) 附录 (13) 参考文献 (13) 文中原题 (13)
摘要 背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以0-1背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。 本文就4道背包变化的题做一些探讨研究，提出本人的一些做法，希望能起到抛砖引玉的作用。 关键字 动态规划背包优化
正文 一、引言 背包问题是运筹学中的一个经典的优化难题，是一个NP-完全问题，但其有着广泛的实际应用背景，是从生活中一个常见的问题出发展开的：一个背包，和很多件物品，要在背包中放一些物品，以达到一定的目标。 在信息学中，把所有的数据都量化处理后，得到这样的一个问题： 0-1 背包问题：给定n 件物品和一个背包。物品i的价值是W i，其体积为V i，背包的容量为C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。 在选择装入背包的物品时，对每件物品i ，要么装入背包，要么不装入背包。不能将物品i 多次装入背包，也不能只装入部分物品i （分割物品i）。因此，该问题称为0-1 背包问题。 用于求解0-1背包问题的方法主要有回溯算法、贪婪算法、遗传算法、禁忌搜索算法、模拟退火算法等。 在高中阶段，我们所谓的经典0-1背包问题，保证了所有量化后的数据均为正整数，即是一个特殊的整数规划问题，本文中如无特殊说明均以此为前提。其经典的O(n*C)动规解法是： 状态是在前i件物品中，选取若干件物品其体积总和不大于j，所能获得的最大价值为F i[j]，当前的决策是第i件物品放或者不放，最终得到转移方程： F i[j] = F i-1[j] (V i>j>=0) F i[j] = max{ F i-1[j] , F i-1[j-V i]+W i } (C>=j>=V i) 其中由于F i只与F i-1有关，可以用滚动数组来节省程序的空间复杂度。以下就是经典算法的伪代码。 1.FOR i: = 1 TO n 2. FOR j: = C DOWNTO V i 3. Max ( F[ j ] , F[ j-V i ] + W i ) → F[ j ] 4. END FOR 5.END FOR
数学模型的建立、比较和应用 苏州中学邵铮 关键字: 数学模型算法母函数 【摘要】 数学模型是解决实际问题的一种基本工具。将实际问题抽象成一个数学模型，运用数学工具进行求解，并将结果应用于具有相同特征的一类问题中，是解决问题的一种基本的途径。本文首先介绍了数学模型的一些性质，然后建立了三种不同的数学模型来求解一个问题，将三种数学模型相互比较，得出数学模型抽象性与高效性之间的关系，再将数学模型推广应用于另两个问题的求解，得出数学模型抽象性与可推广性之间的关系，最后总结全文，揭示出有关数学模型的一些普遍规律。 一、引论 实际问题往往是纷繁而复杂的，而其中的规律也是隐藏着的，要想直接用计算机来求解实际问题往往有一定的困难。计算机擅长的是解决数学问题。因此，我们有必要将实际问题抽象成数学模型，然后再用计算机来对数学模型进行求解。 与实际问题相比，数学模型有以下几个性质： 抽象性：数学模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。这一点是下面两个性质的基础。 高效性：数学模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解的效率。由于这一点是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型效率的高低有重要的影响，这一点将在第二部分中详细阐述。 可推广性：数学模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个数学模型就解决了一类实际问题。这里的“相同性质”是指相同的本质，表面看似毫不相干的问题可能有着相同的本质。由于这一点也是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型的推广范围也有重要的影响，这一点将在第三部分中详细阐述。 二、数学模型的建立和比较 由于考虑问题的角度不同，面对同一个实际问题，可能建立起各种各样的数学模型。在各种数学模型中，我们要寻找的是效率高的模型。模型的效率同模型的抽象化程度有关，下面从一个实例中来分析它们之间的具体关系。 【多边形分割问题】将一个凸n边形用n-3条互不相交的对角线分割为n-2
浅谈用极大化思想解决最大子矩形问题 福州第三中学王知昆 【摘要】 本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变形问题，介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。 【关键字】矩形，障碍点，极大子矩形 【正文】 一、问题 最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。 这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大子矩形问题。 Winter Camp2002,奶牛浴场 题意简述：（原题见论文附件） John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何一个奶牛的产奶点，但产奶点可以出在浴场的边界上。John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴场的面积尽可能大。 参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。 二、定义和说明 首先明确一些概念。 1、定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。
2、极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形） 3、定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。以下简称为最大子矩形。 三、极大化思想 【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。 证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存在一个包含A且比A更大的有效子矩形，这与“A是最大子矩形”矛盾，所以【定理1】成立。 四、从问题的特征入手，得到两种常用的算法 定理1虽然很显然，但却是很重要的。根据定理1，我们可以得到这样一个解题思路：通过枚举所有的极大子矩形，就可以找到最大子矩形。下面根据这个思路来设计算法。 约定：为了叙述方便，设整个矩形的大小为n×m，其中障碍点个数为s。 算法1 算法的思路是通过枚举所有的极大子矩形找出最大子矩形。根据这个思路可以发现，如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子矩形，那么可以肯定这个算法做了“无用功”，这也就是需要优化的地方。怎样保证每次枚举的都是极大子矩形呢，我们先从极大子矩形的特征入手。 【定理2】：一个极大子矩形的四条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖了一个障碍点，要么与整个矩形的边界重合。
浅谈数形结合思想在信息学竞赛中的应用 安徽省芜湖一中周源 目录 目录 (1) 摘要 (2) 关键字 (2) 引子 (3) 以形助数 (3) [例一]Raney引理的证明 (3) [题意简述] (3) [分析] (3) 目标图形化 (3) 小结 (4) [例二]最大平均值问题(USACO 2003 March Open) (4) [题意简述] (4) [分析] (5) 目标图形化 (5) 构造下凸折线 (5) 维护下凸折线 (6) 最后的优化：利用图形的单调性 (7) 小结 (7) 以数助形 (7) [例三]画室(POI oi V Stage I) (8) [题意简述] (8) [分析] (8) 目标数值化 (9) 动态规划解题 (9) 小结 (10) 总结 (10) 附录 (11) 关于2003年上海市选拔赛题Sequence (11) [题意简述] (11) [分析] (11) 论文附件 (12) 参考文献 (12)
摘要 数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。 本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。 最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。 关键字 信息学竞赛数学思想数形结合思想 以数助形以形助数 辩证矛盾多元性个体差异性 思维、编程、时间、空间复杂度
引子 数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。 在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。 数形结合思想常包括以形助数、以数助形两个方面。 以形助数 正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。 [例一]Raney引理的证明 [题意简述] 设整数序列A = {A i, i=1, 2, …, N}，且部分和S k=A1+…+A k，序列中所有的数字的和S N=1。 证明：在A的N个循环表示1中，有且仅有一个序列B，满足B的任意部分和S i均大于零。 [分析] 先来看一个例子，若有序列A = <1, 4, -5, 3, -2, 0>，其6个循环表示为 1.<1, 4, -5, 3, -2, 0> 2.<4, -5, 3, -2, 0, 1> 3.<-5, 3, -2, 0, 1, 4> 4.<3, -2, 0, 1, 4, -5> 5.<-2, 0, 1, 4, -5, 3> 6.<0, 1, 4, -5, 3, -2> 其中只有第4个序列，部分和为3, 1, 1, 2, 6, 1，满足成为序列B的条件。 若要用一般的代数或是组合方法来证明这个有趣的结论，似乎无从下手，但若要想到了用“形”来帮忙，问题就简单多了。 目标图形化 周期性的推广A序列，得到一个无穷序列，便于观察其循环表示，得到： 1先设一个序列是环状的，则从其任意一个字符处断开以后形成的非环序列即为该序列的一个循环表示。
分治算法在树的路径问题中的应用 【摘要】 树作为一类特殊的数据结构，在信息学中有着极为重要的作用，各类关于树的题目在竞赛中更是屡见不鲜。本文选取了近几年出现的关于树的路径的题目，并结合例题讲解了分治算法在此类问题上的应用。 【关键字】 树路径路径剖分分治数据结构
【目录】 【序言】 (3) 【正文】 (4) 一.树的分治算法 (4) 基于点的分治： (4) 基于边的分治： (4) 效率分析： (5) 【例1】树中点对统计 (8) 算法分析 (8) 【例2】Free Tour 2 (10) 算法分析 (10) 【本节小结】 (13) 二．树的路径剖分算法： (14) 【例3】Query On a Tree (14) 算法分析 (14) 引入路径剖分 (14) 轻重边路径剖分 (15) 【例4】黑白树 (17) 算法分析 (17) 【小结】 (18) 路径剖分与树的分治的联系： (19) 【例5】Query On a Tree Ⅳ (20) 算法分析 (20) 【本节小结】 (23) 三．树的分治的进一步探讨： (24) 如何改进基于边的分治的时间复杂度 (24) 使用基于边的分治解决【例2】 (26) 使用基于边的分治解决【例5】 (27) 四．全文总结 (28) 【参考文献】 (29) 【感谢】 (29) 【附录】 (29)
树被定义为没有圈的连通图，具有以下几个性质： 1.在树中去掉一条边后所得的图是不连通的。 2.在树中添加一条边后所得的图一定存在圈。 3.树的每一对顶点U和V之间有且仅有一条路径。 由于树具有一般图所没有的特点，因此在竞赛中有着更加广泛的应用，尤其是关于树中路径的问题，即一类以路径为询问对象的题目，更是频繁的出现在各种比赛中，每一个有志于OI及ACM的选手都应该掌握这类问题的算法。 分治，指的是分而治之，即将一个问题分割成一些规模较小的相互独立的子问题，以便各个击破。我们常见的是在一个线性结构上进行分治，而在本文中我们将会讲解分治算法在树结构上的运用，称之为树的分治算法。 分治往往与高效联系在一起，而树的分治正是一种用来解决树的路径问题的高效算法。 下面让我们一起来感受树的分治算法的美妙吧。