算法合集之問題中的變和不變

1、問題中的變與不變 陳雪 長沙市雅禮中學(xué) 410007【摘要】 信息學(xué)競賽中很多試題本質(zhì)上都是對變量進(jìn)行求解或者維護(hù)的過程。而有時候變量有很多種變化，單純的維護(hù)變量往往導(dǎo)致時空復(fù)雜度的低下。而如果能在變量的變化里找出其中“不變”的常量，往往能將問題迎刃而解。本文簡單的介紹了幾種在變量中找出“不變”的技巧，使得問題得到簡化?！娟P(guān)鍵字】變 變量 不變 常量 維護(hù)【引言】 變量在信息學(xué)中是最常見的，最基本的有循環(huán)變量，累計(jì)變量，決策變量。維護(hù)這些變量也是信息學(xué)中最基本的操作。信息學(xué)中關(guān)于變量的維護(hù)也有很多數(shù)據(jù)結(jié)構(gòu)，像平衡二叉樹，棧，隊(duì)列等等。 然而有些問題規(guī)模很大，僅僅是所需要的變量進(jìn)行維護(hù)的總操作數(shù)

2、就會達(dá)到無法承受的時空復(fù)雜度。于是我們就要對變量進(jìn)行化簡，找出其中的有用信息，從而使得維護(hù)這些變量的操作數(shù)更少，甚至將一些變量化成“常量”。下面就讓我們具體看看這類技巧在信息學(xué)中的應(yīng)用?！菊摹?將有用的變量放在一起看成一個集合，利用特殊的性質(zhì)，進(jìn)行一系列的操作，比如加發(fā)，乘法，是將變量轉(zhuǎn)化成常量的最常見的方法。下面我們就看這樣的一道問題。例1：螞蟻ants1一些螞蟻以1cm/s的速度在長度為lcm的線段上爬行，爬到線段端點(diǎn)就會掉下去。當(dāng)兩只螞蟻相遇，就會立刻掉頭返回。已知l和一開始每只螞蟻的位置，但不知道它們的方向，求它們最早何時全部掉落，最遲何時全部掉落。最多1,000,000只螞蟻。分析

3、：螞蟻一出來我們只知道位置，不知道方向。如果單純枚舉方向的話，光是各種方案的可能性就有21000000種，這個一個無法承受的數(shù)字。因此不可能去枚舉每個螞蟻的方向，不如先從簡單的問題著手。假設(shè)我們已知了螞蟻初始的方向后，接下來的任務(wù)就是模擬所有的螞蟻相遇和掉落的過程，求出最后一個掉落的時間。在這個過程中，最復(fù)雜的變量就是每只螞蟻的方向了，明顯在最壞情況下相遇次數(shù)可能達(dá)到n2級別，僅僅是維護(hù)每只螞蟻的方向和位置都是不能滿足題目的時間復(fù)雜度的要求的。我們從細(xì)節(jié)開始考慮問題：首先考慮題目中最基本的一個操作也就是2只螞蟻碰頭的情況：假設(shè)一只螞蟻a從左向右爬行，在x點(diǎn)的時候遇到了另一只從右向左的螞蟻b后返

4、回。同時螞蟻b也從x向右返回。 圖1 2只螞蟻相撞后的情況 將這2只螞蟻有用的信息也就是速度 (是向量)和當(dāng)前位置記錄下來一起構(gòu)成集合u，也就是。 在螞蟻a和螞蟻b相遇前瞬間一刻， 而在螞蟻a和螞蟻b相遇后瞬間一刻， 我們發(fā)現(xiàn)u=u，也就是說雖然對于每只螞蟻，它的速度發(fā)生了改變，但是把這2只螞蟻放在一個集合看的話，這個集合并沒有發(fā)生變化?；蛘哒f，在同一個集合內(nèi)的螞蟻相遇，這個集合是不會變的。 于是把所有的螞蟻看成一個大集合。 根據(jù)上面說提到的，在這個集合v內(nèi)的任何相遇對于集合v都沒有影響。 同時我們通過集合v可以知道，雖然每只螞蟻掉落的時間ti無法求出，但是所有的ti所構(gòu)成的集合t我們是可以求

