分治和倍增課件

分治合倍增ByDJ什么是分治？字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。舉個(gè)栗子萬(wàn)一聯(lián)賽時(shí)腦抽了，忘記algorithm怎么打了，該怎么快排呢？（假設(shè)你只忘單詞沒(méi)忘算法）來(lái)個(gè)學(xué)霸講講快排原理？也就是說(shuō)，我們可以通過(guò)不斷地將某一區(qū)間內(nèi)的數(shù)分成比第一個(gè)數(shù)大的和比第一個(gè)數(shù)小的兩部分，如此便可將整個(gè)區(qū)間分成兩小份，繼續(xù)對(duì)每一個(gè)區(qū)間進(jìn)行quicksort操作，直到區(qū)間內(nèi)只有兩個(gè)數(shù)為止。這便是分治了！逆序?qū)χv到快排就想到歸并排序，講到歸并排序就想到逆序?qū)ΑＤ嫘驅(qū)?，說(shuō)白了就是你在我后面你還比我小的一對(duì)數(shù)，如132中，3、2為一組逆序?qū)ΑＶ苯訕闼厮惴?，不用講了吧？如何巧妙地算逆序?qū)δ?？無(wú)序數(shù)列太亂，先從有序考慮。兩個(gè)有序數(shù)對(duì)前后相接，逆序?qū)υ趺辞螅磕敲窗褵o(wú)序轉(zhuǎn)化成有序呢？討論三步：分、治、合?；舅悸肺覄偛耪f(shuō)到了歸并排序，那么我們能否在歸并排序時(shí)做點(diǎn)手腳，順便記錄逆序?qū)δ?？答案是肯定的！在兩個(gè)有序數(shù)列歸并時(shí)，設(shè)兩個(gè)指針，從后往前遍歷，當(dāng)搜到后列當(dāng)前元素小于前排當(dāng)前元素時(shí)，則說(shuō)明前列指針及它后面的元素均組成逆序?qū)Γ尤隺nswer中。又來(lái)個(gè)栗4+3+2+1偽代碼：Voidni(intl,intr){if(l==r)return;If(r-l==1){if(本身為逆序?qū)?{ans++;交換位置;}return;}//治Intmid=(l+r)/2;Ni(l,mid);mi(mid+1,r);//分把兩個(gè)有序數(shù)列a[l..mid]、a[mid+1..r]歸并排序同時(shí)求逆序?qū)?；Return;}平面內(nèi)最近點(diǎn)對(duì)問(wèn)題：給出n個(gè)點(diǎn)的坐標(biāo)(x,y)，求出最近兩點(diǎn)的距離（4位小數(shù)）。能用分治法算一維嗎？能不能將其拓展到二維呢？討論如何設(shè)計(jì)三步：分、治、合。二維呢？一維啟示我們：要按照坐標(biāo)中位數(shù)來(lái)分，效果最好。合？初步偽代碼Intzjdd(點(diǎn)集s)//不會(huì)STL的可試著數(shù)組模擬，可加數(shù)組元素個(gè)數(shù)為參數(shù){if(規(guī)模足夠小)return解決方案;

遍歷點(diǎn)集的x，獲得中位數(shù)mid;

再次遍歷，分出x=mid左邊的點(diǎn)集s1和x=mid右邊上的點(diǎn)集s2;intm=min(zddd(s1),zjdd(s2));

找到x=mid附近點(diǎn)的最近距離m0;returnmin(m,m0);}如何合呢？合之前，我們已經(jīng)找到每一個(gè)子問(wèn)題中最近距離m了，顯然與x=mid距離大于等于m的點(diǎn)是無(wú)論如何也找不到更優(yōu)解的。于是我們確定了范圍：x∈(mid-m,mid+m)。運(yùn)氣不好的話，可能會(huì)囊括所有點(diǎn)（比如集中在一條平行于y軸上的線上，s1=?，s2=?，結(jié)果我們等于沒(méi)分）。這些點(diǎn)之間難道又要爆搜嗎？顯然不必，否則我就直接過(guò)了。我們可以設(shè)范圍內(nèi)x=mid左邊點(diǎn)集為p1,其他為p2，mid既在p1內(nèi)又在p2內(nèi)?？梢园l(fā)現(xiàn)，除非p1中的點(diǎn)在x=mid上未被考慮過(guò)，否則它們之間的距離都大于等于m。所以，我們可以對(duì)p1內(nèi)每一個(gè)點(diǎn)進(jìn)行考慮，如果不在mid上，易證可能存在的更優(yōu)解在p2中且位于以這個(gè)點(diǎn)為圓心m為半徑的圓內(nèi)。但圓內(nèi)的坐標(biāo)判斷太煩人，干脆把圓擴(kuò)充成矩形，看著順眼，判得容易。有人要問(wèn)了：把圓擴(kuò)大成矩形，不是會(huì)增加更多點(diǎn)，增大復(fù)雜度嗎？事實(shí)上，這矩形內(nèi)的點(diǎn)撐死就6個(gè)點(diǎn)（mid上密集點(diǎn)除外）。有沒(méi)有大神來(lái)證明一下？證明過(guò)程請(qǐng)點(diǎn)擊。證明：不妨把矩形分成六個(gè)小矩形，每個(gè)矩形為2/3m*1/2m，易證每個(gè)矩形內(nèi)不可能有兩個(gè)點(diǎn)，否則這兩個(gè)點(diǎn)的距離會(huì)小于m。根據(jù)鴿籠原理，每個(gè)矩形內(nèi)最多只能有一個(gè)。而且他們之間還相互限制，可能使中間兩個(gè)矩形為空。撐死塞下六個(gè)點(diǎn)只有一種可能。（不過(guò)，mid上一堆點(diǎn)也不是不可能的）OK,我們得到合的方案了！我們可以找到p1、p2后將他們關(guān)于ysort一遍，再對(duì)于p1內(nèi)每一個(gè)點(diǎn)，我們可以在p2內(nèi)建立一個(gè)這樣的矩形，遍歷矩形內(nèi)所有點(diǎn)，若發(fā)現(xiàn)某個(gè)距離m0<m，更新m的值。遍歷完畢后，返回。優(yōu)化？每合一次都要sort，如果出題者把每次sort都弄到最壞呢？如果陰險(xiǎn)的出題者弄一堆點(diǎn)在一條豎直線上呢？練習(xí)題（水題練手感）1、小學(xué)奧數(shù)：兩人一車(chē)（附帶駕駛員）從A地到B地，輸入s、v人、v車(chē)（實(shí)數(shù)，v人<V車(chē)），求兩人同時(shí)到達(dá)B地的最短時(shí)間。2、初中奧數(shù)：給出n次方程(n<5)，按降冪輸入每一項(xiàng)的系數(shù)，保證每?jī)蓚€(gè)解的距離不小于1.0，求-100~100內(nèi)所有解。3、高中選修：給出n次函數(shù)(2<=n<5)，按降冪輸入每一項(xiàng)的系數(shù)，保證每個(gè)極值點(diǎn)的橫坐標(biāo)之差不小于1.0，求-100~100內(nèi)所有極值。（若函數(shù)f(x)在x?的一個(gè)鄰域D有定義，且對(duì)D的所有點(diǎn)，都有f(x)<f(x?)，則稱(chēng)f(x?)是函數(shù)f(x)的一個(gè)極大值，反之，f(x)>f(x?)，則為極小值，統(tǒng)稱(chēng)極值）以上均輸出3位小數(shù)，文件名：”shui”+題號(hào)，歡迎AK。SampleinputSampleoutput32123

