【文章內(nèi)容簡介】 間的體積改變時，氣壓改變滿足以下規(guī)律 P1V1=P2V2,其中 P1， V1為壓縮前的氣壓和體積， P2， V2為壓縮后的。 一單位高度的水柱產(chǎn)生的壓力為 KP=。 相連的水在同一個高度的水壓是相等的。 現(xiàn)問：第一個管子注滿水時，共倒了多少單位體積的水？ 上圖為一個只有兩個管子的例子， N≤1000000。 3 初步分析 這題看上去感覺并不復(fù)雜，對于原來的規(guī)模，只要按照那些性質(zhì)直接模擬即 3 此題與原題有些區(qū)別，條件限制和數(shù)據(jù)規(guī)模上都有所加強，原題有個限制是橫管的高度是從左到右遞增的，并且數(shù)據(jù)規(guī)模只有 10，詳見附錄中的英文原題。 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 可。我們的感性認識告訴我們，對于每個管子，只需要在氣壓和水壓上建立一個平衡，就可以了，但事實上，對這題的感性認識騙了我們自己，即使是模擬，由于很多量在變化，每個容器的氣壓涉及到很多因素，其間需要很多的討論和判斷。比如說下面的這種的情況。 當?shù)诙€容器中的水低于第三個容器時，第二個容器的剩余空氣與第三個容器中的空氣是連通的，所以當?shù)?二個容器的水升高的時候，第二個容器和第三個容器的氣壓是共同升高的，而當我們繼續(xù)倒水變成右上圖所示情況的時候：兩個容器的空氣就隔絕了，此時兩個容器的氣壓就需要分別處理。而顯然，當容器數(shù)增多的時候，情況就遠不止這樣了。本題的難點就在于如何處理這些情況。 一些簡單的性質(zhì) 本題情況多樣，對于本題，一種經(jīng)典而又樸素的方案便是繁瑣的討論了，但是剛切入題目便討論，必然會對很多特殊情況漏判或者誤判，很難做到嚴謹，而這正是這類題目所最為需要的。我們需要的另一種簡潔明了的方案，而得到方案的路必然是盤旋上升的，想一步登天是不可行 的，即使是討論，也需要對本題的一些性質(zhì)和規(guī)律有深入的了解，所以首先看一些簡單的結(jié)論。 設(shè)第 i 個容器中水面高度為 H[i]，那么有： 性質(zhì)一： H[i] pipe_H[i]時， H[i + 1] = 0,其中 i ≠N。 性質(zhì)二： H[i + 1] pipe_H[i]時，左右連通。否則，左右不連通。 性質(zhì)三：第 i 個容器若和左右都不連通時，它上方空氣的體積和氣壓的乘積就確定下來了，此時 H[i]僅和最高水柱高度即 H[1]有關(guān)，可單獨考慮。 以上兩條性質(zhì)均可直接獲得，雖然他們看似廢話，但他們是我們繼續(xù)探索的基 礎(chǔ)。由它們可以繼續(xù)得到以下的結(jié)論： 性質(zhì)三： 0 H[i + 1] pipe_H[i]時， H[i] = pipe_H[i]。 證明： 如果 H[i] pipe_H[i]，與性質(zhì)一矛盾。 如果 H[i] pipe_H[i]，水會往右邊流，直到左邊水面高度等于橫管高度或者右邊水波面高度不小于橫管高度。 證畢。 這些簡單的信息事實上就高度概括了水流的規(guī)律，而只有通過這些規(guī)律才能題目開刀。 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 對一類特殊情況的分析 僅僅知道水怎么流是不夠的，我們還是很難直接提出算法，我們不妨先來看一個特殊的情況，再想辦 法從特殊推到一般。 把從原題刪去的限制條件加回去，也就是多了這么個限制：橫管的高度是從左到右遞增的。 這個限制條件的添加事實上給我們的解題提供了很大的便利，從感性認識上講，就會覺得少了很多情況，事實也正是如此，容器中水的上升情況的規(guī)律很容易就能發(fā)現(xiàn)： 假設(shè)第 1 個容器無限大，那么在往第 1 個容器中倒水的過程中：首先 H[2]到達 pipe_H[2]后， H[3]開始上升，上升到 pipe_H[2]后，容器 2， 3 隔絕，容器 2中的空氣達到密封， H[2]可單獨考慮，然后 H[3]繼續(xù)上升，上升到 pipe_H[3]后，H[4]開始上升，上升到 pipe_H[3]后，容器 3， 4，隔絕， H[3]可單獨考慮??直到最后一個管子 H[N] = pipe_H[N – 1]。 觀察整個過程，其中的關(guān)鍵點是相鄰的兩個容器的隔絕，因為它導(dǎo)致了兩部2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 分氣壓變化的分化，鑒于此，我們稱 H[i]＝ pipe_H[i – 1]時到 H[i + 1] ＝ pipe_H[i – 1]時的變化為第 i 階段的變化，又因為沒有 H[0]，不妨就令第一階段的變化為一開始到 H[1] = H[2] = pipe_H[1]的變化。上圖是某個變化階段的例子，其中第三階段的第二步 還未完成時，第一個容器已經(jīng)滿了，因此第三階段結(jié)束 對一類特殊情況的算法 然后，一個簡明算法就能設(shè)計出來了，其中 i 表示目前的階段數(shù)， V 表示目前第 i 個容器右邊（不包括第 i 個）的空氣的體積， P 表示其氣壓，其中的 col_H[1]即為最終的水柱高度，用來計算壓強。 step 1：初始化 H[1] = H[2] = pipe_H[1]， i = 1， V 賦為總體積 col_H[1]H[2]，P = 1。 step 2： i ++，若 i = N，計算 H[i]最終高度，跳入 step5。若 H[i]在從 pipe_H[i – 1]上升到 pipe_H[i]的過程中能達到最終水壓和氣壓的平衡，即存在 delH 使得0≤delHpipe_H[i] – pipe_H[i – 1]，并且 (col_H[1]H[i] – delH)*KP + 1 = V * P / (V – delH)。那么 H[i] += delH，跳入 step5，否則 H[i] = pipe_H[i]，更新 V， P。 step 3：如果 H[i + 1]在從 0 上升到 pipe_H[i]的過程中能達到最終水壓和氣壓的平衡，即存在 delH 使得 0≤delHpipe_H[i]，并且 (col_H[1] – pipe_H[i]) * KP + 1 = V * P / (V – delH)。那么 H[i + 1] = delH，跳入 step5，否則 H[i + 1] = pipe_H，更新 V， P。 step 4：計算 H[i]的最終高度，跳回 step2。 step 5：統(tǒng)計答案并輸出。 其中要注意解一元二次方程的時候用最小的非負解。 算法中 step2~step4 就是對階段的循環(huán)處理，他們的復(fù)雜度均為 O(1)，最多 N個階段，復(fù)雜度為 O(N)，而 step1， step5 的復(fù)雜度也為 O(N)，因此總的 算法時間復(fù)雜度為 O(N)，空間復(fù)雜度也為 O(N)，至此這一類特殊情況已解決。 4 從特殊到一般 回到一般的情況，我們已經(jīng)知道特殊情況的解決方案，要解決一般的情況，一種方案就是把一般的情況通過某種方式歸為特殊的情況。就是說，要從無序的pipe_H 中造出一個“遞增”來。 事實上，這個轉(zhuǎn)化的方式并不難想到。這里引入一個塊的定義： 一個 塊 是一段連續(xù)的容器 i~j，滿足以下性質(zhì)： 1： pipe_H[i] pipe_H[i + 1] pipe_H[i + 1] ?? pipe_H[j]。 (不妨設(shè)pipe_H[N] = 0) 2： pipe_H[i] pipe_H[i – 1]或 i = 1。 3： pipe_H[j] pipe_H[j + 1]或 j = N。 對于一般的情況，一個塊就相當于特殊情況中的一個容器，而特殊情況相對于一般情況，就是每個容器都是一個塊。下圖是某個一般情況的塊（用虛線框出的部分）： 4 程序請參見附錄中 。 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 在一般情況的塊中，也沒有特別顯著的遞增，但是它滿足任兩個塊連接處的pipe_H 是遞增的 —— 如上圖中 23， 67， 78，這個的意義在于當前這個塊后面的一個容器的 H 到達一定高度時，兩個塊的空氣 就隔絕了 —— 如當?shù)谌齻€容器中的水上漲到 2 的高度時，第一個塊和第二個快就隔絕了。而我們構(gòu)造特殊情況所要達到的目的即在于此，因此可以說我們構(gòu)造出了一個“潛遞增”。 一般情況的解決 一般情況的解決就在于一個塊和特殊情況中一個容器的對應(yīng)，相對于特殊情況中的階段，我們不妨先把一般情況階段劃分出來： 設(shè)第 i 個塊的起始容器為 pos[i]，那么 H[pos[i]] = pipe_H[pos[i] – 1]為第 i 個階段的起點（對于第 1 個階段，起點為 H[1] = 0）， H[pos[i + 1]] = pipe_H[pos[i + 1] – 1]為這個階段的終點，也就是下個階段的起點。 套用特殊情況的算法框架后，我們只要把某個階段的算法從對一個容器的處理改成一個塊的處理，也就是要找出一個塊中的水面變化規(guī)律，由于一個塊中的容器之間的 pipe_H 滿足遞減，這個規(guī)律并不難找到，設(shè)這個塊從第 i 個容器到第 j 個容器，那么有： 1： H[i]從 pipe_H[i – 1]上升到 pipe_H[i]。 2： H[i + 1]從 0 上升到 pipe_H[i + 1]。 ?? k： H[i + k – 1]從 0 上升到 pipe_H[i + k – 1]。 ?? j – i + 1： H[j]從 0 上升到 pipe_H[j]。 j – i + 2： H[j + 1]從 0 上升到 pipe_H[j]，導(dǎo)致這個塊與下一個塊的空氣分隔。 以上只是水壓無限上漲的情況，事實上如果任意一步使得水壓和氣壓達到了平衡，都可以直接跳出。 這里的操作就相當于特殊情況中的 step2 和 step3 了，如果沒有跳出，順利與下個塊隔絕時，就要對這個塊進行密封后的處理，相當于特殊情況中的 step4，2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 這個的處理就沒有特殊情況中那么簡單了，因為塊中的空氣還會隨著水面的上漲而隔絕： 1： H[j]從 pipe_H[j]上升到 pipe_H[j – 1]，如果其間達到平衡，跳出，否則會造成 j 容器中的空氣與塊中剩余其它空氣的隔絕，此時可直接算出 H[j]最終的高度，然后把氣壓和剩余空氣體積更新。 2：同樣的方法對 H[j – 1]從 pipe_H[j – 1]上升到 pipe_H[j – 2]進行處理。 ?? k：對 H[j – k + 1]從 pipe_H[j – k + 1]上升到 pipe_H[j – k]進行處理。 ?? j – i：對 H[i + 1]從 pipe_H[i + 1]上升到 pipe_H[i]進行處理。 j – i + 1：此時 i 容器中的空氣已隔絕，直接可以求出答案。 這樣，相對于特殊情況算法中的 step4 也順利地解決了。 對某個塊的 step2~step4 操作可以從下圖中更加直觀的看出來： 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 其中要說明的是，上圖是某個局部，默認水壓無限增大，上