算法合集之《浅谈信息学竞赛中的“压缩法”》

《算法合集之《浅谈信息学竞赛中的“压缩法”》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、压去冗余缩潯精华——肉淡信息学丸赛中的“压缩矗”安徽周源摘要在信息学竞赛中，我们经常遇到这样一类问题：数据规模大，或是数据间的关系复杂，总而言之即输入数据的信息量过大。作者在综合分析了很多信息学竞赛试题后，提出了“压缩法”这个概念：即压去输入数据中的冗余信息，保留下对解决问题有帮助的精华部分。压缩法在信息学竞赛中有着广泛的应用，但在各类问题中却有看起来截然不同的表现形式，本文即将选择多道有代表性的例题，提炼它们的共同点，提出压缩法适用问题的两个要点。最后，作者将在总结部分着重分析压缩法的工作特点，认为压缩法是在化归思想的基础上，加上了“信息化”的因素，通过合理的利用信息达到化

2、简问题的目的。关键字信息学竞赛压缩法冗余/精华信息可压缩性替代法则化归思想信息化目录压去冗余缩得精华1——戌淡信息学克塞中的“压缩法”1摘要2关键字2H录3引子4压缩法的定义4压缩法的简单实例4［例一］多源最短路问题（经典问题）4［例二］球队问题（经典问题）5压缩法的要点71.可圧缩性72.替代法则7［例三］模方程纽的替代法则（经典问题）7压缩法的应用8［例四］欧元兑换（BOI2003）8［分析］9［动态规划的矛盾］9［压缩法化解矛盾］10［小结］12［例五］合并数列问题（ZOJpl794MergingSequenceProblem改编）12［分析］13［观察压缩耍点］13［

3、寻找可压缩性：第一阶段压缩］14［寻找可压缩性：第二阶段压缩］16［贪心法解题］17［小结］17总结18附录19附录一：关于［例四］中的斜率优化法19附录二：论文附件19附录三：关于MergeSequence.pas程序的输入格式20参考文献20引子可能不少同学都对题目中“压缩法”这个名词感到很陌生，不错，因为这是作者自己发明的一个名词©。这篇论文就将带领人家走近我所说的“压缩法”，熟悉“压缩法”。看到“压缩”二字，可能有的同学会想到我们常用的压缩软件，如WinZip,WinRAR等等，他们都是想尽办法的减小文件占用的空间來为我们服务。这正是压缩一词的木义，即“加以压力,以减

4、小体积、大小、持续时间、密度和浓度等”1O然而木文中要讨论的“压缩法”的含义则为：“除去冗余信息，留下精华,以减小问题的规模”，看得出，这正是为信息学竞赛量身定制一种好方法。下面，就让我们看看压缩法在竞赛中的精彩表现吧！压缩法的定义一般来说，当我们处理问题时常常遇到一个集合S,S内部各个元素之间的关系对问题的结果不造成影响，而且也不会受到外部因素的干扰，那么我们可以将S看作一个内外隔绝的包裹(package),忽略包裹内部的兀余信息，并将这个包裹与外部事物的联系保留，打包、压缩后作为一个新的元素存储下来以供以后分析处理。这就是压缩法工作的基本流程，其好处在于略去了包裹内部种种

5、纷扰却无用的信息，从而化简了问题，进而用更好的方法去解决问题。压缩法的简单实例其实我们对压缩法并不陌生，相信大家对下面两个例子都有一定的了解。［例一］多源最短路问题(经典问题)如下图。在一个加正权的有向图G={V,E}中，给出源的位置，求源到其余所有点的最短路长度。与-•般最短路问题不同的是，木题屮源是一个集合S中的所有点。而S到某一个点p的最短距离等于S中所有点与p最短距离的最小值。2'摘录自《高级汉语大词典》。图屮边上的数值为边的权值，顶点后JS号内的数值为到该点最短路的长度。图1［分析］这道题日的关键在于有多个源，而为了提高效率，只能执行一次Dijkstra算法。其实这

6、是很简单的，很多不同的方法都可以做到这一点。卜-面让我们看一看压缩法是怎么实现的：可以看出，由于不可能有一条最短路径从一个源点出发却又经过另外一个源点，因此源点集合S中任何两点间的连边关系对答案都没有影响。如上文所述，可以将S视为一个内外隔绝的“包裹”，舍去包裹内的冗余信息，并将其“压缩”成为一个新的点凡。另一方面，我们还需要保留S小节点对外的连边情况作为压缩后节点Ps的对外连边。这样，我们就成功的完成了压缩流程，得到的是一张新图和一个单源最短路问题：这正是Dijkstra所做的。Ps图2［例二］球队问题（经典问题）给出某个篮球队的球员通讯图G={V,E}如下，若存在有向边（

7、仏y）表示球员"可将消息及时告诉门若教练想将一条紧急消息告知给全体队员，利用这个通讯图，他至少要亲自通知几个队员？CED图3［分析］看着这个朵乱无章的通讯图，我们决定还是使用压缩法“压去”一些不必要的关系，简化题设条件。分析图中的每一个强连通分量S,若S中的某一个球员得知了消息，那么显然S中其他所有的队员都可以及时获得消息。即S中何:一个球员是否得知消息的状态都是相等的，如果有必更的话，教练最多只会通知S中的一个球员。此时保留S中的通讯边己经毫无意义，我们可以舍去它们，并将S压缩成为一个点Ps，并保留s