456

789

567

891

234

樣例解釋?zhuān)鹤畲蠊舱叫尉仃嚍榧t色標(biāo)記。請(qǐng)自行到網(wǎng)上評(píng)測(cè)。練習(xí)題（較難題提升）鳴謝：Cab

剛才那些水題想必是稍微想想就能夠想出來(lái)的，不過(guò)其中蘊(yùn)含了一個(gè)非常重要的思想：二分答案。什么是二分答案呢？當(dāng)一個(gè)問(wèn)題難于直接求解甚至不能直接求解時(shí)，我們不如換個(gè)角度，從答案這邊入手，從問(wèn)題的邊界二分，不停逼近，直到找出那個(gè)最優(yōu)解?？啥执鸢傅囊螅河薪缧浴握{(diào)性。使用二分答案的條件：直接求解困難（其他題要裝逼硬是用二分答案我也沒(méi)辦法）血的教訓(xùn)——河中跳房子?。。‘?dāng)時(shí)被貪心坑了的有木有！發(fā)現(xiàn)貪心不行又沒(méi)學(xué)二分答案的有木有！用二分答案二三十行AC的有木有！如何二分呢？記錄初始狀態(tài)下最大距離和最小距離，以此為界二分答案，所有距離小于當(dāng)前預(yù)設(shè)答案的就搬掉石頭。若搬掉的總數(shù)大于M，則答案過(guò)小，往大一邊分；否則答案足夠大，往小的一邊分。二分答案通用偽代碼Voidfin(intl,intr){if(l==r)return;intmid=(l+r)/2;

If(mid符合要求){ans=mid;fin(mid+1,r);}Elsefin(l,mid-1);}還有呢?。ň毩?xí)題，都不是裸的）1、bzoj1082為了搭建柵欄，F(xiàn)J需要R塊木料，但他只找來(lái)了N塊很長(zhǎng)的木料，這些木料可以裁成稍短一些的木料。但為了柵欄的穩(wěn)固，不能將兩塊短的拼起來(lái)。FJ想知道他最多能如愿得到多少塊木料。輸入：4行，分別為：N、N塊木料的長(zhǎng)度、R、R塊木料的長(zhǎng)度輸出：最多能得到多少需要的長(zhǎng)度的木料。怎么破？二分答案+搜索2、bzoj2732沫沫最近在玩一個(gè)二維的射箭游戲，這個(gè)游戲中的x軸在地面，第一象限中有一些豎直線段作為靶子，任意兩個(gè)靶子都沒(méi)有公共部分，也不會(huì)接觸坐標(biāo)軸。沫沫控制一個(gè)位于(0,0)的弓箭手，可以朝0至90°中的任意角度以任意大小的力量射出帶有穿透能力的光之箭。由于游戲中沒(méi)有空氣阻力，并且光之箭沒(méi)有箭身，箭的軌跡會(huì)是一條標(biāo)準(zhǔn)的拋物線，被軌跡穿過(guò)的所有靶子都認(rèn)為被沫沫射中了，包括那些只有端點(diǎn)被射中的靶子。這個(gè)游戲有多種模式，其中沫沫最喜歡的是闖關(guān)模式。在闖關(guān)模式中，第一關(guān)只有一個(gè)靶子，射中這個(gè)靶子即可進(jìn)入第二關(guān)，這時(shí)在第一關(guān)的基礎(chǔ)上會(huì)出現(xiàn)另外一個(gè)靶子，若能夠一箭雙雕射中這兩個(gè)靶子便可進(jìn)入第三關(guān)，這時(shí)會(huì)出現(xiàn)第三個(gè)靶子。依此類(lèi)推，每過(guò)一關(guān)都會(huì)新出現(xiàn)一個(gè)靶子，在第K關(guān)必須一箭射中前K關(guān)出現(xiàn)的所有K個(gè)靶子才能進(jìn)入第K+1關(guān)，否則游戲結(jié)束。沫沫花了很多時(shí)間在這個(gè)游戲上，卻最多只能玩到第七關(guān)“七星連珠”，這讓她非常困惑。于是她設(shè)法獲得了每一關(guān)出現(xiàn)的靶子的位置，想讓你告訴她，最多能通過(guò)多少關(guān)。輸入文件第一行是一個(gè)正整數(shù)N，表示一共有N個(gè)靶子。接下來(lái)有N行，第i+1行是用空格隔開(kāi)的三個(gè)正整數(shù)xi，yi1，yi2(yi1<yi2

)，表示第i個(gè)靶子的橫坐標(biāo)是xi，縱坐標(biāo)的范圍是從yi1到y(tǒng)i2

