国家集训队论文集周源.docVIP

压去冗余 缩得精华 ——浅谈信息学竞赛中的“压缩法” 安徽 周源 摘要 在信息学竞赛中，我们经常遇到这样一类问题：数据规模大，或是数据间的关系复杂，总而言之即输入数据的信息量过大。 作者在综合分析了很多信息学竞赛试题后，提出了“压缩法”这个概念：即压去输入数据中的冗余信息，保留下对解决问题有帮助的精华部分。压缩法在信息学竞赛中有着广泛的应用，但在各类问题中却有看起来截然不同的表现形式，本文即将选择多道有代表性的例题，提炼它们的共同点，提出压缩法适用问题的两个要点。最后，作者将在总结部分着重分析压缩法的工作特点，认为压缩法是在化归思想的基础上，加上了“信息化”的因素，通过合理的利用信息达到化简问题的目的。 关键字 信息学竞赛 压缩法 冗余/精华信息 可压缩性 替代法则 化归思想 信息化 目录 压去冗余 缩得精华 1 ——浅谈信息学竞赛中的“压缩法” 1 摘要 2 关键字 2 目录 3 引子 4 压缩法的定义 4 压缩法的简单实例 4 [例一]多源最短路问题（经典问题） 4 [例二]球队问题（经典问题） 5 压缩法的要点 7 1. 可压缩性 7 2. 替代法则 7 [例三]模方程组的替代法则（经典问题） 7 压缩法的应用 8 [例四]欧元兑换（BOI 2003） 8 [分析] 9 [动态规划的矛盾] 9 [压缩法化解矛盾] 10 [小结] 12 [例五]合并数列问题（ZOJ p1794 Merging Sequence Problem改编） 12 [分析] 13 [观察压缩要点] 13 [寻找可压缩性：第一阶段压缩] 14 [寻找可压缩性：第二阶段压缩] 16 [贪心法解题] 17 [小结] 17 总结 18 附录 19 附录一：关于[例四]中的斜率优化法 19 附录二：论文附件 19 附录三：关于MergeSequence.pas程序的输入格式 20 参考文献 20 引子 可能不少同学都对题目中“压缩法”这个名词感到很陌生，不错，因为这是作者自己发明的一个名词(。这篇论文就将带领大家走近我所说的“压缩法”，熟悉“压缩法”。 看到“压缩”二字，可能有的同学会想到我们常用的压缩软件，如WinZip, WinRAR等等，他们都是想尽办法的减小文件占用的空间来为我们服务。这正是压缩一词的本义，即“加以压力,以减小体积、大小、持续时间、密度和浓度等”。 然而本文中要讨论的“压缩法”的含义则为：“除去冗余信息，留下精华，以减小问题的规模”，看得出，这正是为信息学竞赛量身定制一种好方法。 下面，就让我们看看压缩法在竞赛中的精彩表现吧！ 压缩法的定义 一般来说，当我们处理问题时常常遇到一个集合S，S内部各个元素之间的关系对问题的结果不造成影响，而且也不会受到外部因素的干扰，那么我们可以将S看作一个内外隔绝的包裹（package），忽略包裹内部的冗余信息，并将这个包裹与外部事物的联系保留，打包、压缩后作为一个新的元素存储下来以供以后分析处理。 这就是压缩法工作的基本流程，其好处在于略去了包裹内部种种纷扰却无用的信息，从而化简了问题，进而用更好的方法去解决问题。 压缩法的简单实例 其实我们对压缩法并不陌生，相信大家对下面两个例子都有一定的了解。 [例一]多源最短路问题（经典问题） 如下图。在一个加正权的有向图G = {V, E}中，给出源的位置，求源到其余所有点的最短路长度。与一般最短路问题不同的是，本题中源是一个集合S中的所有点。而S到某一个点p的最短距离等于S中所有点与p最短距离的最小值。 图 1 [分析] 这道题目的关键在于有多个源，而为了提高效率，只能执行一次Dijkstra算法。 其实这是很简单的，很多不同的方法都可以做到这一点。下面让我们看一看压缩法是怎么实现的： 可以看出，由于不可能有一条最短路径从一个源点出发却又经过另外一个源点，因此源点集合S中任何两点间的连边关系对答案都没有影响。如上文所述，可以将S视为一个内外隔绝的“包裹”，舍去包裹内的冗余信息，并将其“压缩”成为一个新的点PS。 另一方面，我们还需要保留S中节点对外的连边情况作为压缩后节点PS的对外连边。 这样，我们就成功的完成了压缩流程，得到的是一张新图和一个单源最短路问题：这正是Dijkstra所做的。 图 2 [例二]球队问题（经典问题） 给出某个篮球队的球员通讯图G = {V, E}如下，若存在有向边(u, v)表示球员u可将消息及时告诉v，若教练想将一条紧急消息告知给全体队员，利用这个通讯图，他至少要亲自通知几个队员？ 图 3 [分析] 看着这个杂乱无章的通讯图，我们决定还是使用压缩法“压去”一些不必要的关系，简化题设条件。 分析图中的每一个强连通分量S，若S中的某一个球员得知了消息，那么显然S中其他所有的队员都可以及时获得消息