5、出來的。 事實(shí)上就是t=第i只螞蟻按初始方向走到一端點(diǎn)的時間|1in。得到了這個有效的結(jié)論后，我們回到原來的問題：它們最早何時全部掉落，最遲何時全部掉落。先考慮最早何時全部掉落：根據(jù)t=第i只螞蟻按初始方向走到一頂點(diǎn)的時間|1in，我們貪心的讓每只螞蟻都朝離自己最近的端點(diǎn)爬行，即可保證t中最大值最小。同理最遲何時全部掉落的情況就是每只螞蟻朝離自己最遠(yuǎn)的端點(diǎn)爬行，即可保證t中最大值最大。最終我們得到了一個時間復(fù)雜度為o(n)的算法了。這已經(jīng)是理論的下限了。小結(jié)通過集合的概念，我們將原來要維護(hù)每個螞蟻的方向,位置這些規(guī)模龐大的變量轉(zhuǎn)化成一些“常量”。而通過這些“常量”不用維護(hù)就可以直接得出最終結(jié)果

6、。 集合操作在這類變量轉(zhuǎn)化成“常量”的問題有極廣泛地運(yùn)用，常?？梢岳妙}目給定的條件，來構(gòu)造集合，然后利用集合內(nèi)元素之間的特殊性質(zhì)來判斷無解或者優(yōu)化算法。 通過這道題目我們也能看到，仔細(xì)觀察，從細(xì)節(jié)入手，尋找變量之間的聯(lián)系，才能找到將變量轉(zhuǎn)化成“常量”的方法。例2：navigation game2這里有一個n行m列的方陣，第n行象征著這里，第1行象征著海那邊的彼岸。這中間的n-2行象征著你所期盼的大海。你的目標(biāo)是，控制一艘船，從這里的任意一個停泊處（用“h”表示），經(jīng)過最短的航行時間到達(dá)對岸的任意一個停泊處。只有這樣，你才可以通過這個通道。你的船只能向左，向右或向上前進(jìn)，一次一格，而且除非登陸

7、（這時你必須到達(dá)一個停泊處，從而結(jié)束你的游戲），你是不能駛向陸地的。記住，人生沒有回頭路。因此，一旦你離開一個格子，就永遠(yuǎn)也無法返回。向著目標(biāo)航行永遠(yuǎn)是一件令人愉快的事情。因此向上航行只需要消耗一個單位的時間。但是，看似原地打轉(zhuǎn)的左右方向的航行會讓人厭倦。如果某次左右航行之前你已經(jīng)連續(xù)進(jìn)行了x次左右航行，你這次左右航行所消耗的時間就是x+1個時間單位。海上你可能會遇到：o：障礙物。障礙物占據(jù)的格子，你永遠(yuǎn)也不會到達(dá)。f：命運(yùn)之輪。經(jīng)過這里，你的命運(yùn)會從此逆轉(zhuǎn)。我了解你的命運(yùn)有多么不幸。因此，你必須在航行途中經(jīng)過奇數(shù)次命運(yùn)之輪，才能安全到達(dá)彼岸。b：祝福石。走到這里是不需要時間的。s：暴風(fēng)雨的咒

8、符。走到這里所需的時間是正常情況的兩倍。1012132112311hhobffsooooooooofoh 圖2 例2的一個樣例說明數(shù)據(jù)范圍約定: n,m1000。分析：根據(jù)題目的要求，不能走回頭路，同時只能向上或者向右或者向左，于是我們考慮使用動態(tài)規(guī)劃：設(shè)表示從起點(diǎn)到(i,j)且走過的命運(yùn)之輪的次數(shù)為t的最少的代價(t表示奇偶性)。設(shè)表示從(i+1,j)到(i,j)的代價。 于是得到狀態(tài)轉(zhuǎn)移方程:（其中表示從(i,k)移動到(i,j)按照題目所給要求的代價，且(i,k)到(i,j)之間沒有障礙物,t=t xor (i,k)到(i,j)之間f個數(shù)）假設(shè)如果沒有題目所限制o,s的限制，那么。首先我

9、們只考慮從左往右走。那么狀態(tài)轉(zhuǎn)移方程可以寫成: 不妨另=,=。狀態(tài)轉(zhuǎn)移方程就變成了 考慮ui的最優(yōu)決策k，那么滿足(i>k>l)： 另,。把,畫在平面坐標(biāo)軸上，根據(jù)上面的式子有(,)-(,)之間的斜率小于i的時候，決策k比決策l更優(yōu)。事實(shí)上這是一個經(jīng)典的斜率優(yōu)化動態(tài)規(guī)劃的模型3。根據(jù)一般性我們知道維護(hù)一個隊(duì)列表示(,)的凸包中的下凸部分即可在均攤o(n)的時間內(nèi)求出最優(yōu)值。具體操作如下：用stack隊(duì)列來表示這個凸包的下凸部分。同時設(shè)隊(duì)首指針st和隊(duì)尾指針en。根據(jù)stack隊(duì)列維護(hù)的是凸包的下凸部分，那么滿足下面的性質(zhì)2.1:1. <<<2. -的斜率<

