二分的應(yīng)用與補(bǔ)集轉(zhuǎn)換思想

1、二分倍增與補(bǔ)集轉(zhuǎn)換思想的應(yīng)用,長沙市第一中學(xué) 曹利國,分治思想,分治(divide-and-conquer)就是“分而治之”的意思，其實(shí)質(zhì)就是將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題的解。其三個步驟如下； 分解(Divide)：將原問題分成一系列子問題。 解決(Conquer)：遞歸地解各子問題。若子問題足夠小，則可直接求解。 合并(combine)；將子問題的結(jié)果合并成原問題的解。,分治思想,如果在將規(guī)模為n的問題分成k個不同子集合的情況下，能得到k個不同的可分別求解的子問題，其中1k=n，而且在求出了這些子問題的解之后，還可找到

2、適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€問題的解，那么，具備上述特性的問題可考慮使用分治策略設(shè)計(jì)求解。這種設(shè)計(jì)求解的思想就是將整個問題分成若干個小問題后分而治之。,分治思想,分治的應(yīng)用,解決一類求方程的根的問題 解決真假硬幣的稱量問題 基于NLgN算法效率的排序和查找問題(歸并排序，二分查 找) 倍增算法 快速冪,分治的應(yīng)用(分段處理),例題：取余運(yùn)算（mod.exe） 輸入b，p，k的值，編程計(jì)算bp mod k的值。其中的b，p，k*k為長整型數(shù)。 【輸入輸出樣例】 mod.in 2 10 9 mod.out 210 mod 9=7,分析,1、用高精度計(jì)算比較煩，復(fù)雜度太高 2、轉(zhuǎn)而用其他方法求解 （1

3、）取模運(yùn)算的一個規(guī)律：a*b mod k=(a mod k)*(b mod k) mod k （2）運(yùn)用規(guī)律可以把樣例數(shù)據(jù)分解：b19=b2*9+1=b 9b9b，其中的指數(shù)9可以繼續(xù)分解為241，4再分解程220，2120，1011。反過來，我們可以從0出發(fā)，通過乘以2再加上1或0推得1，2，4，9，19，然后依次以這些數(shù)為指數(shù)的自然數(shù)除以k的余數(shù)。,分析,（3）不難看出，前面乘以2后要加上的1或0就是該數(shù)對應(yīng)二進(jìn)制數(shù)各位上的數(shù)字1或0。如，19（10011）2 。求解的過程也就是將二進(jìn)制數(shù)還原為十進(jìn)制數(shù)的過程。 （4）綜上所述，該題可采用分治得思想進(jìn)行遞推求解。 我們計(jì)算出A(2k)，即

4、A,A2,A4,A8這需要logK的時間 而我們回答AK，則根據(jù)K的二進(jìn)制位上的1來相乘 A11=A8*A2*A 也只需要logK次,問題轉(zhuǎn)化再二分,例題(北京08省選)： 在數(shù)軸上有N類點(diǎn)，每一類用S,E,D來表示，意思是這些點(diǎn)分布在 S,S+D,S+2DS+kD (S+kD=E) 已知最多只有一個坐標(biāo)上有奇數(shù)個點(diǎn)，要求找出它或指出不存在。,分析,我們用0表示偶數(shù)個點(diǎn)，1表示奇數(shù)個點(diǎn) 那么數(shù)軸上的點(diǎn)分布如下 000000000000000000010000. 因?yàn)閿?shù)軸太大，點(diǎn)太多 我們無法快速判斷1的位置,分析,000000000000000000010000. 考慮前綴和 00000000

5、0000000000011111. 我們可以用二分法找到0/1分界點(diǎn)，即唯一的1的位置 每次二分時，掃描每一類點(diǎn)，統(tǒng)計(jì)點(diǎn)的前綴和 復(fù)雜度O(N*logS)，S為數(shù)軸長，即值域,二分再轉(zhuǎn)化問題,NOIP2010，第三題 關(guān)押罪犯 將N個人分成兩組，其中M對人有Ci的不和諧值，其中如果兩人在同一組，并且它們兩人不和諧，那么就會有Ci的不和諧值。 要求找出一個分組方案，使得最大不和諧值最小。,分析,直接做不好下手 由于要求最大值最小，即一個上界，所以我們可以二分這個上界 那么我們就能確定哪些人不能在一組(不和諧值大于上界的) 此時我們只需判斷這個圖能否構(gòu)成二分圖即可。 用簡單的BFS即可解決這個問題

