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

IOI2005冬令营演示文稿安徽周源压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源IOI2005冬令营演示文稿安徽周源引子•压缩软件？–本义：加以压力,以减小体积、大小、持续时间、密度和浓度等•压缩法–除去冗余信息，留下精华，以减小问题的规模IOI2005冬令营演示文稿安徽周源压缩法的定义•将集合S作为内外隔绝的包裹打包压缩•略去了包裹内部的冗余信息，从而简化问题SIOI2005冬令营演示文稿安徽周源[例二]球队问题(经典问题)•篮球队的球员通讯图，(B,A)表示B能通知A•教练需要通知所有人一条消息•最少需要告诉几个人？•本例中最少为2人–如A,F等等ABCDEFG亲自IOI2005冬令营演示文稿安徽周源[例二]球队问题(经典问题)•使用压缩法，“压去”不必要的信息–求出强连通分量S1,S2,S3…–“压缩”•每个分量新点•保留分量间连边情况ABCDEFGS1S3S2IOI2005冬令营演示文稿安徽周源[例二]球队问题(经典问题)•压缩转化后的新图–简洁：没有环的存在–无入度的点：必须亲自通知–有入度的点：必定可以由队员通知•结论：答案为压缩后图中无入度点的数目S1S3S2IOI2005冬令营演示文稿安徽周源压缩法的要点•1.可压缩性–集合S内部各个元素之间的联系不会和外部元素相互作用而影响到问题的结果即可压缩–[例二]中：•强连通分量内球员的通讯情况不会影响球员是否得知消息状态的恒等性•舍去分量内球员的通讯情况，压缩为新的节点IOI2005冬令营演示文稿安徽周源压缩法的要点–压：可以压去存在的冗余信息(可压缩性)–缩：保留S作为一个点与外部信息的联系(替代法则)•2.替代法则–用什么样的形式表现出精华部分的内容–[例二]中•用一个点替代一个集合•用相同形式的有向边代替原来集合的内外联系IOI2005冬令营演示文稿安徽周源压缩法的应用•压缩法在很多竞赛试题中有巧妙的应用–[例四]欧元兑换(BOI2003euro)–[例五]合并数列问题(ZOJp1794)[例五]合并数列问题(ZOJp1794改编)IOI2005冬令营演示文稿安徽周源[例五]合并数列问题(ZOJp1794改编)•有K个数列a1,1,a1,2,a1,3…a1,n1a2,1,a2,2,a2,3…a2,n2…ak,1,ak,2,ak,3…ak,nk•如K=3时35-45-106-35-104-515-205-13-42-6IOI2005冬令营演示文稿安徽周源[例五]合并数列问题(ZOJp1794改编)•如K=3时•要求将这些数列归并成为一个新的数列S35-45-106-35-104-515-205-13-42-65-104-55-13-42-635-45-1015-206-3S：•且新数列S的部分和中最大的数最小最大部分和为7•有K个数列a1,1,a1,2,a1,3…a1,n1a2,1,a2,2,a2,3…a2,n2…ak,1,ak,2,ak,3…ak,nk•数据范围K≤100000N=n1+n2+…+nk≤100000IOI2005冬令营演示文稿安徽周源初步分析•普通动态规划算法–时间复杂度O(K*NK)–显然无法承受IOI2005冬令营演示文稿安徽周源观察压缩要点•1.可压缩性–观察：最优串中的一些子串就是原串的子串–反之：若原串的子串满足性质P即为S的子串–该子串可压缩，P就是可压缩性35-45-106-35-104-515-205-13-42-6最优串S：5-104-55-13-42-6……5-104-55-104-55-13-42-65-13-42-6IOI2005冬令营演示文稿安徽周源观察压缩要点•2.替代法则–若存在一段可压缩的子串u–替代法则保存u内元素与外部因素间的联系•a)u的最大部分和(即相对峰值)可能是S的最大部分和•b)u的总和对以后的部分和产生影响相对峰值总和替代法则u的部分和–用连续的两个数a,b代替•a为u的相对峰值b为非正的修正值•(a+b)为u的总和ab(a+b)a一“对”(couple)IOI2005冬令营演示文稿安徽周源寻找可压缩性：第一阶段压缩•[定理5.1]–某子串c1,c2,…,cp可压缩当–总和非正其余部分和为正数c•[证明5.1]–调整法–若c在S中不连续出现则可调整–具体方法参见论文IOI2005冬令营演示文稿安徽周源寻找可压缩性：第一阶段压缩35-45-105-104-515-205-13-42-6•[定理5.1]–某子串c1,c2,…,cp可压缩当–总和非正其余部分和为正数•压缩转化后–每个数列的前一部分•每一“对”的总和都是负数（或0）•正数后有一个绝对值更大的负数–每个数列的后一部分•一串任意部分和为正的子列•作为对称问题考虑(9-10)(7-8)6-3IOI2005冬令营演示文稿安徽周源寻找可压缩性：第二阶段压缩•[定理5.2]和[推论5.2.1]–若在一个数列中–存在连续多个“对”–当峰值在第一“对”，则可压缩•证明依然使用调整法•压缩转化后•每一“对”在数列中的相对峰值递增35-45-105-104-515-205-13-42-6(9-10)(7-8)(5-11)6-3IOI2005冬令营演示文稿安徽周源最后的贪心•贪心算法–由于每一“对”的总和为负–相对峰值大的尽量向后放–将每一“对”按相对峰值归并排序即可–时间复杂度：O(Nlog2K)35-45-105-104-55-13-42-6(9-10)(7-8)(5-11)6-35-117-89-1015-206-315-20S:部分和:05-61-72-87-13-7-10第一阶段压缩成果第二阶段压缩成果IOI2005冬令营演示文稿安徽周源[例五]合并数列问题(ZOJp1794改编)•小结–第一阶段压缩：正数后总有绝对值更大的负数–第二阶段压缩：负数后总有绝对值更大的正数–得到精华信息：一个个“对”的相对峰值递增–为贪心法解题创造了良好的条件IOI2005冬令营演示文稿安徽周源总结换元法[例二]球队问题[例五]合并数列问题强连通分量一个点复杂的联系图有向无环图一段子串一个“单峰”K个任意数列美妙的单调性t2+1+t=7化归思想无理有理复杂简单抽象形象t压缩法化归思想IOI2005冬令营演示文稿安徽周源总结化归思想压缩法两个要点可压缩性替代法则：存在冗余：除去冗余除去冗余合理利用信息化难为易化繁为简IOI2005冬令营演示文稿安徽周源压去冗余缩得精华当题设条件过多、信息量过大，无从下手时