NOIP基礎(chǔ)算之分治

分治策略一、分治思想分治法，又叫分治策略，顧名思義，分而治之。它的基本思想為：對于難以直接解決的規(guī)模較大的問題，把它分解成若干個(gè)能直接解決的相互獨(dú)立的子問題，遞歸求出各子問題的解，再合并子問題的解，得到原問題的解。通過減少問題的規(guī)模，逐步求解，能夠明顯降低解決問題的復(fù)雜度。二、分治法的適用條件能使用分治法解決的問題，它們一般具備以下幾個(gè)特征：①該問題可以分解成若干相互獨(dú)立、規(guī)模較小的相同子問題；②子問題縮小到一定的程度能輕易得到解；③子問題的解合并后，能得到原問題的解；分治法在信息學(xué)競賽中應(yīng)用非常廣泛，使用分治策略能生成一些常用的算法和數(shù)據(jù)結(jié)構(gòu)，如快排、最優(yōu)二叉樹、線段樹等；還可以直接使用分治策略，解決一些規(guī)模很大、無法直接下手的問題。三、分治的三步驟①分解：將要解決的問題分解成若干個(gè)規(guī)模較小的同類子問題；②解決：當(dāng)子問題劃分得足夠小時(shí)，求解出子問題的解。③合并：將子問題的解逐層合并成原問題的解。分治算法設(shè)計(jì)過程圖分治思想由分治法所得到的子問題與原問題具有相同的類型。如果得到的子問題相對來說還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出不用進(jìn)一步細(xì)分就可求解的子問題。分治求解可用一個(gè)遞歸過程來表示。要使分治算法效率高，關(guān)鍵在于如何分割？一般地，出于一種平衡原則，總是把大問題分成個(gè)規(guī)模盡可能相等的子問題，但也有例外，如求表的最大最小元問題的算法，當(dāng)n＝6時(shí)，等分定量成兩個(gè)規(guī)模為3的子表L1和L2不是最佳分割。一般來講，都是2分為主。四、分治的框架結(jié)構(gòu)if問題不可分{直接求解；返回問題的解；}else{對原問題進(jìn)行分治；遞歸對每一個(gè)分治的部分求解;歸并整個(gè)問題，得出全問題的解；}五、分治的典型應(yīng)用1、求最大值和最小值2、非線性方程求根3、二分查找4、歸并排序5、快速冪6、求解線性遞推關(guān)系7、棋盤覆蓋問題8、循環(huán)日程表問題9、尋找最近點(diǎn)對1、求最大值和最小值例題1：給n個(gè)實(shí)數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。分析：假設(shè)數(shù)據(jù)個(gè)數(shù)為n,存放在數(shù)組a;ma=a>mama=a<minnminn=a;使用這一算法，比較次數(shù)為2n-1。若n=10,則比較18次。用分治法解決這個(gè)問題就是把集合a分成a1,a2兩個(gè)子集，每個(gè)子集有n/2個(gè)元素，應(yīng)用遞歸結(jié)構(gòu)找出兩個(gè)子集的最大元和最小元，比較得到的兩個(gè)最大元和最小元即可得到整個(gè)集合a中的最大元和最小元。劃分：把n個(gè)數(shù)均分為兩半。即：劃分點(diǎn)為d=r1r2/2，兩個(gè)區(qū)間為。遞歸求解：求左半的最小值min1和最大值ma1以及右半最小值min2和最大值ma2。合并：所有數(shù)的最大值為ma，最小值為minn。核心代碼voida,int&minn{intma1,min1,ma2,min2,d;ifr1==r2{ma=minn=;}elseifr2==r11{if;minn=;minn=;}}else{d=r1r2/2;a1,min1;a2,min2;ifma1>ma2ma=ma1;elsema=ma2;ifmin1<min2minn=min1;elseminn=min2;}}【思考試題】最大值最小化【問題描述】把一個(gè)包含n個(gè)正整數(shù)的序列劃分成m個(gè)連續(xù)的子序列每個(gè)正整數(shù)恰好屬于一個(gè)序列。設(shè)第i個(gè)序列的各數(shù)之和為Si，你的任務(wù)是讓所有的Si的最大值盡量小。例如序列123254劃分成3個(gè)序列的最優(yōu)方案為123|25|4，其中S1=6，S2=7，S3=4，最大值為7；如果劃分成12|32|54，則最大值為9；不如剛才的好。n<=10^6，所有數(shù)字之和不超過10^9。2、非線性方程求根【例題2】一元三次方程的解【題目描述】有形如：a3b2cd=0這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)a,b,c,d均為實(shí)數(shù)，并約定該方程存在三個(gè)不同實(shí)根根的范圍在-100至100之間，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根根與根之間留有空格，并精確到小數(shù)點(diǎn)后4位?！疚募斎搿枯斎雰H一行，有四個(gè)數(shù)，依次為a、b、c、d【文件輸出】輸出也只有一行，即三個(gè)根從小到大輸出【樣例輸入】1-5-420【樣例輸入】-200200500分析如果精確到小數(shù)點(diǎn)后兩位，可用簡單枚舉法：將從-10000到10000（步長001）逐一枚舉，得到20000個(gè)f，取其值與0最接近的三個(gè)f，對應(yīng)的即為答案。而題目已改成精度為小數(shù)點(diǎn)后4位，枚舉算法時(shí)間復(fù)雜度將達(dá)不到要求。直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值分析A當(dāng)已知區(qū)間a,b內(nèi)有一個(gè)根時(shí)；用二分法求根，若區(qū)間a,b內(nèi)有根，則必有fa*fb<0。重復(fù)執(zhí)行如下的過程：1若a00001>b或fab/2=0，則可確定根為ab/2并退出過程；2若fa*fab/2<0,則由題目給出的定理可知根在區(qū)間a,ab/2中,故對區(qū)間重復(fù)該過程；3若fa*fab/2>0,則必然有fab/2*fb<0,根在ab/2,b中,對此區(qū)間重復(fù)該過程。執(zhí)行完畢,就可以得到精確到00001的根。分析B、求方程的所有三個(gè)實(shí)根所有的根的范圍都在-100至100之間，且根與根之差的絕對值>=1。因此可知：在、這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能有一個(gè)根。即：除區(qū)間，只有當(dāng)fa=0或fa·fa1<0時(shí)，方程在此區(qū)間內(nèi)才有解。若fa=0，解即為a；若fa·fa1<0，則可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。核心參考代碼voiddividedouble1,double2{double0,y0,y1,y2;0=12/2;y1=cal1;y2=cal2;y0=cal0;if2-1<000001&&y1*y2<0{printf"%4f",21/2;return;}ify1*y0<0||0-1>1divide1,0;ify0*y2<0||2-0>1divide0,2;}3、歸并排序歸并排序的基本思想：歸并排序充分應(yīng)用分治算法的策略，將n個(gè)數(shù)分成n個(gè)單獨(dú)的有序數(shù)列，每個(gè)數(shù)列中僅有一個(gè)數(shù)字；再將相鄰的兩列數(shù)據(jù)合并成一個(gè)有序數(shù)列，每個(gè)數(shù)列中有2個(gè)數(shù)；再重復(fù)上面的合并操作，直到合成一個(gè)有序數(shù)列。按照分治三步法來說，歸并過程為：（1）劃分：把序列分成元素個(gè)數(shù)相等的兩半；（2）遞歸求解：把兩半分別排序；（3）合并：把兩個(gè)有序表合成一個(gè)；分析顯然，前兩部分是很容易完成的，關(guān)鍵在于如何把兩個(gè)有序表合成一個(gè)。每次只需要把兩個(gè)序列中當(dāng)前的最小元素加以比較，刪除較小元素并加入合并后的新表。核心參考代碼intteman];//輔助空間voidMergeSortintleft,intright//對區(qū)間left---right進(jìn)行歸并排序{ifleft==rightreturn;//只有一個(gè)元素mid=leftright/2;//找中間位MergeSortleft,mid;//對左邊歸并MergeSortmid1,right;//對右邊歸并i=left,j=mid1,id&&j<=rightifa;}【變形1】逆序?qū)?shù)目例題：求“逆序?qū)Α?。給定一整數(shù)數(shù)組A=A1,A2,…An,若i<j且Ai>Aj,則<i,j>就為一個(gè)逆序?qū)Α＠鐢?shù)組（3，1，4，5，2）的逆序?qū)τ?lt;3,1>,<3,2>,<4,2>,<5,2>。問題是，輸入n和A數(shù)組，統(tǒng)計(jì)逆序?qū)?shù)目。數(shù)據(jù)范圍：1<=n<=30000。樸素算法原始的解決方案（雙重循環(huán)）C:=0;Fori:=1ton-1doforj:=i1tondoifathenc:=c1;時(shí)間復(fù)雜度為On2分治算法：采用二分法求解:記數(shù)列a的逆序?qū)?shù)目為Dst,ed;