10、-的斜率. <-的斜率具體操作如下：從小到大枚舉i。對于當(dāng)前i，如果滿足-的斜率<i，則不斷刪除隊(duì)首元素。此時隊(duì)首元素就是當(dāng)前i的最優(yōu)決策。同時把i加入隊(duì)列隊(duì)尾，維護(hù)隊(duì)尾滿足性質(zhì)2.1。同樣我們也可以用類似的方法求出從右向左走的最小值。但是這道題目有個很獨(dú)特條件：經(jīng)過s不用時間和經(jīng)過b時間加倍。由于從不同的起點(diǎn)經(jīng)過一個s或者b產(chǎn)生的代價的改變是不同的，這個變化值決定了上面所說的方法不能夠直接搬到這個問題來?；氐皆瓉淼姆匠躺?。還是先考慮從左往右走，即j>k。顯然，無論(i,j)-(i,k)之間無論是b或者s，變量都能表述成一個關(guān)于(j-k)的二次函數(shù)。不妨設(shè)。當(dāng)然a和b都是需要

11、維護(hù)的變量。先考慮如何維護(hù)。假設(shè)k已經(jīng)固定，當(dāng)前。下面觀察。1.(i,j+1)上不是b也不是s: 有2.(i,j+1)上是b,不需要時間: 有3.(i,j+1)上是s,時間要加倍: 有根據(jù)上面所說，我們及時更新a,b就能得出新的。同時我們也能看到a的意義就是在(i,k+1)-(i,j)這一段中，。我們看另一種情況:如果j固定，而k發(fā)生變化的時候，的維護(hù)。重新掃描一遍肯定會導(dǎo)致算法效率低下。而且變量一共有o(n3)的級別，即使我們能在均攤o(1)的時間內(nèi)算出所有時間復(fù)雜度依然是o(n3)的。于是考慮優(yōu)化算法，盡量在短時間內(nèi)算出對我們有用的信息。假設(shè)當(dāng)前已知，而且已知的a和b。下面我們要求。既然重

