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

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

1、压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源第20页共20页压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源摘要在信息学竞赛中，我们经常遇到这样一类问题：数据规模大，或是数据间的关系复杂，总而言之即输入数据的信息量过大。作者在综合分析了很多信息学竞赛试题后，提出了“压缩法”这个概念：即压去输入数据中的冗余信息，保留下对解决问题有帮助的精华部分。压缩法在信息学竞赛中有着广泛的应用，但在各类问题中却有看起来截然不同的表现形式，本文即将选择多道有代

2、表性的例题，提炼它们的共同点，提出压缩法适用问题的两个要点。最后，作者将在总结部分着重分析压缩法的工作特点，认为压缩法是在化归思想的基础上，加上了“信息化”的因素，通过合理的利用信息达到化简问题的目的。关键字信息学竞赛压缩法冗余/精华信息可压缩性替代法则化归思想信息化第20页共20页压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源目录压去冗余缩得精华1——浅谈信息学竞赛中的“压缩法”1摘要2关键字2目录3引子4压缩法的定义4压缩法的简单实例4[例一]多源最短路问题（经典问题）4[例二]球队问题（经典问题）5压

3、缩法的要点71.可压缩性72.替代法则7[例三]模方程组的替代法则（经典问题）7压缩法的应用8[例四]欧元兑换（BOI2003）8[分析]9[动态规划的矛盾]9[压缩法化解矛盾]10[小结]12[例五]合并数列问题（ZOJp1794MergingSequenceProblem改编）12[分析]13[观察压缩要点]13[寻找可压缩性：第一阶段压缩]14[寻找可压缩性：第二阶段压缩]16[贪心法解题]17[小结]17总结18附录19附录一：关于[例四]中的斜率优化法19附录二：论文附件19附录三：关于MergeSeque

4、nce.pas程序的输入格式20参考文献20第20页共20页压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源引子可能不少同学都对题目中“压缩法”这个名词感到很陌生，不错，因为这是作者自己发明的一个名词J。这篇论文就将带领大家走近我所说的“压缩法”，熟悉“压缩法”。看到“压缩”二字，可能有的同学会想到我们常用的压缩软件，如WinZip,WinRAR等等，他们都是想尽办法的减小文件占用的空间来为我们服务。这正是压缩一词的本义，即“加以压力,以减小体积、大小、持续时间、密度和浓度等”摘录自《高级汉语大词典》。。然而

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

6、了包裹内部种种纷扰却无用的信息，从而化简了问题，进而用更好的方法去解决问题。压缩法的简单实例其实我们对压缩法并不陌生，相信大家对下面两个例子都有一定的了解。[例一]多源最短路问题（经典问题）如下图。在一个加正权的有向图G={V,E}中，给出源的位置，求源到其余所有点的最短路长度。与一般最短路问题不同的是，本题中源是一个集合S中的所有点。而S到某一个点p的最短距离等于S中所有点与p最短距离的最小值。图中边上的数值为边的权值，顶点后括号内的数值为到该点最短路的长度。第20页共20页压去冗余缩得精华——浅谈信息学竞赛中的“

7、压缩法”安徽周源(2)(3)(4)AS1S3232BCDE132(3)(2)212S2图1[分析]这道题目的关键在于有多个源，而为了提高效率，只能执行一次Dijkstra算法。其实这是很简单的，很多不同的方法都可以做到这一点。下面让我们看一看压缩法是怎么实现的：可以看出，由于不可能有一条最短路径从一个源点出发却又经过另外一个源点，因此源点集合S中任何两点间的连边关系对答案都没有影响。如上文所述，可以将S视为一个内外隔绝的“包裹”，舍去包裹内的冗余信息，并将其“压缩”成为一个新的点PS。另一方面，我们还需要保留S中节点

8、对外的连边情况作为压缩后节点PS的对外连边。这样，我们就成功的完成了压缩流程，得到的是一张新图和一个单源最短路问题：这正是Dijkstra所做的。(3)(4)(2)232ABCDE1322(3)(2)PS图2[例二]球队问题（经典问题）给出某个篮球队的球员通讯图G={V,E}如下，若存在有向边(u,v)表示球员u可将消息及时告诉v，若教练想将一