【正文】 。 感謝為我寫此論文提供莫大幫助，提供資料，糾正錯誤的劉汝佳2022 年信息學奧領匹克競賽冬令營論文 浙江 方戈 教練。 證畢。如果兩個操作不能使該盆地飽和，那么交換是可以的，無論先后關卡的水都往此盆地流一部分，而此盆地的水流不出去。 Case 2：兩個操作均在 k+1 的關卡上或均在 k+1 的盆地上，那么這兩個操作可合并，顯然互換也是可以的。 2：若對于兩個操作所在盆地或關卡高度均 ≤k(k≥0)時成立，那么，要證明對≤k+1 時也均成立，只要證明下面幾種情況。 證明： 這兒引入第二步操作 中盆地和關卡的概念來對其進行證明。 這類問題是非常迎合當今的問題發(fā)展趨勢的，相信以后會有更多更好的有物理特色的問題會出現(xiàn)，而當我們面對這類問題時，只要發(fā)揮豐富的想象力，保持冷靜的頭腦，不中途而廢，相信問題最終一定會迎刃而解，而我們從中也一定能獲得一些意想不到的收獲?？梢钥吹阶罱K它們的算法都是條理清晰，而實現(xiàn)它們也并不困難。這又一次證明了對于這樣的一類問題，只要肯抓住其特點一步一步好 好地分析，最終一定能得到勝利。 7 小結 這題數(shù)據(jù)規(guī)模巨大，一開始提出的模擬的想法總讓人感覺是不可能有希望的，然而，在這樣的情況下，我們大膽地提出猜想對其進行第一次優(yōu)化，又仔細分析后提出壓縮的思想而對其進行了第兩次的優(yōu)化，每次優(yōu)化都使算法變優(yōu)很多，使時間復雜度從一開始的不可能到最終的很優(yōu)。 step 3 也是 O(1)的，因此總復雜度為 O(N*M) + O(N*M) + O(1)＝ O(N*M)。 step 1，求盆地和關卡中每個點最多 bfs 到一次，而每個點最多往外延伸 4 個點，因此 bfs的總復雜度為 O(N*M)，除 bfs 外的操作均是 O(1)的，最多有 O(N*M)個操作，2022 年信息學奧領匹克競賽冬令營論文 浙江 方戈 因此這步的總復雜度為 O(N*M)。 證畢。 否則， i 的最終水位必然為 i，因為它不能貯存水，它與一個最種水位比它的高度低的方格相連，倒在它上面的水一定為往下流。 假如對于高度 i 的操作，滿足操作前剩余格最終水位均 ≥i，那么： 如果 i 不在邊界上也不與某個已訪問的點相連，那么 i 所在的未訪問連通塊的邊界上的方格高度必然都 i，那么這個連同塊的最小水位即為最低邊界格 i，因此 i 的最終水位不為 i， i 不是關卡， 顯然也就不存在海拔為 i 的盆地。用歸納法來對此進行證明。 2：對每個 i 相鄰的格子，如果未訪問，并且高度 i，那么就以它為七點 bfs，bfs 時也是相同的限制條件， bfs 出的點即為一個盆地，把它們?nèi)?部標記了，并順便計算它的容量。下面來看得到盆地的算法： 從高度從小到大的順序判斷相應高度的格子是否是關卡并求出盆地，在操作時把已經(jīng)確定的點標記為 visited。 step 3：輸出答案。 2：把所有過度飽和的相應海拔盆地的過度水量反倒在關卡 i 上。 step 2：對所有關卡從大到小進行處理： 對關卡 i 的處理如下： 1：把關卡中的水往下倒，倒的水按相應方格各種情況計入不飽和的相應海拔的盆地的水量、低于其海拔的盆地的水量、低于其海拔的關卡以及答案。根據(jù)最終水位判斷此方格是否是關卡或所 在盆地的編號，并算出所有盆地的容量。 證畢。那么由于關卡的定義，這個方格的最終水位高于原高度，因此與它相鄰的方格的最終水位均大于等于它的最終水位，其中必然有方格的最終水位等于它的最終水位，否則它的最終水位應該更高，如果此方格屬于盆地，那么與盆地性質(zhì)第 3 條矛盾，否則繼續(xù)把它加入連通塊，繼續(xù)找與此連通塊連通且最終水位相等的方格，連通塊會無限擴大直到找到一個盆地，而地圖是有限大的，因此矛盾。 任何一個方格，要么在某個盆地中，要么是一個關卡。假設不成立。 這也保證了從任何關卡可以往下倒水。 這個 性質(zhì)可直接從定義中獲得。稱這兩者的差為此盆地的 過度水量。 稱一個盆地 飽和 ，如果 它的總水量等于它的容量 。 一個海拔盆地為 i 的盆地的 容量 ，即為 其方 格個數(shù) *i－其方格原高度和 ，它表示該盆地中最多能倒入多少水而不溢出。 2：所有方格的最終水位等于 i，而原來的高度 i。 為了后面對算法的描述的方便及準確，不妨先對盆地及一些其他概念作更為精確的定義： 方格 i 的最終水位 H[i]，表示在所有方格上倒無限大的水后，方格 i 的水位。比如還是這個例子中， 1， 2， 3， 4 就像一個盆地，這個盆地中的水最多升到 7，再上升就會從 7往外漏了，因此盆地的容量為 18，所以我們不妨把倒在 1， 2， 3， 4 上的水一起算，算出一個落在此盆地的水的總水量 tot，若 tot18，那么浪費的水量就為 tot18，可見這里用到一個壓縮的思想，我們把 一個盆地中的具體水位變化當作冗余的信息壓縮了，只保留此盆地溢出的水量。看來我們還是應該再繼續(xù)分析下去，另辟蹊徑來解決 Case 2 的麻煩。 然而， Case 2 的計算會大大增加計算的復雜度，每次 水面的升高將要一次新的 bfs，一種優(yōu)化辦法是對于連續(xù)的水面升高，維護當前的水面邊界，再加上一些數(shù)據(jù)結構如堆來優(yōu)化取最小值的時間，但是即使這樣，每次做 Case 2 理論上需要的復雜度還是 O(N*M)，并且它還會使 i 增加，這就連 Case1 的總復雜度O(N*M)都無法保證了。 7 發(fā)現(xiàn)有相鄰格比它低，于是進行 case1把 4單位水倒在邊界外。 邊界為 7 ， 6 (74)*4， 4 全變成。 2 無法進行 case1 操作，進行 case2:bfs得湖面為兩格，最低邊界為 3， 2 的水位升到 3， 2 指向3， 3 上倒 9 單位水，i=3。 其中 Case 2 即為對第二中情況的模擬，直接講對數(shù)據(jù)的處理辦法可能比較難以理解，這里不妨來局部模擬一下幫助理解。然后 i 賦值為 j，并把剩余水量 V(ji)*area 倒在方格 j 上。 i Case 2，方格 i 不存在比它低的鄰格： bfs 得到水位與方格 i 相同的區(qū)域（當然包括這個方格自己），形象地講，這相當于一個湖的湖面，按照我們的操作，能保證湖面四周的邊界方塊均高于 i，我們求出區(qū)域面積 area，在邊界方塊中，選一個最低的方格 j—— 那么使湖面上升到 j 所需要的水量為 (ji)*area，如果當前往方格 i 上倒的總水量為 V，那么若 V (ji)*area，就把整個水面區(qū)域的水位都提升 V/area 單位， i，本次操作結束。 i 表示目前在對方格 i 進行操作，初始 i=N*M，不斷進行操作直到 i = 0 結束，跳入 step3。如果對第二種情況直接模擬的話，我們就能提出一個像樣的算法了： step 1：對所有操作在每個方格上的總倒水量進行統(tǒng)計。 事實上，一個簡單而有效的排序方法就是把操作按照所倒的方塊的高度從大到小排序，因為水不能從低處到高處，如果忽略第二種情況造成的影響，我們的每次對當前方塊進行操作后均不用再次操作了，因為后面的方塊均比當方 塊小。 第一種算法 光光能對操作匯總，延遲還是不夠的，我們還是無法保證解決第一種情況全部復雜度，比如，有兩 個方塊一個低，一個高并且相鄰，那么我們?nèi)粝忍幚砹说偷?，再處理高的，那么高的中的水會又流到低的上使得我們不得不再次去處理低的，如果后來又在一個更高的方塊上，那么我們不得不對這兩個方塊都再處理一遍，那對于總方塊數(shù)高達 106的數(shù)據(jù)就無法勝任了。比如說，有兩個操作都是往方塊 6 上倒水，那么這兩個操作就能合并成一個；又如，方塊 5 和方塊 4 都與方塊 3 相鄰，有兩個操作一個往方塊 5 上倒水，一個往方塊 4 上倒水，兩次倒水都會倒到方塊 3 上一部分，但我們倒了一部分以后，不需要立刻模擬這部分在方塊 3 的下一步會怎樣，我們可以在下一部分也倒下來以后一起處理，甚至可以加到原本往方塊 3 上倒水的操作中。 這個結論對于本題的優(yōu)化意義在于：我們能對操作進行 匯總處理 及 延遲處 6 關于此結論的證明，請參照附錄。 6 由這個結論，還能夠推出下面這個非常重要的推論： 對所有操作的任何順序的操作都對結果沒有影響。 想像一下這題操作時的圖景，我們不難提出這樣的一個問題：任意的兩個操作，交換其順序，對情況是否有影響呢？再用感性的認識想想如何會有反例吧，比如方塊 1，方塊 2（不妨稱原始高度為 i 的方塊為方塊 i，下同）相鄰，第一個操作把方塊 1 水位提到了 2，第二個操作在方塊 2 上倒水，如果先進行第一個操作再進行第二個 ，那么第二個操作的水不會落到方塊 1 上，但如果先進行第二個操作，第二個操作的水就會落到方塊 1 上，但再做下去呢？再給方塊 1 的倒的水就會滿出來，多余的水從高度為 2 的方快上流出去，最終兩種操作方式對水位的影響是完全一致的。 第一步優(yōu)化 —— 大膽猜測 這題是一道非常實際的題，這有一點好處，就是能讓人對它有很好的感性認識，對第一步優(yōu)化，我們需要利用我們對此題的感性認識，大膽地進行一些 猜測。因為這個遞歸會造成操作 指數(shù)級增長，不要說數(shù)據(jù)中最多有 106個操作，即使只有 1， 2 個，我們也無能為力 —— 想像這樣一種數(shù)據(jù)，地圖的中心是最高點，然后盤旋往下降，就像一座山，如果在山頂澆一點水，那么遞歸層數(shù)實際上就能達到 500 左右，每次即使只增加兩倍，也是天文數(shù)字中的天文數(shù)字了。在操作過程中，維護目前各個位置的水位情況。 數(shù)據(jù)規(guī)模如下： N， M≤1000， T≤1000000， k≤1000000。 5 程序請參見附錄中 2022 年信息學奧領匹克競賽冬令營論文 浙江 方戈 2： bi,j中有水或它的高度沒有比相鄰的單元格水位高： 這種情況下，倒入的 k 單位水會與 bi,j 中原有水及與其相連的水混合導致水位升高直到不能再升高，因為旁邊也許有缺口，限制水位的繼 續(xù)升高，而多余的水會從缺口按照第一種情況往下倒。對于很大一部分問題，特別是這類有“物理”味的問題，這是一個通用而有效的解決問題的辦法。想象如果直接給出改過的題目，大概很多人就會手足無措，沒法切入。 5 小結 通過一步步的分析，我們最后得到了一個簡潔高效的算法，達到了原先難以想像的效率，這中間的過程，一步步的銜接也是自然而簡單，而不是靠運氣。 把這些步驟嵌入到特殊情況的算法框架中，就能得到一個適用于一般情況的算法，具體的算法描述這兒就不再贅述了，相信讀者自己能夠理 出來。 這樣，相對于特殊情況算法中的 step4 也順利地解決了。 ?? j – i：對 H[i + 1]從 pipe_H[i + 1]上升到 pipe_H[i]進行處理。 2：同樣的方法對 H[j – 1]從 pipe_H[j – 1]上升到 pipe_H[j – 2]進行處理。 以上只是水壓無限上漲的情況，事