mid=,則有：Dst,ed=Dst,midDmid1,edF,ed其中Fst,mid,ed表示一個(gè)數(shù)取自A的逆序?qū)?shù)目。和歸并排序一樣，劃分和遞歸求解都好辦，關(guān)鍵在于合并：如何求出i在左邊，而j在右邊的逆序?qū)?shù)目呢？統(tǒng)計(jì)的常見技巧是“分類”。我們按照j的不同把這些“跨越兩邊”的逆序?qū)M(jìn)行分類：只要對于右邊的每個(gè)j，統(tǒng)計(jì)左邊比它大的元素個(gè)數(shù)fj，則所有fj之和便是答案。幸運(yùn)的是，歸并排序可以幫助我們“順便”完成fj的計(jì)算：由于合并操作是從小到大進(jìn)行排序的，當(dāng)右邊的a復(fù)制到T中時(shí)，左邊還沒有來得及復(fù)制到T的那些數(shù)就是左邊所有比a大的數(shù)。此時(shí)累加器中加上左邊元素個(gè)數(shù)mid-i1即可。即把“ifa=a;}”。4、二分查找【問題描述】給出從小到大排列的n個(gè)不同數(shù)a，試判斷元素是否出現(xiàn)在表中。方法1：順序查找：方法是一個(gè)個(gè)尋找，時(shí)間復(fù)雜度為On。這個(gè)方法并沒有用到“n個(gè)數(shù)從小到大排列”這一個(gè)關(guān)鍵條件，因而時(shí)間效率低下。方法2：二分查找只需要比較log2n個(gè)元素。假設(shè)需要在aL<=m<=r，如果a>，那么元素只可能在a<，那么元素只可能在a中。合并：不需要合并。方法1：二分查找的遞歸實(shí)現(xiàn)intbsearchintL,intr,int{ifL>rreturn-1;intm=Lr/2;ifa>returnbsearchL,m-1,;elsereturnbsearchm1,r,;}方法2：二分查找的非遞歸實(shí)現(xiàn)：intbsearchintL,intr,int{intm;whileL<=r{m=Lr/2;ifa>r=m–1;elseL=m1;}return-1;//查找不成功}【擴(kuò)展1】二分查找求下界，即第一次出現(xiàn)的位置intErfenintL,intr,int{intmid;whileL<r{mid=Lr/2;if<=ar=mid;elseL=mid1;}returnL;}【擴(kuò)展2】二分查找求上界，即最后一次出現(xiàn)位置的后一個(gè)位置【思考題目】給出n個(gè)整數(shù)和m個(gè)詢問，對于每個(gè)詢問a,b，輸出閉區(qū)間內(nèi)的整數(shù)c的個(gè)數(shù)?！舅悸伏c(diǎn)撥】①先把所有的數(shù)據(jù)從小到大排序；②二分查找求下界，即第一次出現(xiàn)的位置low；③二分查找求上界，即最后一次出現(xiàn)位置的后一個(gè)位置high；④答案區(qū)間為：ans=high-low【變形1】查找等值點(diǎn)【問題描述】n個(gè)不同整數(shù)從小到大排序后放在數(shù)組A0~An-1中，是否存在i，使得Ai=i？若存在，試找到此點(diǎn)。5、快速冪【問題描述】計(jì)算an%，n<=109。方法1：樸素算法。每次乘以a，時(shí)間復(fù)雜度On。intpowerinta,intn{int=1;fori=1;i<=n;i*=a;return;}方法2：分治算法劃分：如果n是偶數(shù)，考慮=n/2，否則考慮=n-1/2遞歸求解：計(jì)算a。合并：如果n是偶數(shù)，則an=a2，否則an=a2*a根據(jù)這個(gè)方法很容易寫出程序：intpowerinta,intn{ifn==0return1;elseifn%2==1{int=powera,n-1/2;return*%*a%;}else{int=powera,n/2;return*%;}}方法3：用二進(jìn)制實(shí)現(xiàn)快速冪計(jì)算cin>>b>>od{ans=ans*ans%;ifa==1ans=b%*ans%;//如果是奇數(shù)，就多乘b}cout<<ans<<endl;//輸出b^od6、求解線性遞推關(guān)系【例題】Fibonacci數(shù)【題目描述】Fibonacci數(shù)列定義為：f=1,f=1?，F(xiàn)在請你求Fibonacci數(shù)列的第n項(xiàng)?！疚募斎搿枯斎胛募挥幸恍袨橐粋€(gè)整數(shù)n1<=n<=2^31-1。【文件輸出】輸出文件只有一行為一個(gè)整數(shù)，表示Fibonacci數(shù)列的第n項(xiàng)mod32768的值。【樣例輸入】4【樣例輸出】3【數(shù)據(jù)范圍】對于20%的數(shù)據(jù)，1<=n<=1000對于40%的數(shù)據(jù)，1<=n<=10000000對于100%的數(shù)據(jù)，1<=n<=2^31-1分析枚舉，肯定超時(shí)voidprecalc_fibintn{f=1;forinti=2;i<=n;if;}先復(fù)習(xí)矩陣乘法?兩個(gè)2*2矩陣相乘的公式為?可用倍增法在Ologn時(shí)間內(nèi)求出冪忽略高精度一般情形7、棋盤覆蓋問題分析8、循環(huán)日程表問題【例題】比賽安排【問題描述】設(shè)有2nn<=6個(gè)球隊(duì)進(jìn)行單循環(huán)比賽,計(jì)劃在2n-1天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場比賽。設(shè)計(jì)一個(gè)比賽的安排，使在2n-1天內(nèi)每個(gè)隊(duì)都與不同的對手比賽。例如n=2時(shí)的比賽安排為：

隊(duì)1234

比賽1-23-4第一天

1-32-4第二天

1-42-3第三天【文件輸入】一個(gè)整數(shù)n?！疚募敵觥枯敵霰荣惏才疟??！緲永斎搿?【樣例輸出】1-23-4

1-32-4

1-42-3初看此題，感覺無法下手，因?yàn)闆]有任何直接可用的算法和數(shù)據(jù)結(jié)構(gòu)。仔細(xì)分析，可以發(fā)現(xiàn)，將問題進(jìn)