算法合集之《浅析信息学竞赛中一类及物理有关的问题》.ppt

浅析信息学竞赛中 一类与物理有关的问题 ——杭州学军中学 方戈 序言 看上去简单 贴近实际 实现方法多 易转化，易扩展 想起来困难 无固定形式 特殊情况多 数据规模大 趣味性 序言 这类问题所涉及到的知识： 模拟 枚举 搜索 数学 计算几何 动态规划 数据结构 序言 一般解决路线 简单实际的解决办法 更好的办法1 更好的办法2 更好的办法3 死胡同 算法1 算法2 算法3 算法N [例]water tanks(ACM 2007 Final改编) 有许多高低不同的圆柱型容器由一些高低不同的横向的管道连接 最多能倒多少体积的水 气压变化法则P1V1=P2V2 同一水平面水压处处相等 规模：容器数N1000000 对样例的解释 1 2 3 高度H1 高度H2 初步分析 第一感觉：简单 题目中元素单一 对水压气压的理解很具体 类似于实验室中的一些容器 日常生活中的经验 普通模拟方法 严格按照规律往容器中倒水 初步分析 事件点无限，如何解决？ 方案1：每次倒一点点水 精度问题 次数惊人，每次的模拟至少要O(N) 显然无法承受 方案2：把某容器水位到达左或右管子当作一个事件点 次数依然有O(N)，模拟也要O(N) 依然无法承受 初步分析 初步分析 抓住问题特征 只要求倒的水量 最终第一个容器的水柱高度是固定的 最终水压只由该容器水柱高度决定 分别考虑各个容器 遇到的问题 若容器中的空气与其他容器连通 此容器气压受其他容器影响，无法单独考虑 称容器的连通为空气的连通 初步分析 称与左右两边都不连通的容器为独立的 利用独立容器水压与气压的平衡 直接算出独立容器最终的水位 只需考虑容器独立前水位是如何变化的 1 6 2 3 4 5 一类特殊情况 不妨先研究一类简单的情况 大胆提出限制：管子的高度递增 这种情况下容器间更容易封住 一类特殊情况 一类特殊情况 从左到右对每个容器进行处理 总复杂度O(N) 特殊情况解决 从特殊到一般 大胆进行类比，引入块的概念 一个块是一段连续的容器 这段容器间的管子高度递减 从特殊到一般 这样定义块的原因 块内水位上升规律明显 块与块之间容易密封 一般情况的解决 块水位变化的规律 与右边的块密封前的规律 一般情况的解决 块水位变化的规律 与右边的块密封后的规律 一般情况的解决 从左到右依次对块进行处理 复杂度分析 每个块的处理复杂度为O(块的大小） 总复杂度即为O(所有块的大小之和)即为O(N) 原问题完美解决 拓展 若不只第一个容器是有开口的会怎样？ 总结 此题的解决路线： 模拟走不通时，抓住问题特点另辟蹊径 大胆提出限制条件解决特殊情况 利用类比解决一般情况 最终的算法——复杂，难以想到 三步之间的衔接——自然，简洁 总结 回顾例题并参考其它这类的问题 这类问题对我们的要求与培养： 有创造力，勤于实践 理性与感性相结合 思维的多样性和严谨性 灵活应对问题，看清本质 深入研究，举一反三 耐心，永不放弃的品质