。輸入保證30%的數(shù)據(jù)滿足N≤100，50%的數(shù)據(jù)滿足N≤5000，100%的數(shù)據(jù)滿足N≤100000且給出的所有坐標(biāo)不超過(guò)109。輸入樣例：輸出樣例：54

2812

545

3810

623

137樣例解釋如圖，此時(shí)無(wú)論如何也過(guò)不了第五關(guān)，所以只能通過(guò)4關(guān)。怎么破？二分答案+半平面交3、bzoj1822在游戲《魔獸爭(zhēng)霸》中，巫妖是一種強(qiáng)大的英雄，它的技能冷凍波每次可以殺死一個(gè)小精靈。我們認(rèn)為，巫妖和小精靈都可以看成是平面上的點(diǎn)。當(dāng)巫妖和小精靈之間的直線距離不超過(guò)R，且巫妖看到小精靈的視線沒(méi)有被樹(shù)木阻擋的話，巫妖就可以瞬間殺滅一個(gè)小精靈。在森林里有N個(gè)巫妖，每個(gè)巫妖釋放冷凍波之后，都需要等待一段時(shí)間，才能再次施放。不同的巫妖有不同的等待時(shí)間和施法范圍，但相同的是，每次施放都可以殺死一個(gè)小精靈。現(xiàn)在巫妖的頭目想知道，若從0時(shí)刻開(kāi)始計(jì)算，至少需要花費(fèi)多少時(shí)間可以殺死所有的小精靈？輸入文件第一行包含三個(gè)整數(shù)N、M、K(N,M,K<=200)，分別代表巫妖的數(shù)量、小精靈的數(shù)量和樹(shù)木的數(shù)量。接下來(lái)N行，每行包含四個(gè)整數(shù)x,y,r,t，分別代表了每個(gè)巫妖的坐標(biāo)、攻擊范圍和施法間隔（單位為秒）。再接下來(lái)M行，每行兩個(gè)整數(shù)x,y，分別代表了每個(gè)小精靈的坐標(biāo)。再接下來(lái)K行，每行三個(gè)整數(shù)x,y,r，分別代表了每個(gè)樹(shù)木的坐標(biāo)和半徑。輸入數(shù)據(jù)中所有坐標(biāo)范圍絕對(duì)值不超過(guò)10000，半徑和施法間隔不超過(guò)20000。輸出一行，為消滅所有小精靈的最短時(shí)間（以秒計(jì)算）。如果永遠(yuǎn)無(wú)法消滅所有的小精靈，則輸出-1。輸入樣例：輸出樣例：2315