6、,用BFS做二分圖判定,二分圖判定: 判斷一個圖能否形成二分圖 我們從任一點(diǎn)開始，令其在二分圖左邊，然后開始BFS，每次搜到的點(diǎn)放對面即可，直至所有點(diǎn)放完或出現(xiàn)矛盾 正確性： 對于每個聯(lián)通量而言，一個點(diǎn)如果確定，其他點(diǎn)均確定，而這個點(diǎn)放左，放右實(shí)際上是對稱的方案,二分的選擇,有趣的元素(2011克羅地亞競賽): 如果一個數(shù)列中 2*K 的元素中前 K 個元素和與后 K 個元素和都不大于 S 那么我們說這些元素是有趣的。 給你一個長度為 N 的數(shù)列 A,求各個元素從本身開始能構(gòu)成的最長有趣元素的長度。,一個簡單的想法,枚舉i，二分最遠(yuǎn)j使得ij與j+1j+j-i+1為有趣的 i j j+1 j+

7、j-i+1 時間復(fù)雜度O(NlogN) 看似沒問題的二分算法其實(shí)是錯誤的 如S=100,N個數(shù)為 1 1 98 98 1 1 當(dāng)i=1，二分j=2時不合法，而其實(shí)j=3時合法,錯誤的原因,二分是需要問題滿足單調(diào)性的 形象的說就如剛才講過的北京省選題，每個點(diǎn)的狀態(tài)形如: 00000000000011111111111 0代表合法，1代表不合法 而不能是凌亂的 00010110111010001010000,還是可以二分,我們考慮枚舉起點(diǎn)再二分是不對的 但是如果枚舉中間點(diǎn)再二分是沒有錯的! 所以我們枚舉中間點(diǎn)，再二分最遠(yuǎn)擴(kuò)展距離 這樣我們得到若干區(qū)間，我們將包含的區(qū)間去掉 再處理一下就能得到答案！

8、 用單調(diào)隊(duì)列還可以做到O(N),倍增算法,如何設(shè)計(jì)最少的面值拼出連續(xù)最大的面值？ 答案自然是1,2,4,8.即2k 倍增算法就基于這個性質(zhì)，我們通過解決所有2k的問題來解決整個問題,倍增算法解決RMQ問題,RMQ問題： 給定N個數(shù)，M個詢問(a,b) 每次回答第a個數(shù)到第b個數(shù)中的最小值 線段樹等常數(shù)較大，能不能不利用高級數(shù)據(jù)結(jié)構(gòu)做到O(NlogN),分析,我們用Fik表示從i開始，連續(xù)2k個數(shù)的最小值 那么有Fi0=Ai 容易得到由于2k個數(shù)的最小值是前2(k-1)個數(shù)的最小值或者后2(k-1)個數(shù)的最小值。 Fik =minFik-1,Fi+2(k-1)k-1,分析,那么我們很簡單的預(yù)處理

9、出了F數(shù)組 主要代碼如下 讀入Ai，F(xiàn)i0=Ai 循環(huán)k=1logN 循環(huán)i=1N Fik=minFik-1,Fi+2(k-1)k-1,分析,至于回答，類似拼錢 我們每次找出一張最大面值 如回答26的最小值 我們先找到22=4，用F22更新答案 那么現(xiàn)在變成56，我們找到21=2 用F51更新答案 總時間復(fù)雜度O(NlogN)，常數(shù)小，方便寫，容易理解。,倍增的其他應(yīng)用,LCA（最近公共祖先問題）或一些靜態(tài)的樹路徑詢問(樹上兩點(diǎn)路徑權(quán)和/最值) 我們用Fik表示i到其2k個祖先的的信息 用跟剛才類似的倍增的方法可以在logN的時間內(nèi)回答詢問 后綴樹組的倍增法構(gòu)造 ,例一單色三角形問題（POI9

10、714 TRO）,題目大意,空間里有n個點(diǎn)，其中任意三點(diǎn)不共線。每兩點(diǎn)間都有紅色或黑色邊（只有一條，非紅即黑?。┻B接。若一個三角形的三邊同色，則稱它為單色三角形。對于給定的點(diǎn)數(shù)和紅色邊的列表，找出單色三角形的個數(shù)。例如下圖中有5個點(diǎn)，10條邊，形成3個單色三角形。,輸入點(diǎn)數(shù)n、紅色邊數(shù)m以及這m條紅色的邊所連接的頂點(diǎn)標(biāo)號，輸出單色三角形個數(shù)R。 3=n=1000，0=m=250000。,初步分析,自然的想法：用一個數(shù)組記錄每兩點(diǎn)間邊的顏色。枚舉所有的三角形（這是通過枚舉三個頂點(diǎn)實(shí)現(xiàn)的），判斷它的三邊是否同色，若同色則總數(shù)R加1（當(dāng)然，初始時R為0）。,空間上：O(n2)，需要一個1000*10

