淺析信息學(xué)競(jìng)賽中一類(lèi)與物理有關(guān)的問(wèn)題

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

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

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

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

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

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