12、新求沒有太好的方法，我們干脆做一個大膽的猜想那就是希望改變一些變量值使得的a和b能直接滿足的要求。把的代價分為2個部分，一部分表示從(i,k)出發(fā)在 (i,k)-(i,l)這一段的代價，另一部分表示在(i,l+1)-(i,j)這一段的代價。而第1部分的代價顯然就是。第二部分當(dāng)中既有對我們有用的代價,同時也有一部分的多余代價(從l出發(fā)比k節(jié)省的時間)。于是我們得到于是我們只要給就無需改變a和b。而這樣做會不會對產(chǎn)生影響？我們分析由-> 的過程，就能知道這樣做是沒有任何影響的。而這樣做的好處就是能把用一種更具體的形式給出。而不是一個虛擬的變量。實(shí)際上為了方便處理我們可以另。(b就是上文中的b

13、,也可以看成是的最優(yōu)決策k，中的那個b)這樣原狀態(tài)轉(zhuǎn)移方程就可以寫成(雖然a,b是變化的，但是對于單獨(dú)的一個，a,b是固定的)。仿照沒有b和s時的思路，設(shè)最優(yōu)決策k，同時觀察決策l。 另，。還是仿照上面的思路維護(hù)一個隊(duì)列表示所構(gòu)成的凸包的下凸部分。具體操作同沒有b和s的情況類似，這里就不重復(fù)了。但是這樣是否依然能保證正確性？ 每次j會增加1，而無論(i,j)上是b或者s，a只會發(fā)生1的變化。于是右邊的改變量依然能保證是非負(fù)的。所以正確性顯然。而從左到右反過來考慮即可?？偟臅r間復(fù)雜度:o(行數(shù)*(列數(shù)+隊(duì)列的操作數(shù))=o(nm)。小結(jié) 這道題目中，由于特殊的條件的約束，如果使用其他方法維護(hù)cos

14、t(i,k,j)中的a,b反而令問題更加復(fù)雜。于是大膽猜想，通過調(diào)整其他變量使a,b不變，從而在后面的問題中，利用隊(duì)列和斜率將算法優(yōu)化到o(nm)。例三：circular railway4在一條長度為l的環(huán)形軌道上有n個a類點(diǎn)，n個b類點(diǎn)?，F(xiàn)在要你安排一種方案使得這n個a類點(diǎn)和n個b類點(diǎn)一一匹配。并且所有匹配點(diǎn)之間的最短距離（指在軌道上）和最小。數(shù)據(jù)范圍: 1 n 50000, 2 l 109分析：首先將n個a類點(diǎn)按順時針排序后設(shè)他們的坐標(biāo)為,.。 將n個b類點(diǎn)按順時針排序后設(shè)他們的坐標(biāo)為,.。(同時另) 顯然問題實(shí)際上就是一個二分圖的最小權(quán)匹配。但是最小權(quán)匹配最壞情況下是o(n4)的時間復(fù)雜

15、度，對于題目的數(shù)據(jù)范圍，肯定是不能滿足要求的。 仔細(xì)分析我們就能發(fā)現(xiàn)最小權(quán)匹配時有一條重要的性質(zhì): 性質(zhì)3.1: 2條匹配邊肯定不會相交。 圖3 性質(zhì)3.1的證明 反證：如果出現(xiàn)了2條匹配邊-和-相交，那么我們交換,的匹配使得-和-肯定可以讓匹配的總權(quán)值最小。（如圖3所示） 按照性質(zhì)3.1，我們可以知道最小權(quán)匹配必然滿足下面的條件： 不妨另匹配的點(diǎn)是，然后 (1<in)匹配的點(diǎn)就是從開始順時針數(shù)到的第i個b類點(diǎn)。（如圖4所示，綠色代表，藍(lán)色代表） 圖4 最小權(quán)匹配的方案 既然最小權(quán)匹配滿足上述條件，我們得到了算法3.2:枚舉與匹配的點(diǎn),然后根據(jù)上面的條件，可以知道匹配的點(diǎn)就是。然后根據(jù)每

16、條匹配求出總代價，這當(dāng)中最小的代價就是我們要求的最小權(quán)匹配了。算法3.2的時間復(fù)雜度為o(n2)。盡管對于n=50000仍然有些力不從心，但是已經(jīng)有了很大的進(jìn)步了。 繼續(xù)分析假設(shè)匹配的點(diǎn)，同時設(shè)表示至的最短距離。那么我們知道在上面所說的算法中，只要維護(hù)了變量，就能得出最優(yōu)答案。但是僅僅是把所有的至的最短距離求出來就已經(jīng)o(n2)，也就是說一共有n2種不同的值。這也意味著維護(hù)或者預(yù)處理計(jì)算的時間復(fù)雜度都是o(n2)的。為了優(yōu)化算法，我們要考慮另辟捷徑。 換個角度考慮。下面具體分析。同時令j=。 下面考慮的幾種取值可能。 1. 2. 3. 4. 下面繼續(xù)分析最優(yōu)值分別為每種情況的時候和關(guān)系。 1.

17、當(dāng)最優(yōu)，此時和要滿足條件：1. > 2. -l/2 2.當(dāng)最優(yōu)，此時和要滿足條件：1. > 2. -l/2 3當(dāng)最優(yōu)，此時和要滿足條件：1. ->l/2 4當(dāng)最優(yōu)，此時和要滿足條件：1. ->l/2 通過上面的分析發(fā)現(xiàn)只與當(dāng)前的和有關(guān)，既然關(guān)于變量無能為力，那么我們不妨把注意力放到和上來，不妨另。下面考慮對的影響，也就是函數(shù)。 根據(jù)上面的分析，我們知道當(dāng) 1當(dāng)->l/2有， 2當(dāng)l/2->0有， 3當(dāng)l/2->0有， 4當(dāng)l/2<-有， 我們把注意力放到變量上來，通過上面的討論，可以知道雖然還是個變量，但是與相比，當(dāng)j從1遞增到n這個過程中最多有

18、4種情況，事實(shí)上1,4不會同時出現(xiàn)，只有3種。也就是說可以看成是幾乎不變的“常量”了。 同樣的方法分析最多也只有4種變化。 現(xiàn)在我們從小到大枚舉和a1匹配的點(diǎn)bk后，其他的點(diǎn)按順序一一匹配，現(xiàn)在的總代價。 當(dāng)k變化的時候，我們只看的變化，把放到一邊。根據(jù)上面的分析，在我們從1到n枚舉k的過程中，每一個,最多只會變4次。而我們可以通過預(yù)處理知道對于每個，變到是在k=變成k=+1時改變的，變到是在k=變成k=+1時改變的，變到是在k=變成k=+1時改變的。同理也可以通過預(yù)處理知道每個變量它發(fā)生改變的時間。不妨把,發(fā)生改變看成一次事件，可以知道事件總數(shù)肯定不會超過8n。假設(shè)我們已經(jīng)通過預(yù)處理知道每件事件發(fā)生的時間（每次事件的時間x指事件是在k=x變成k=x+1發(fā)生的）。而通過這些事件我們就可以即時維護(hù)sum。在sum達(dá)到最小值時，就是我們要求的答案了。整個算法的流程如下： 1.將ai和bi排序。 2.預(yù)處理求出每個事