11、00的大數(shù)組,時間上：O(n3)，n達(dá)到1000，無法接受！,常用技巧：無從下手。,深入思考,本題中單色三角形的個數(shù)可以非常龐大，所以一切需要枚舉每個單色三角形的方法都是不可能高效的。,單純的枚舉不可以，那么組合計(jì)數(shù)是否可行呢？,從總體上進(jìn)行組合計(jì)數(shù)很難想到。我們嘗試枚舉每一個點(diǎn)，設(shè)法找到一個組合公式來計(jì)算以這個點(diǎn)為頂點(diǎn)的單色三角形的個數(shù)。,深入思考,組合公式很難找到！,補(bǔ)集轉(zhuǎn)化,從反面來看問題：每兩點(diǎn)都有邊連接，所以每三個點(diǎn)都可以組成一個三角形（單色或非單色的），所有的三角形數(shù)S=C(n,3)=n*(n-1)*(n-2)/6。,單色三角形數(shù)R加上非單色三角形數(shù)T就等于S，所以如果我們可以求出

12、T，那么顯然，R=ST。,原問題轉(zhuǎn)化為：怎樣高效地求出T,補(bǔ)集轉(zhuǎn)化,原先的枚舉組合計(jì)數(shù)算法的障礙是無法在“邊”與“單色三角形”之間建立確定的對應(yīng)關(guān)系。,YES!,補(bǔ)集轉(zhuǎn)化,非單色三角形的三條邊共有紅黑兩種顏色,其中兩條邊同色，另一條邊異色,如果從一個頂點(diǎn)B引出兩條異色的邊BA、BC，則無論AC邊是何種顏色，三角形ABC都只能是一個非單色三角形,補(bǔ)集轉(zhuǎn)化,A,C,B,A,C,B,非單色三角形數(shù)T=“有公共頂點(diǎn)的異色邊”的總對數(shù)Q/2,補(bǔ)集轉(zhuǎn)化,補(bǔ)集轉(zhuǎn)化,Q求出之后，R=ST=n*(n-1)*(n-2)/ 6-Q/2,時間復(fù)雜度：O(m+n) 空間復(fù)雜度：O(n),優(yōu)秀的算法！,小結(jié),通過補(bǔ)集轉(zhuǎn)化

13、，我們在原來無法聯(lián)系起來的“邊”和“三角形”之間建立起確定的關(guān)系，并以此構(gòu)造出組合計(jì)數(shù)的公式。,WC2007剪刀石頭布,在一些一對一游戲的比賽（如下棋、乒乓球和羽毛球的單打）中，我們經(jīng)常會遇到A勝過B，B勝過C而C又勝過A的有趣情況，不妨形象的稱之為剪刀石頭布情況。有的時候，無聊的人們會津津樂道于統(tǒng)計(jì)有多少這樣的剪刀石頭布情況發(fā)生，即有多少對無序三元組(A, B, C)，滿足其中的一個人在比賽中贏了另一個人，另一個人贏了第三個人而第三個人又勝過了第一個人。注意這里無序的意思是說三元組中元素的順序并不重要，將(A, B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C,

14、A, B)和(C, B, A)視為相同的情況。 有N個人參加一場這樣的游戲的比賽，賽程規(guī)定任意兩個人之間都要進(jìn)行一場比賽：這樣總共有 場比賽。比賽已經(jīng)進(jìn)行了一部分，我們想知道在極端情況下，比賽結(jié)束后最多會發(fā)生多少剪刀石頭布情況。即給出已經(jīng)發(fā)生的比賽結(jié)果，而你可以任意安排剩下的比賽的結(jié)果，以得到盡量多的剪刀石頭布情況。,分析,題目大意 對于一個競賽圖，給定一些邊，要求你通過給剩下的邊定向，最大化圖中的三元環(huán)。 競賽圖：基礎(chǔ)圖(將有向邊變?yōu)闊o向邊)為完全圖的有向圖 三元環(huán)：三個點(diǎn)組成的環(huán),分析,最大化三元環(huán)并不好想，利用補(bǔ)集轉(zhuǎn)化 三元環(huán)的個數(shù)P=圖中所有由三個點(diǎn)構(gòu)成的子圖個數(shù)-這些子圖中不是三元環(huán)的個數(shù)。 容易證明，三個點(diǎn)的競賽圖不是三元環(huán)的充要條件是圖中有一點(diǎn)入度等于2。,分析,三元環(huán)的個數(shù)P= 圖中所有由三個點(diǎn)構(gòu)成的子圖個數(shù)A-這些子圖中不是三元環(huán)的個數(shù)B，入度為Di P=A-B =C(n,3) - sigma C(Di,2) =n*(n-1)*(n-2)/6 - sigma Di*(Di-1)/2 =n*(n-1)*(n