淺析信息學(xué)競賽中一類與物理有關(guān)的問題

1、淺析信息學(xué)競賽中 一類與物理有關(guān)的問題,——杭州學(xué)軍中學(xué) 方戈,序言,看上去簡單貼近實(shí)際實(shí)現(xiàn)方法多易轉(zhuǎn)化，易擴(kuò)展,想起來困難無固定形式特殊情況多數(shù)據(jù)規(guī)模大,趣味性,序言,這類問題所涉及到的知識：模擬 枚舉搜索數(shù)學(xué)計(jì)算幾何動態(tài)規(guī)劃數(shù)據(jù)結(jié)構(gòu),綜合素質(zhì),序言,一般解決路線,簡單實(shí)際的解決辦法,,,,抓特點(diǎn) 找規(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,,初步分析,第一感覺：簡單題目中元素單一對水壓氣壓的理解很具體類似于實(shí)驗(yàn)室中的一些容器日常生活中的經(jīng)驗(yàn)普通模擬方法嚴(yán)格按照規(guī)律往容器

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

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

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

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