-10001003

10001005

-100-10

10010

11011

5510

怎么破？二分答案+網(wǎng)絡(luò)流倍增概念倍增是什么？我也說(shuō)不清。問(wèn)大神，大神忙著裝逼沒(méi)時(shí)間。當(dāng)時(shí)我心里是這樣想的：據(jù)說(shuō)是把一大坨東西按照2^k分成多份，每份分別解決什么的，與分治思想有些相似?？焖賰缛∧Ｊ裁垂淼摹拍钚缘奈乙膊惶瑥膶?shí)踐中理解吧！看一道例題：麥森數(shù)。從文件中輸入P(1000<P<3100000)，計(jì)算2^p-1的位數(shù)和最后500位數(shù)字。不難發(fā)現(xiàn)，2^n=(2^(n/2))^2*2^(n%2)。不妨設(shè)f(x)=2^x，則有遞推公式f(x)=f^2(n/2)*2^(n%2)。對(duì)于這個(gè)數(shù)據(jù)范圍，2^22就ok了，開(kāi)25*510的數(shù)組綽綽有余，然后，回憶必修一的一個(gè)公式：a^(m+n)=a^m*a^n，把p分解成2^p1+2^p2+2^p3……，則原式=2^(2^p1+2^p2+2*p3+……)=2^(2^p1)*2^(2^p2)*……，而2^(2^k)我們已經(jīng)預(yù)處理存入了數(shù)組中，直接調(diào)用第k行就行了。（什么？問(wèn)怎么算乘法？高乘高都不會(huì)的面壁去！去背10.26的基礎(chǔ)題5?。┧裕梢赃@樣理解：所謂倍增，就是把一個(gè)數(shù)據(jù)規(guī)模為n的問(wèn)題分解成若干個(gè)2^ai的和，預(yù)處理數(shù)據(jù)范圍內(nèi)所有2^ai的情況，再將這些規(guī)模為2^ai的問(wèn)題通過(guò)一定的方法合并，得出原問(wèn)題的解。分治基本上是分治合三步走，如何巧妙地分、如何高效地合是其重點(diǎn)；倍增是找到成倍數(shù)的數(shù)據(jù)規(guī)模之間的遞推公式，預(yù)處理數(shù)據(jù)范圍內(nèi)所有成倍情況，再將原數(shù)據(jù)范圍分解成我們已經(jīng)算過(guò)的這幾倍的情況，再進(jìn)行合的處理。重點(diǎn)在于尋找遞推公式和高效地合。那么，這有什么用呢？單獨(dú)的倍增算法往往費(fèi)力討好，又難想到又難理解，例如剛才的麥森數(shù)，相信大神們有n!種方法鞭尸，也許只要三四十行，甚至復(fù)雜度還更低。但是在某些題目里可以打出神助攻，比如，rmq。rmq算法用處：求任意區(qū)間內(nèi)最值。復(fù)雜度：O(nlogn)預(yù)處理，O(1)查找。基本思想：剛剛一維最近點(diǎn)對(duì)講過(guò)，區(qū)間[l,r]的最值為區(qū)間[l,m]的最值和區(qū)間[m,r]最值中更優(yōu)的那一個(gè)。當(dāng)m=(l+r)/2時(shí)，顯然可以用倍增算出從l點(diǎn)開(kāi)始2、4、8…長(zhǎng)度的最值，再將l、r這一段區(qū)間分解成若干長(zhǎng)度為2^ai的幾段，求這幾段的最值。細(xì)心的人會(huì)發(fā)現(xiàn)，這個(gè)查找并不是O(1)，且當(dāng)長(zhǎng)度類(lèi)似于麥森數(shù)時(shí)，這個(gè)倍增比O(1)高了很多，到了O(logn)。有什么好辦法呢？（大神禁言）我們可以巧妙地轉(zhuǎn)化一下：創(chuàng)造性地違背分治原則，分成兩個(gè)有公共部分的區(qū)間，分別是[l,l+2^k]、[r-2^k,r]，其中k=max(2^k<r-l)。如此一來(lái)直接從rmq記錄的數(shù)組中查找相應(yīng)最值進(jìn)行比較就行了。有了rmq，我們就可以做lca了！這個(gè)留作思考。后綴數(shù)組(suffixarray)后綴、字符串大小比較，這幾個(gè)概念就不用講了吧？那么后綴數(shù)組是什么呢？這可以理解為一個(gè)排好序的數(shù)組，滿足以這些數(shù)的位置為開(kāi)始的字符串S的后綴具有單調(diào)性（一般是遞增）。即：設(shè)字符串類(lèi)型函數(shù)suffix(i)表示從第i位開(kāi)始的后綴(首字母為第一位)，例如對(duì)于”watchdog”，suffix(6)=“dog”；對(duì)于”GTAsa”，suffix(4)=“sa”，等等。后綴數(shù)組sa,滿足：對(duì)于任意1≤i<j≤strlen(S)，都有suffix(sa[i])<suffix(sa[j]).就像GTAsa中主角會(huì)有一個(gè)好朋(ji)友，sa數(shù)組也和另一個(gè)數(shù)組rank打配合。Rank滿足：rank[sa[i]]=i.易證sa[rank[i]]=i.有了這兩個(gè)數(shù)組，我們就具有解決后綴數(shù)組問(wèn)題的基礎(chǔ)了。那么，如何構(gòu)造呢？看這PPT標(biāo)題就知道是用倍增了。用倍增，重在找成倍的規(guī)模的問(wèn)題之間的聯(lián)系。在字符串中，不難發(fā)現(xiàn)，如果把兩個(gè)長(zhǎng)度均為n的字符串a(chǎn)1、a2分別在后面加上另兩個(gè)長(zhǎng)度為n的字符串b1、b2，得到兩條長(zhǎng)度為2n的新字符串，這兩個(gè)字符串大小比較無(wú)需像常規(guī)比較一樣一個(gè)一個(gè)比，直接