淺析信息學競賽中一類與物理有關的問題

1、淺析信息學競賽中 一類與物理有關的問題,——杭州學軍中學 方戈,序言,看上去簡單貼近實際實現(xiàn)方法多易轉化，易擴展,想起來困難無固定形式特殊情況多數(shù)據(jù)規(guī)模大,趣味性,序言,這類問題所涉及到的知識：模擬 枚舉搜索數(shù)學計算幾何動態(tài)規(guī)劃數(shù)據(jù)結構,綜合素質,序言,一般解決路線,簡單實際的解決辦法,,,,抓特點 找規(guī)律,更好的辦法1,更好的辦法2,更好的辦法3,,死胡同,,,,,,,算法1,算法2,算法3,,算法

2、N,[例]water tanks(ACM 2007 Final改編),有許多高低不同的圓柱型容器由一些高低不同的橫向的管道連接最多能倒多少體積的水氣壓變化法則P1V1=P2V2同一水平面水壓處處相等規(guī)模：容器數(shù)N<1000000,,,對樣例的解釋,1,2,3,,高度H1,高度H2,,初步分析,第一感覺：簡單題目中元素單一對水壓氣壓的理解很具體類似于實驗室中的一些容器日常生活中的經(jīng)驗普通模擬方法嚴格按照規(guī)律往容器

3、中倒水,初步分析,事件點無限，如何解決？方案1：每次倒一點點水精度問題次數(shù)驚人，每次的模擬至少要O(N)顯然無法承受方案2：把某容器水位到達左或右管子當作一個事件點次數(shù)依然有O(N)，模擬也要O(N)依然無法承受,初步分析,數(shù)據(jù)規(guī)模實在是太大了！,模擬碰到死胡同,怎么辦？,從頭想起 另找出路,固定框架沒法套,初步分析,抓住問題特征只要求倒的水量最終第一個容器的水柱高度是固定的最終水壓只由該容器水柱高度決定分別考慮

4、各個容器遇到的問題若容器中的空氣與其他容器連通此容器氣壓受其他容器影響，無法單獨考慮稱容器的連通為空氣的連通,,初步分析,稱與左右兩邊都不連通的容器為獨立的利用獨立容器水壓與氣壓的平衡直接算出獨立容器最終的水位只需考慮容器獨立前水位是如何變化的,1,6,2,3,4,5,一類特殊情況,不妨先研究一類簡單的情況大膽提出限制：管子的高度遞增這種情況下容器間更容易封住,一類特殊情況,一類特殊情況,從左到右對每個容器進行處理總

5、復雜度O(N)特殊情況解決,如何推到一般的情況呢？,從特殊到一般,大膽進行類比，引入塊的概念一個塊是一段連續(xù)的容器 這段容器間的管子高度遞減,,從特殊到一般,這樣定義塊的原因塊內(nèi)水位上升規(guī)律明顯塊與塊之間容易密封,一般情況的解決,塊水位變化的規(guī)律與右邊的塊密封前的規(guī)律,,一般情況的解決,塊水位變化的規(guī)律與右邊的塊密封后的規(guī)律,一般情況的解決,從左到右依次對塊進行處理復雜度分析每個塊的處理復雜度為O(塊的大小）總復雜度

6、即為O(所有塊的大小之和)即為O(N)原問題完美解決拓展若不只第一個容器是有開口的會怎樣？,總結,此題的解決路線：模擬走不通時，抓住問題特點另辟蹊徑大膽提出限制條件解決特殊情況利用類比解決一般情況,最終的算法——復雜，難以想到,三步之間的銜接——自然，簡潔,總結,回顧例題并參考其它這類的問題這類問題對我們的要求與培養(yǎng)：有創(chuàng)造力，勤于實踐理性與感性相結合思維的多樣性和嚴謹性靈活應對問題，看清本質深入研究，舉一反三