《算法合集之《浅谈信息学竞赛中的“压缩法”》》由会员分享，可在线阅读，更多相关《算法合集之《浅谈信息学竞赛中的“压缩法”》（20页珍藏版）》请在金锄头文库上搜索。
1、2005 年信息学奥林匹克竞赛冬令营论文 安徽 周源压去冗余压去冗余 缩得精华缩得精华浅谈信息学竞赛中的浅谈信息学竞赛中的“压缩法压缩法”安徽 周源压去冗余 缩得精华 浅谈信息学竞赛中的“压缩法” 安徽 周 源第 2 页 共 20 页摘要摘要在信息学竞赛中，我们经常遇到这样一类问题：数据规模大，在信息学竞赛中，我们经常遇到这样一类问题：数据规模大，或是数据间的关系复杂，总而言之即输入数据的信息量过大。或是数据间的关系复杂，总而言之即输入数据的信息量过大。作者在综合分析了很多信息学竞赛试题后，提出了作者在综合分析了很多信息学竞赛试题后，提出了“压缩法压缩法”这个概念：即压去输入数据中的冗余信息，
2、保留下对解决问题有帮这个概念：即压去输入数据中的冗余信息，保留下对解决问题有帮助的精华部分。压缩法在信息学竞赛中有着广泛的应用，但在各类助的精华部分。压缩法在信息学竞赛中有着广泛的应用，但在各类问题中却有看起来截然不同的表现形式，本文即将选择多道有代表问题中却有看起来截然不同的表现形式，本文即将选择多道有代表性的例题，提炼它们的共同点，提出压缩法适用问题的两个要点。性的例题，提炼它们的共同点，提出压缩法适用问题的两个要点。最后，作者将在总结部分着重分析压缩法的工作特点，认为压缩法最后，作者将在总结部分着重分析压缩法的工作特点，认为压缩法是在化归思想的基础上，加上了是在化归思想的基础上，加上了“
3、信息化信息化”的因素，通过合理的利的因素，通过合理的利用信息达到化简问题的目的。用信息达到化简问题的目的。关键字关键字信息学竞赛信息学竞赛 压缩法压缩法冗余冗余/ /精华信息精华信息可压缩性可压缩性 替代法则替代法则 化归思想化归思想 信息化信息化压去冗余 缩得精华 浅谈信息学竞赛中的“压缩法” 安徽 周 源第 3 页 共 20 页目录目录压去冗余 缩得精华.1浅谈信息学竞赛中的“压缩法”.1摘要.2 关键字.2 目录.3 引子.4 压缩法的定义.4 压缩法的简单实例.4 例一多源最短路问题（经典问题）.4 例二球队问题（经典问题）.5 压缩法的要点.7 1.可压缩性.7 2.替代法则.7 例
4、三模方程组的替代法则（经典问题）.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压去冗余 缩得精华 浅谈信息学竞赛中
5、的“压缩法” 安徽 周 源第 4 页 共 20 页引子引子可能不少同学都对题目中“压缩法”这个名词感到很陌生，不错，因为这 是作者自己发明的一个名词。这篇论文就将带领大家走近我所说的“压缩 法” ，熟悉“压缩法” 。 看到“压缩”二字，可能有的同学会想到我们常用的压缩软件，如 WinZip, WinRAR 等等，他们都是想尽办法的减小文件占用的空间来为我们服 务。这正是压缩一词的本义，即“加以压力,以减小体积、大小、持续时间、 密度和浓度等”1。 然而本文中要讨论的“压缩法”的含义则为：“除去冗余信息，留下精华， 以减小问题的规模” ，看得出，这正是为信息学竞赛量身定制一种好方法。 下面，就让
6、我们看看压缩法在竞赛中的精彩表现吧！压缩法的定义压缩法的定义一般来说，当我们处理问题时常常遇到一个集合 S，S 内部各个元素之间 的关系对问题的结果不造成影响，而且也不会受到外部因素的干扰，那么我 们可以将 S 看作一个内外隔绝的包裹（包裹（package） ，忽略包裹内部的冗余信息， 并将这个包裹与外部事物的联系保留，打包、压缩后压缩后作为一个新的元素存储 下来以供以后分析处理。 这就是压缩法工作的基本流程，其好处在于略去了包裹内部种种纷扰却无 用的信息，从而化简了问题，进而用更好的方法去解决问题。压缩法的简单实例压缩法的简单实例其实我们对压缩法并不陌生，相信大家对下面两个例子都有一定的了解。例一多源最短路问题（经典问题）如下图。在一个加正权的有向图 G = V, E中，给出源的位置，求源到其 余所有点的最短路长度。与一般最短路问题不同的是，本题中源是一个集合 S 中的所有点。而 S 到某一个点 p 的最短距离等于 S 中所有点与 p 最短距离 的最小值。21 摘录自高级汉语大词典 。
