【正文】 目中巨大的數(shù)據(jù)規(guī)模?？磥砦覀冞€是應(yīng)該再繼續(xù)分析下去，另辟蹊徑來解決 Case 2 的麻煩。 第二步優(yōu)化 —— 壓縮 要優(yōu)化，就要發(fā)現(xiàn)我們作了哪些沒用的工作，哪些 對最終答案無關(guān)的工作，觀察我們上個算法對 Case 2 的模擬，會發(fā)現(xiàn)水位上升的過程和最終方塊 1， 2， 3，4 的水位情況跟答案并無影響，能不能略去對這些的操作而直接獲得答案呢？看2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 上去是不可能的任務(wù)，但只要好好想想，其實還是有辦法的。比如還是這個例子中， 1， 2， 3， 4 就像一個盆地，這個盆地中的水最多升到 7，再上升就會從 7往外漏了，因此盆地的容量為 18，所以我們不妨把倒在 1， 2， 3， 4 上的水一起算，算出一個落在此盆地的水的總水量 tot，若 tot18，那么浪費的水量就為 tot18，可見這里用到一個壓縮的思想，我們把 一個盆地中的具體水位變化當(dāng)作冗余的信息壓縮了，只保留此盆地溢出的水量。而這對本題 Case 2 的優(yōu)化的作用，顯然是非常巨大的。 為了后面對算法的描述的方便及準(zhǔn)確，不妨先對盆地及一些其他概念作更為精確的定義： 方格 i 的最終水位 H[i]，表示在所有方格上倒無限大的水后，方格 i 的水位。 一個海拔為 i 的盆地 ，滿足以下性質(zhì)： 1：它由一些連通的方格組成。 2：所有方格的最終水位等于 i，而原來的高度 i。 3：方格 i 與盆地相鄰，除此之外所有與盆地相鄰的方格的高度 i。 一個海拔盆地為 i 的盆地的 容量 ，即為 其方 格個數(shù) *i－其方格原高度和 ，它表示該盆地中最多能倒入多少水而不溢出。 如果 方格 i 的最終水位為 i，那么稱方格 i 為海拔為 i 的 關(guān)卡 ，因為所有海拔為 i 的盆地均與它相鄰，并且它們溢出的水均要通過它往下流。 稱一個盆地 飽和 ，如果 它的總水量等于它的容量 。 稱一個盆地 過度飽和 ，如果 它的總水量大于它的容量 。稱這兩者的差為此盆地的 過度水量。 根據(jù)定義，不難發(fā)現(xiàn)以下幾個與其有關(guān)的性質(zhì)： 每個盆地都有一個且僅有一個相應(yīng)海拔的關(guān)卡與其相鄰，一個關(guān)卡可能不與任何相應(yīng)海拔的盆地相鄰，也可能與最多 3 個相應(yīng)海拔的盆地相鄰。 這個 性質(zhì)可直接從定義中獲得。 每個關(guān)卡都與至少一個最終水位低于此關(guān)卡海拔的方格相鄰。 這也保證了從任何關(guān)卡可以往下倒水。 證明： 若存在關(guān)卡 i，它不與任何最終水位低于此關(guān)卡海拔的方格相鄰，那么考慮關(guān)卡 i 及所有相應(yīng)海拔的盆地所組成的連通塊，根據(jù)盆地的性質(zhì) 3 及假設(shè)，此連通塊相鄰的所有方格的高度均 i，那么這個連通塊中方格的最終水位不應(yīng)該是 i，而應(yīng)該更大，矛盾。假設(shè)不成立。 證畢。 任何一個方格，要么在某個盆地中，要么是一個關(guān)卡。 證明： 若存在方格既不在盆地中，也不在關(guān)卡中。那么由于關(guān)卡的定義，這個方格的最終水位高于原高度，因此與它相鄰的方格的最終水位均大于等于它的最終水位，其中必然有方格的最終水位等于它的最終水位，否則它的最終水位應(yīng)該更高，如果此方格屬于盆地，那么與盆地性質(zhì)第 3 條矛盾，否則繼續(xù)把它加入連通塊，繼續(xù)找與此連通塊連通且最終水位相等的方格，連通塊會無限擴大直到找到一個盆地，而地圖是有限大的，因此矛盾。假設(shè)不成立。 證畢。 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 第二種算法 好了，有了這些定義和性質(zhì)，我們就能對 Case 2 進行優(yōu)化，提出一個新的算法了： step 1：計算出所有方格的最終水位。根據(jù)最終水位判斷此方格是否是關(guān)卡或所 在盆地的編號，并算出所有盆地的容量。對所有關(guān)卡及盆地的初始總水量進行統(tǒng)計。 step 2：對所有關(guān)卡從大到小進行處理： 對關(guān)卡 i 的處理如下： 1：把關(guān)卡中的水往下倒，倒的水按相應(yīng)方格各種情況計入不飽和的相應(yīng)海拔的盆地的水量、低于其海拔的盆地的水量、低于其海拔的關(guān)卡以及答案。并把關(guān)卡的水量賦為 0。 2：把所有過度飽和的相應(yīng)海拔盆地的過度水量反倒在關(guān)卡 i 上。 3：如果關(guān)卡 i 的水量為 0，跳出，否則跳入 1。 step 3：輸出答案。 其中 step 1 中算最終水位和得到盆地過于籠統(tǒng)，事實上這也不 是一個非常簡單的問題，在實際的操作中，是直接得到盆地的，最終水位其實只是一個為了便于敘述而創(chuàng)造的概念。下面來看得到盆地的算法： 從高度從小到大的順序判斷相應(yīng)高度的格子是否是關(guān)卡并求出盆地，在操作時把已經(jīng)確定的點標(biāo)記為 visited。 假如目前在操作高度 i 的點： 1：首先看 i 是否在邊界上或與某個已訪問的點相連，如果是，那么 i 是關(guān)卡，標(biāo)記 i，否則直接跳出操作 i+1 的。 2：對每個 i 相鄰的格子，如果未訪問，并且高度 i，那么就以它為七點 bfs，bfs 時也是相同的限制條件， bfs 出的點即為一個盆地，把它們?nèi)?部標(biāo)記了，并順便計算它的容量。 下面來證明這個算法的正確性： 證明： 先證明對高度 i 的操作把最終水位為 i 的點全標(biāo)記了出來，也就是說每次操作 i 前，剩余格的最終水位均 ≥i，操作后均 i。用歸納法來對此進行證明。 一開始，剩余格即為所有格，最終水位均 ≥1，滿足條件。 假如對于高度 i 的操作，滿足操作前剩余格最終水位均 ≥i，那么： 如果 i 不在邊界上也不與某個已訪問的點相連，那么 i 所在的未訪問連通塊的邊界上的方格高度必然都 i，那么這個連同塊的最小水位即為最低邊界格 i，因此 i 的最終水位不為 i， i 不是關(guān)卡， 顯然也就不存在海拔為 i 的盆地。此時不標(biāo)記任何點，但是滿足剩余格最終水位均 i。 否則， i 的最終水位必然為 i，因為它不能貯存水，它與一個最種水位比它的高度低的方格相連，倒在它上面的水一定為往下流。而對盆地進行 bfs 也是按照盆地的定義， bfs 后，最終水位為 i 的點全被標(biāo)記了，滿足剩余格的最終水位均 i。 證畢。 現(xiàn)在我們已經(jīng)得到一個具體而又正確的算法，來分析一下復(fù)雜度。 step 1，求盆地和關(guān)卡中每個點最多 bfs 到一次，而每個點最多往外延伸 4 個點，因此 bfs的總復(fù)雜度為 O(N*M)，除 bfs 外的操作均是 O(1)的，最多有 O(N*M)個操作，2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 因此這步的總復(fù)雜度為 O(N*M)。 step 2，對某個關(guān)卡的處理看似會出現(xiàn)死循環(huán)，但事實上可以證明這個循環(huán)的次數(shù)是有限并且很小的，每次循環(huán)，要么跳出，要么多一個飽和的盆地 —— 不跳出意味著有至少一個盆地從過度飽和變?yōu)轱柡停虼搜h(huán)次數(shù)最多為最大盆地個數(shù)＋ 1 次，而一個關(guān)卡最多連接三個盆地，因此循環(huán)次數(shù)最多為 4 次，每次循環(huán)都是 O(1)的，因此對某個高度的操作是 O(1)的，而這個算法能保證操作的高度遞降而不回升，因此操作總數(shù)最多 O(N*M)次，復(fù)雜度為 O(N*M)。 step 3 也是 O(1)的，因此總復(fù)雜度為 O(N*M) + O(N*M) + O(1)＝ O(N*M)?？臻g復(fù)雜度也為 O(N*M)，這表明此算法能夠勝任題目中給出的巨大數(shù)據(jù)。 7 小結(jié) 這題數(shù)據(jù)規(guī)模巨大，一開始提出的模擬的想法總讓人感覺是不可能有希望的，然而，在這樣的情況下，我們大膽地提出猜想對其進行第一次優(yōu)化，又仔細(xì)分析后提出壓縮的思想而對其進行了第兩次的優(yōu)化，每次優(yōu)化都使算法變優(yōu)很多，使時間復(fù)雜度從一開始的不可能到最終的很優(yōu)。而最終算法的實現(xiàn)也變得非常明了簡潔。這又一次證明了對于這樣的一類問題，只要肯抓住其特點一步一步好 好地分析，最終一定能得到勝利。 總結(jié) 回顧文中這類具有物理特色的問題，我們能非常清楚地看到它們具有的一種鮮明的特征：它們都是實際的，這讓我們一開始就對它們有一個程度的感性認(rèn)識；它們中隱藏了許多優(yōu)美的規(guī)律，要發(fā)掘這些規(guī)律，就需要我們利用現(xiàn)有的感性認(rèn)識，經(jīng)過一步一步理性的分析，找出一個個突破點，而最終達(dá)到我們的目的?？梢钥吹阶罱K它們的算法都是條理清晰，而實現(xiàn)它們也并不困難。 對這類問題的分析還需要有嚴(yán)謹(jǐn)?shù)木瘢駥ξ锢淼姆治鲂枰獓?yán)謹(jǐn)?shù)木褚粯?—— 一開始也許會覺得嚴(yán)謹(jǐn)只是使分析復(fù)雜化，但只有通過嚴(yán)謹(jǐn)?shù)姆治觯?才能夠發(fā)現(xiàn)問題深處透出的優(yōu)美，從而更好地理解問題的意義。 這類問題是非常迎合當(dāng)今的問題發(fā)展趨勢的，相信以后會有更多更好的有物理特色的問題會出現(xiàn)，而當(dāng)我們面對這類問題時，只要發(fā)揮豐富的想象力，保持冷靜的頭腦，不中途而廢，相信問題最終一定會迎刃而解，而我們從中也一定能獲得一些意想不到的收獲。 附錄 附錄一：關(guān)于 [例三 ]中的證明 這里僅證明交換兩個操作對最終結(jié)果不會產(chǎn)生影響，而事實上，也可以證明一個更強的結(jié)論 —— 交換兩個操作對所有方格的水位都不會影響，有興趣的讀者 7 程序請參加附錄中 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 可以試著證明。 證明： 這兒引入第二步操作 中盆地和關(guān)卡的概念來對其進行證明。采用歸納法： 1：兩個操作所在盆地或關(guān)卡的高度均＝ 0（可以認(rèn)為它們倒在邊界外）時成立。 2：若對于兩個操作所在盆地或關(guān)卡高度均 ≤k(k≥0)時成立，那么，要證明對≤k+1 時也均成立，只要證明下面幾種情況。 Case 1：其中一個操作所在盆地或關(guān)卡高度 ≤k，另一個＝ k+1，前一個操作無論先做后做，均不會影響后一個操作對盆地水位變化的影響，也不會對方格k+1 往下倒的水量有影響，而方格 k+1 往下倒的水會落在幾個最終水位高度 ≤k的方格上，而根據(jù)假設(shè)，這幾個操作是可以與前一個 操作互換的，因此可以說這兩個操作也是可以互換的。 Case 2：兩個操作均在 k+1 的關(guān)卡上或均在 k+1 的盆地上，那么這兩個操作可合并，顯然互換也是可以的。 Case 3：一個操作在 k+1 的盆地上，一個操作在 k+1 的關(guān)卡上。如果兩個操作不能使該盆地飽和，那么交換是可以的，無論先后關(guān)卡的水都往此盆地流一部分，而此盆地的水流不出去。如果能使該盆地飽和，兩個操作共同的作用無論先后均等價于用總水量讓盆地飽和后往 k+1 的關(guān)卡上倒剩余的水，也是等價的。 證畢。 附錄二：附件 ars longa 英文原題： ars ars longa 的程序： water tanks 的英文原題： water water tanks 的第一個程序： water tanks 的第二個程序： 3D Musical Waterfence 的英文原題： 3D Musical Waterfence 的程序： 附錄三：供測試的網(wǎng)址 感謝 感謝讓我走上 OI 之路，為我啟蒙，帶我比賽的沈曉恬老師。 感謝為我寫此論文提供莫大幫助，提供資料，糾正錯誤的劉汝佳2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 教練。 感謝伴隨我一路走來的，給予我鼓勵的 4 個朋友。