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

压去冗余 缩得精华 ——浅谈信息学竞赛中的“压缩法” 引子 压缩软件？ 本义：加以压力,以减小体积、大小、持续时间、密度和浓度等 压缩法 除去冗余信息，留下精华，以减小问题的规模 压缩法的定义 将集合S作为内外隔绝的包裹打包压缩 略去了包裹内部的冗余信息，从而简化问题 [例二]球队问题(经典问题) 篮球队的球员通讯图，(B, A)表示B能通知A 教练需要通知所有人一条消息 最少需要 告诉几个人？ 本例中最少为2人 如A, F等等 [例二]球队问题(经典问题) 使用压缩法，“压去”不必要的信息 求出强连通分量 S1, S2, S3… “压缩” 每个分量?新点 保留分量间连边情况 [例二]球队问题(经典问题) 压缩转化后的新图 简洁：没有环的存在 无入度的点： 必须亲自通知 有入度的点： 必定可以由队员通知 结论：答案为 压缩后图中无入度点的数目 压缩法的要点 1.可压缩性 集合S内部各个元素之间的联系不会和外部元素相互作用而影响到问题的结果即可压缩 [例二]中： 强连通分量内球员的通讯情况不会影响 球员是否得知消息状态的恒等性 舍去分量内球员的通讯情况，压缩为新的节点 压缩法的要点 压：可以压去存在的冗余信息 (可压缩性) 缩：保留S作为一个点与外部信息的联系 　 (替代法则) 2.替代法则 用什么样的形式 表现出精华部分的内容 [例二]中 用一个点替代一个集合 用相同形式的有向边代替原来集合的内外联系 压缩法的应用 压缩法在很多竞赛试题中有巧妙的应用 [例四]欧元兑换(BOI 2003 euro) [例五]合并数列问题(ZOJ p1794) [例五]合并数列问题(ZOJ p1794改编) 有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 [例五]合并数列问题(ZOJ p1794改编) 如K=3时 初步分析 普通动态规划算法 时间复杂度O(K*NK) 显然无法承受 观察压缩要点 1.可压缩性 观察：最优串中的一些子串就是原串的子串 反之：若原串的子串满足性质P即为S的子串 该子串可压缩，P就是可压缩性 观察压缩要点 2.替代法则 若存在一段可压缩的子串u 替代法则保存u内元素与外部因素间的联系 a)u的最大部分和(即相对峰值)可能是S的最大部分和 b)u的总和对以后的部分和产生影响 寻找可压缩性：第一阶段压缩 [定理5.1] 某子串c1, c2, …, cp可压缩当 总和非正 其余部分和为正数 寻找可压缩性：第一阶段压缩 寻找可压缩性：第二阶段压缩 [定理5.2]和[推论5.2.1] 若在一个数列中 存在连续多个“对” 当峰值在第一“对”，则可压缩 证明依然使用调整法 压缩转化后 每一“对”在数列中的相对峰值递增 最后的贪心 贪心算法 由于每一“对”的总和为负 相对峰值大的尽量向后放 将每一“对”按相对峰值归并排序即可 时间复杂度：O(Nlog2K) [例五]合并数列问题(ZOJ p1794改编) 小结 第一阶段压缩：正数后总有绝对值更大的负数 第二阶段压缩：负数后总有绝对值更大的正数 得到精华信息：一个个“对”的相对峰值递增 为贪心法解题创造了良好的条件 总结 总结 [例一]多源最短路问题(经典问题) 加权有向图中，有多个源点的最短路问题 [例一]多源最短路问题(经典问题) 舍去包裹内的连边情况，压缩为新的单源 [例三]模方程组的替代法则(经典问题) 模方程组(红色字母均为未知数) a1x ≡ c1 (mod b1) 令Δ1=(a1, b1)b1 a2x ≡ c2 (mod b2) 令Δ2=(a2, b2)b2 联立(1)(2)： x1 + p1Δ1 = x2 + p2Δ2，解得x0 则x = x0 + k[Δ1,Δ2] x ≡ x0 (mod [Δ1,Δ2]) a1x + k1b1 = c1 x = x1 + p1Δ1 (1) a2x + k2b2 = c2 x = x2 + p2Δ2 (2) 寻找可压缩性：第一阶段压缩 [定理5.1] 某子串c1, c2, …, cp可压缩当 总和非正 其余部分和为正数 * IOI2005冬令营演示文稿 安徽　周源 * IOI2005冬令营演示文稿 安徽　周源 安徽 周源 压缩法？？ S A B C D E F G 亲自 A B C D E F G S1 S3 S2 S1 S3 S2 [例五]合并数列问题(ZOJ p