【正文】 而隨便引入幾個物理概念，就又能編出一類完全不同的題目了，可謂是五花八門，千奇百怪。 但經(jīng)觀察又可以發(fā)現(xiàn)，這些題目還是有些共性的，比如，它們的背景一般是三維的，這就需要我們對空間有很好的感覺，至少我們要能想象出題目描述的是怎么樣的情況，這需要我們對題目有很好的感性認(rèn)識。 而然后，這類題目的做法也不是非常好想的，得到算法是一個盤旋上升的過程，而這中間需要很嚴(yán)謹(jǐn)?shù)乃季S，對于每一個結(jié)論，也必須有嚴(yán)密的證明，這就需要我們對題目有很好的 理性認(rèn)識。 因此說，這類問題是需要感性和理性的結(jié)合的。它們考察的是一個人的各方面綜合素質(zhì)，而從另一個角度上，它們的確涉獵了各個方面的算法 —— 計算幾何，數(shù)學(xué)、動態(tài)規(guī)劃、搜索、模擬、枚舉，而考察各方面能力也正是信息學(xué)問題的發(fā)展趨勢，這也是目前此類問題非常重要的原因之一。 同時，由于背景是三維的，這些問題也就更貼近實際，更具有實用價值，而不像很多數(shù)學(xué)題，動態(tài)規(guī)劃題，只是思維的游戲，它們在這個三維的世界上有著更好的用處，而這，就是此類問題非常重要的另一個原因。 這類問題通常是非常有趣的，并且它們的算法實現(xiàn)非常簡單， 程序不怎么長，但他們的算法設(shè)計需要的是一個很長的一個過程，其間更需要的是有條理的分析和很好的耐性，下面就來看一些例題吧。 例一 [Ars Longa](World Final 2022 Problem C) 題目大意 在空間中有一個結(jié)構(gòu)，由 N 個點和一些連接他們的邊組成，給出 N 個點的位置，點質(zhì)量均為 1KG，點的 z 坐標(biāo)是非負(fù)的， z 坐標(biāo)是 0 的點是粘在地上不能移動的，而 z 坐標(biāo)大于 0 的點可以隨意地移動。給出 M 條邊，故略邊的質(zhì)量，邊十分牢固，可以承受無限大的力，忽略邊之間的作用力。每條邊連接兩個點，邊可以繞著點無摩擦地 轉(zhuǎn)動，長度即為連接的兩個點的初始位置之間的距離。邊對點的作用力可以是推，也可以是拉。 題目的保證不會有這樣的退化數(shù)據(jù)，如一個點只收到水平的邊的作用，這會造成一些很難解決的情況。 稱這個結(jié)構(gòu)是 平衡 的，如果 這個結(jié)構(gòu)在重力作用下不會移動 。 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 稱這個結(jié)構(gòu)是 穩(wěn)定 1的，如果這個結(jié)構(gòu)是平衡的，并且無論怎么給結(jié)構(gòu)中的點施加怎么樣的力（可以給多點同時施力，并且力可以不同）也不會使雕塑移動。 現(xiàn)在要確定這個雕塑是否平衡或穩(wěn)定。其中 N≤100， M≤100。 上面是兩個例子，括號中是點的坐標(biāo)，其中左圖是穩(wěn)定的，就像一個三角架，而 右圖是平衡而非穩(wěn)定的，上面三點的重心剛好在地面點的正上方，因此它能保持平衡，但顯然只要推它一下，它就倒了。 初步分析 這是一道非常貼近實際的題，因此我們對它會有許多的感性認(rèn)識。顯然的，這需要用到物理中有關(guān)物體平衡的簡單定理： 保持靜止的物體是平衡的。 平衡物體所受到的合力為 0。 這樣點的物理模型就出現(xiàn)了，然后是邊的，注意到題目中的一句重要的話： 邊可以繞著點無摩擦轉(zhuǎn)動，這個實際上說明了 邊對點的作用力是在邊所在直線上的 。邊是理想化無重力的模型，因此 邊對兩個點的作用力是相等并且相反 的。 那么，整道題的 物理模型就構(gòu)建好了，然而此物理模型中包含著復(fù)雜多樣的情況，我們無法用計算機對此物理模型進行分析和計算，因此我們需要對模型進行一些轉(zhuǎn)化。 物理模型的轉(zhuǎn)化 所受合力為 0，這樣的判斷句給我們的第一感受就是可以轉(zhuǎn)化為等式。事實上，如果把每個邊所承受的力用未知數(shù)表示的話，那么對于某個在空中的點，它的 x， y， z 坐標(biāo)均可以建立一個平衡，這實際上就把平衡物體的物理模型等價轉(zhuǎn)化為了三個等式 —— 數(shù)學(xué)模型。 其中邊的力也就是未知數(shù)的數(shù)值，而邊對兩點的推和拉也就是未知數(shù)的正負(fù)符號。 若空中點數(shù)有 P 個，那么對于每個空中的點都這樣轉(zhuǎn) 化就會出現(xiàn) 3*P 方程，這些方程有 M 個未知數(shù)，這些方程組成一個 M 元一次方程組。至此物理模型就完全轉(zhuǎn)化為了數(shù)學(xué)的模型。具體轉(zhuǎn)化如下： 1 原題中所說的是“穩(wěn)定 (stable)”，但在物理學(xué)中，更嚴(yán)謹(jǐn)?shù)闹v法是“剛性 (rigid)”，下同 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 設(shè)方程組為：???????????????????????????????????????????100100,333,322,311,3,1333,1322,1311,13,2333,2322,2311,23,333,322,311,3,233,222,211,2,133,122,111,1MMPPPPMMPPPPMMPPPPMMMMMMxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxa??????? 其中第 3i－ 2， 3i－ 1， 3i 個方程分別表示第 i 個懸空點的 x， y， z 方向上的平衡。關(guān)于 z 方向平衡的方程式右式為 1（只要是一個相同的非 0 數(shù)即可）。 對于第 i 條邊，假如它連接了第 p 個懸空點和第 q 個懸空點（如果它連接了非懸空點，則忽略相應(yīng)的操作），并且兩點之間的向量為 (x0， y0， z0)，那么 a3p2,i=x0，a3p1,i=y0， a3p,i=z0， a3q2,i= x0， a3q1,i= y0， a3q,i= z0，其余的 a*,i均為 0。這些賦值保證了該邊對兩點的力的方向與桿的方向一致，并且對兩點的力相反，因此 x0，y0， z0都成倍增加或減少也是成立的，若表現(xiàn)在方程上，成倍增加或減少也不會影響方程的有解性。 可以看到，這里方程的個數(shù)是 O(N)的，未知數(shù)的個數(shù)是 O(M)的。 平衡及穩(wěn)定的判定 由于我們的等價轉(zhuǎn)化，結(jié)構(gòu)的平衡實際上與我們得到方程組的有解是等價的，因此，我們只需要解方程，即可判定結(jié)構(gòu)是否平衡。解方程就 可以用高斯消元法來做了。 2 高斯消元消到最后，會出現(xiàn)一些（也有可能沒有）左邊系數(shù)全為 0 的方程，如果這些方程中某一個的右邊是非 0 數(shù)，顯然方程無解，否則，因為我們對解沒有限制，所以一定有解。這實際上就把不平衡的情況判定出來了。 穩(wěn)定的判定看上去比較復(fù)雜，但經(jīng)過分析也會發(fā)現(xiàn)這只是一只紙老虎。 穩(wěn)定的定義，轉(zhuǎn)化到方程上就是對方程右邊的數(shù)稍加調(diào)整，能否還保持有解。我們首先的想法就是模擬，對每個方程給它變一變，看有沒有產(chǎn)生影響。然而模擬的代價是巨大的。每次都要重新地解一次方程來看是否有無解的情況，這會使最終的復(fù)雜 度成倍增加。有沒有不需要再解方程就判定穩(wěn)定的方法呢？如果仔細(xì)琢磨，不難發(fā)現(xiàn)以下規(guī)律： 高斯消元后，若存在左邊系數(shù)全為 0 的方程，則不穩(wěn)定，否則就穩(wěn)定。 證明： 若存在左邊系數(shù)全為 0 的方程，那么若調(diào)大或調(diào)小原來此方程等號右邊的數(shù)值，會造成消元后此方程等號右邊的數(shù)不等于 0，即不平衡，因此也就不穩(wěn)定。 若不存在左邊系數(shù)全為 0 的方程，那么無論右邊系數(shù)怎么變化，左邊系數(shù)在高斯消元后還是不變的，因此在任何情況下都不存在左邊系數(shù)全為 0 的方程，即在任何情況下都平衡，也就是穩(wěn)定。 證畢。 至此，問題解決，此算法的復(fù)雜度 ，即為高斯消元法的復(fù)雜度，對于 O(N) 2 關(guān)于高斯消元法，可以參見以前的國家集訓(xùn)隊論文。 2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 個方程， O(M)個未知數(shù)，高斯消元的復(fù)雜度為 O(N*M*M)。對于 N=100,M=100的極限數(shù)據(jù)，此復(fù)雜度還是非常寬松的。 對于退化數(shù)據(jù)的一些研究 在研究有物理特色的問題時，嚴(yán)謹(jǐn)是必要的，對于此題，雖然原題中盡量避免出現(xiàn)退化數(shù)據(jù)，但只要仔細(xì)琢磨，還是能想像出一些會退化的數(shù)據(jù)： 其實只要是某個點，與它相鄰的邊全在某一個不與地面平行的平面上，就很容易出現(xiàn)退化的情況。比如說像這樣的一種簡單例子： 上圖中在空中有 3 個點，在旁邊的兩個點由于有地面上三角架的支撐是穩(wěn)定的，這時候中間的點如果動的話，那么連接它的兩邊至少有一個會發(fā)生長度上的變化，這是不可能的，而它自己，由于兩個邊方向相同且不在垂直方向上，它又受到了重力的作用，它是不平衡的，它會移動，這就矛盾了。 對于這個矛盾，我是這樣理解的，某條邊對該點的拉伸，除了在此邊方向上的拉伸，再分出一個豎直方向的 0 向量，由于拉伸可以是無窮大的，而無窮大乘以 0 為一常數(shù)，那么可以用這一常數(shù)把該點支撐。或者也可以這樣理解，在邊上的力趨向于無窮大時，點移動的距離會越來越小，趨向于 0，因此當(dāng)邊上的力為無窮大時，點的移動為 0。點不移動的話， 就可以說此結(jié)構(gòu)是平衡的，進而也可以說它是穩(wěn)定的。 然而由于實際中，邊上的力是無法達到無窮大的，因此，我更覺得題目中“邊可以承受無限大的力”應(yīng)該“改成邊可以承受足夠大的力”，而出數(shù)據(jù)時應(yīng)該杜絕這樣的退化數(shù)據(jù)，因為對于這樣的數(shù)據(jù)，還是不能有很好的算法來分析其最終的情況，比如按我們的算法，最終對于上面提出的例子就會算出不平衡。即使有，我認(rèn)為這些討論也破壞了算法本身的優(yōu)美。事實上要杜絕這樣的數(shù)據(jù)，只要規(guī)定任何點所連的所有邊，不能在同一個平面上，以下情形例外：該平面垂直于地面，或者這些邊在與過該點某平面的同一邊。 小結(jié)及拓展 反觀解題的全過程，從物理模型到數(shù)學(xué)模型是最為重要的一步，對于大多數(shù)物理問題，物理模型建立是很簡單的，但是對于這樣抽象的模型是無法提出有效算法的的，因此勢必要對其進行轉(zhuǎn)化。本題的算法及結(jié)論可謂美妙，通過轉(zhuǎn)化，我們也發(fā)現(xiàn)了高斯消元法在解決實際問題中的價值。而對此題退化情況的分析，2022 年信息學(xué)奧領(lǐng)匹克競賽冬令營論文 浙江 方戈 讓我們對此題的解決更為嚴(yán)謹(jǐn)。 此題也不乏有向多方面拓展的潛力，如原題中，若對每條邊所承受的力的最大值加以限制，那么表現(xiàn)在方程中又會是怎么樣一個情形呢？此時平衡和穩(wěn)定與方程的關(guān)系又是怎么樣的呢？這樣的限制加了以后，問題就更 加實際，也更加需要往深處分析了，這也是此類問題的魅力之一吧。 例二 [water tanks](World Final 2022 Problem I) 題目大意 有 N 個圓柱形容器，它們的底面完全相同 —— 均為一單位面積，它們排成一列，并且已知它們的高度 col_H，第一個管子的上端是開口的，其余的均為密封，任兩個圓柱中間有管子相連，管子與地面平行（如下頁圖），已知第 i 個容器和第 i + 1 個容器之間的管子的高度為 pipe_H[i]，保證 pipe_H[i] ≠pipe_H[i + 1]。管子足夠粗使水以及空氣能夠順 利通過管子，管子足夠細(xì)使得不必計算它們中間的水的體積?，F(xiàn)緩慢往第一個管子倒水，過程中一切滿足以下規(guī)律（理想化的物理模型）： 開放的空氣中氣壓為一個大氣壓。 水不能被壓縮，空氣能被壓縮。 密封的空間內(nèi)處處氣壓相等，密封空