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

1、IOI2005冬令营演示文稿安徽周源IOI2005冬令营演示文稿安徽周源 压缩软件？本义：加以压力,以减小体积、大小、持续时间、密度和浓度等 压缩法除去冗余信息，留下精华，以减小除去冗余信息，留下精华，以减小问题的规模问题的规模 压缩法？IOI2005冬令营演示文稿安徽周源 将集合S作为内外隔绝的包裹打包压缩 略去了包裹内部的冗余信息，从而简化问题SIOI2005冬令营演示文稿安徽周源 篮球队的球员通讯图，(B, A)表示B能通知A 教练需要通知所有人一条消息 最少需要 告诉几个人？ 本例中最少为2人如A, F等等ABCDEFG亲自IOI2005冬令营演示文稿安徽周源 使用压缩法，“压去”不必

2、要的信息求出强连通分量 S1, S2, S3“压缩”每个分量新点保留分量间连边情况ABCDEFGS1S3S2IOI2005冬令营演示文稿安徽周源 压缩转化后的新图简洁：没有环的存在无入度的点： 必须亲自通知有入度的点： 必定可以由队员通知 结论：答案为 压缩后图中无入度点的数目压缩后图中无入度点的数目S1S3S2IOI2005冬令营演示文稿安徽周源 1.可压缩性集合S内部各个元素之间的联系不会和外部元素相互作用而影响到问题的结果即可压缩例二中： 强连通分量内球员的通讯情况不会影响强连通分量内球员的通讯情况不会影响 球员是否得知消息状态的恒等性球员是否得知消息状态的恒等性 舍去舍去分量内球员的通

3、讯情况，压缩压缩为新的节点IOI2005冬令营演示文稿安徽周源压压：可以压去存在的冗余信息 (可压缩性)缩：保留S作为一个点与外部信息的联系 (替代法则) 2.替代法则用什么样的形式 表现出精华部分的内容例二中用一个点替代一个集合用相同形式的有向边代替原来集合的内外联系IOI2005冬令营演示文稿安徽周源 压缩法在很多竞赛试题中有巧妙的应用例四欧元兑换(BOI 2003 euro)例五合并数列问题(ZOJ p1794)IOI2005冬令营演示文稿安徽周源 有K个数列a1,1, a1,2, a1,3a1,n1a2,1, a2,2, a2,3a2,n2 ak,1, ak,2, ak,3ak,nk

4、如K=3时3 5 -4 5 -10 6 -35 -10 4 -5 15 -205 -1 3 -4 2 -6IOI2005冬令营演示文稿安徽周源 如K=3时 要求将这些数列归并归并成为一个新的数列S3 5 -4 5 -10 6 -35 -10 4 -5 15 -205 -1 3 -4 2 -65 -10 4 -5 5 -1 3 -4 2 -6 3 5 -4 5 -10 15 -20 6 -3S：且新数列S的部分和中最大的数最小最大的数最小最大部分和为7 有K个数列a1,1, a1,2, a1,3a1,n1a2,1, a2,2, a2,3a2,n2 ak,1, ak,2, ak,3ak,nk 数据

5、范围K 100000N = n1 + n2 + + nk 100000IOI2005冬令营演示文稿安徽周源 普通动态规划算法时间复杂度O(K*NK)显然无法承受IOI2005冬令营演示文稿安徽周源 1.可压缩性观察：最优串中的一些子串就是原串的子串反之：若原串的子串满足性质P即为S的子串该子串可压缩，该子串可压缩，P就是可压缩性就是可压缩性3 5 -4 5 -10 6 -35 -10 4 -5 15 -205 -1 3 -4 2 -6最优串S：5 -10 4 -5 5 -1 3 -4 2 -6 5 -10 4 -55 -10 4 -5 5 -1 3 -4 2 -65 -1 3 -4 2 -6I

6、OI2005冬令营演示文稿安徽周源 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冬

7、令营演示文稿安徽周源3 5 -4 5 -105 -10 4 -5 15 -205 -1 3 -4 2 -6 定理5.1某子串c1, c2, , cp可压缩当 总和非正总和非正 其余部分和为正数其余部分和为正数 压缩转化后 每个数列的前一部分 每一“对”的总和都是负数（或0） 正数后有一个绝对值更大的负数正数后有一个绝对值更大的负数 每个数列的后一部分 一串任意部分和为正的子列 作为对称问题考虑( 9 -10 )( 7 -8 )6 -3IOI2005冬令营演示文稿安徽周源 定理5.2和推论5.2.1若在一个数列中存在连续多个“对”当峰值在第一“对”，则可压缩 证明依然使用调整法调整法 压缩转化后

8、 每一每一“对对”在数列中的相对峰在数列中的相对峰值递增值递增3 5 -4 5 -105 -10 4 -5 15 -205 -1 3 -4 2 -6( 9 -10 )( 7 -8 )( 5 -11 )6 -3IOI2005冬令营演示文稿安徽周源 贪心算法由于每一“对”的总和为负相对峰值大大的尽量向后向后放将每一“对”按相对峰值归归并排序并排序即可时间复杂度：O(Nlog2K)3 5 -4 5 -105 -10 4 -55 -1 3 -4 2 -6( 9 -10 )( 7 -8 )( 5 -11 )6 -35 -117 -89 -1015 -206 -315 -20S:部分和:0 5 -6 1

9、-7 2 -8 7 -13 -7 -10第一阶段压缩成果第二阶段压缩成果IOI2005冬令营演示文稿安徽周源 小结第一阶段压缩：正数后总有绝对值更大的负数正数后总有绝对值更大的负数第二阶段压缩：负数后总有绝对值更大的正数负数后总有绝对值更大的正数得到精华信息：一个个一个个“对对”的相对峰值递增的相对峰值递增为贪心法解题创造了良好的条件IOI2005冬令营演示文稿安徽周源换元法例二球队问题例五合并数列问题强连通分量一个点复杂的联系图有向无环图一段子串一个“单峰”K个任意数列美妙的单调性t2 + 1 + t = 7化归思想无理无理有理有理复杂复杂简单简单抽象抽象形象形象t压缩法化归思想IOI200

10、5冬令营演示文稿安徽周源化归思想压缩法两个要点可压缩性替代法则：存在冗余：除去冗余除去冗余合理利用信息化难为易化繁为简信息化IOI2005冬令营演示文稿安徽周源当题设条件过多、信息量过大，无从下手时当题设条件过多、信息量过大，无从下手时 IOI2005冬令营演示文稿安徽周源 加权有向图中，有多个源点的最短路问题S1S2S3232ABCDE1322(2)(3)(2)(3)(4)12IOI2005冬令营演示文稿安徽周源 舍去包裹内的连边情况舍去包裹内的连边情况，压缩为新的单源S1S2S3232ABCDE1322(2)(3)(2)(3)(4)SDijkstra模型12IOI2005冬令营演示文稿安徽周源 模方程组(红色红色字母均为未知数)a1x c1 (mod b1) 令1=(a1, b1)b1a2x c2 (mod b2) 令2=(a2, b2)b2 联立(1)(2)： x1 + p11 = x2 + p22，解得x0 则x = x0 + k1,2x x0 (mod 1,2)