国家集训队2008论文集浅析信息学竞赛中一类

《国家集训队2008论文集浅析信息学竞赛中一类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅析信息学竞赛中一类与物理有关的问题——杭州学军中学方戈序言看上去简单贴近实际实现方法多易转化，易扩展想起来困难无固定形式特殊情况多数据规模大趣味性序言这类问题所涉及到的知识：模拟枚举搜索数学计算几何动态规划数据结构综合素质序言一般解决路线简单实际的解决办法抓特点找规律更好的办法1更好的办法2更好的办法3死胡同算法1算法2算法3算法N[例]watertanks(ACM2007Final改编)有许多高低不同的圆柱型容器由一些高低不同的横向的管道连接最多能倒多少体积的水气压变化法则P1V1=P2V

2、2同一水平面水压处处相等规模：容器数N<1000000对样例的解释123高度H1高度H2初步分析第一感觉：简单题目中元素单一对水压气压的理解很具体类似于实验室中的一些容器日常生活中的经验普通模拟方法严格按照规律往容器中倒水初步分析事件点无限，如何解决？方案1：每次倒一点点水精度问题次数惊人，每次的模拟至少要O(N)显然无法承受方案2：把某容器水位到达左或右管子当作一个事件点次数依然有O(N)，模拟也要O(N)依然无法承受初步分析数据规模实在是太大了！模拟碰到死胡同怎么办？从头想起另找出路固定框架

3、没法套初步分析抓住问题特征只要求倒的水量最终第一个容器的水柱高度是固定的最终水压只由该容器水柱高度决定分别考虑各个容器遇到的问题若容器中的空气与其他容器连通此容器气压受其他容器影响，无法单独考虑称容器的连通为空气的连通初步分析称与左右两边都不连通的容器为独立的利用独立容器水压与气压的平衡直接算出独立容器最终的水位只需考虑容器独立前水位是如何变化的162345一类特殊情况不妨先研究一类简单的情况大胆提出限制：管子的高度递增这种情况下容器间更容易封住一类特殊情况一类特殊情况从左到右对每个容器进行处理

4、总复杂度O(N)特殊情况解决如何推到一般的情况呢？从特殊到一般大胆进行类比，引入块的概念一个块是一段连续的容器这段容器间的管子高度递减从特殊到一般这样定义块的原因块内水位上升规律明显块与块之间容易密封一般情况的解决块水位变化的规律与右边的块密封前的规律一般情况的解决块水位变化的规律与右边的块密封后的规律一般情况的解决从左到右依次对块进行处理复杂度分析每个块的处理复杂度为O(块的大小）总复杂度即为O(所有块的大小之和)即为O(N)原问题完美解决拓展若不只第一个容器是有开口的会怎样？总结此题的解决路

5、线：模拟走不通时，抓住问题特点另辟蹊径大胆提出限制条件解决特殊情况利用类比解决一般情况最终的算法——复杂，难以想到三步之间的衔接——自然，简洁总结回顾例题并参考其它这类的问题这类问题对我们的要求与培养：有创造力，勤于实践理性与感性相结合思维的多样性和严谨性灵活应对问题，看清本质深入研究，举一反三耐心，永不放弃的品质谢谢大家