acm入門分治貪心法

1、 ACM暑期訓練講座之分治法 主講人：nuanran自我介紹nuanran安彥東04級軟件一班 .cn參加了05和06的培訓，并最終參加了05年北京賽區(qū)和06年上海賽區(qū)的比賽分治法的基本思想分治法的設計思想是，將一個難以直接解決的大問題，分解成k個可解的子問題，并可利用這k個子問題的解求出原問題的解由分治法產(chǎn)生的子問題往往是原問題的較小規(guī)模，因此分治法常常用遞歸來實現(xiàn)分治法的基本步驟分治法在每一層遞歸上都有三個步驟：1. 分解：將原問題分解成若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題2. 解決：若子問題規(guī)模較小可以直接解決就直接解決，否則繼續(xù)遞歸3. 合并：用各個子問題的解求出原問題的

2、解分治法一般的算法設計模式DivideAndConquer( p ) if ( |p| n0) then return（直接計算的結果）;將p分成p1,p2,pk若干子問題;for(i=1;i=k;i+) yi = DivideAndConquer(pi); T = 合并（y1,y2,yk); return T;分治法大量的實踐證明，在分治法中，將原問題分解成若干相同子問題的時候，子問題的大小越接近，算法的效率就越高很多時候，都是把原問題分解成兩個相等的子問題合并是一個分治算法設計的關鍵所在，通常合并的復雜度要控制在O(n)以內，這樣算法的整體復雜度才能控制在O(nlogn).典型問題一：歸并

3、排序給定n個無序的數(shù)，要求將這n個數(shù)從小到大排列算法思想分解：將n個數(shù)平均分成A和B兩組，其中A集合中包含n/2個數(shù)，B集合包含其余的數(shù)解決：如果n小于2,則無需排序；否則繼續(xù)遞歸合并：設i,j分別為數(shù)組A,B的下標指針，開始時i=j=1,比較Ai和Bj的大小，取出較小者，放入結果數(shù)組，并將相應的指針加1.重復上述步驟直至A或B為空，然后將不為空的數(shù)組中其余的數(shù)加在所得結果數(shù)組的后面，就得到所需要的序列歸并排序舉例考慮6個元素，值分別為:5,3,7,6,10,9歸并排序模板#define MAXN 100000int aMAXN;int bMAXN;void mergeSort(int lef

4、t,int right) if(leftright) int mid=(left+right)/2; mergeSort(left,mid); mergeSort(mid+1,right); merge(left,mid,right); mergeSort(0,n-1);歸并排序模板void merge(int left,int mid,int right) int i=left,j=mid+1,k=left; while(i=mid&j=right) if(ajai) bk+=aj; j+; else bk+=ai; i+; while(i=mid) bk+=ai; i+; while(j=

5、right) bk+=aj; j+; for(i=left;iX其中f(1)=a1,f(2)=a2,f(n)=an Cipher一個置換一般用一個2*n的陣列表示： 例：1,2,3的6個置換如下： Cipher置換的合成運算：如果和是1,2,n上的兩個置換，按先f后g的順序進行合成，則得置換其中Cipher例如：則 (g.f)(1)=3,(g.f)(2)=4, (g.f)(3)=1,(g.f)(4)=2因此類似可得 Cipher置換的合成運算滿足結合律，即： (f.g).h=f.(g.h)現(xiàn)在讓我們回到原題，我們可以把密碼看成是一個置換，對原信息進行k次操作與對密碼進行k-1次合成運算后，再進行一次操作是等效的由于置換的合成運算滿足結合律，我們完全可以用類似an問題的解法對k-1次合成運算使用分治法，從而使復雜度由O(n)降到O(logn).經(jīng)典問題三：最近點對問題給出平面上n個點的坐標，求在任意兩點之間的距離中最近的距離是多少練習題五(選做)：Quoit Design(ZOJ2107).可以參考：data