1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)NOIP復(fù)賽復(fù)習(xí)14尺取法與折半枚舉一、尺取法尺取法：顧名思義，像尺子一樣取一段，借用挑戰(zhàn)書(shū)上面的話說(shuō)，尺取法通常是對(duì)數(shù)組保存一對(duì)下標(biāo)，即所選取的區(qū)間的左右端點(diǎn)，然后根據(jù)實(shí)際情況不斷地推進(jìn)區(qū)間左右端點(diǎn)以得出答案。之所以需要掌握這個(gè)技巧，是因?yàn)槌呷》ū戎苯颖┝γ杜e區(qū)間效率高很多，尤其是數(shù)據(jù)量大的時(shí)候，所以尺取法是一種高效的枚舉區(qū)間的方法，一般用于求取有一定限制的區(qū)間個(gè)數(shù)或最短的區(qū)間等等。當(dāng)然任何技巧都存在其不足的地方，有些情況下尺取法不可行，無(wú)法得出正確答案。使用尺取法時(shí)

2、應(yīng)清楚以下四點(diǎn)：1、什么情況下能使用尺取法?2、何時(shí)推進(jìn)區(qū)間的端點(diǎn)？3、如何推進(jìn)區(qū)間的端點(diǎn)？4、何時(shí)結(jié)束區(qū)間的枚舉？尺取法通常適用于選取區(qū)間有一定規(guī)律，或者說(shuō)所選取的區(qū)間有一定的變化趨勢(shì)的情況，通俗地說(shuō)，在對(duì)所選取區(qū)間進(jìn)行判斷之后，我們可以明確如何進(jìn)一步有方向地推進(jìn)區(qū)間端點(diǎn)以求解滿足條件的區(qū)間，如果已經(jīng)判斷了目前所選取的區(qū)間，但卻無(wú)法確定所要求解的區(qū)間如何進(jìn)一步得到根據(jù)其端點(diǎn)得到，那么尺取法便是不可行的。首先，明確題目所需要求解的量之后，區(qū)間左右端點(diǎn)一般從最整個(gè)數(shù)組的起點(diǎn)開(kāi)始，之后判斷區(qū)間是否符合條件在根據(jù)實(shí)際情況變化區(qū)間的端點(diǎn)求解答案。POJ 3061給定長(zhǎng)度為n的數(shù)列整數(shù)a0,a1,an-

3、1以及證書(shū)S。求出總和不小于S的連續(xù)子序列的長(zhǎng)度的最小值。如果解不存在在，則輸出0.已知：10n1050ai104S108sampleinputn= 10S= 15a= 5,1,3,5,10,7,4,9,2,8sampleoutput2(5 + 10)我們?cè)O(shè)以as開(kāi)始總和最初大于S時(shí)的連續(xù)子序列as+.+at1,這時(shí)as+1+.+at2as+.+at2S所以從as+1開(kāi)始總和最初超過(guò)S的連續(xù)子序列如果是as+1+.+at1的話，則必然有tt。用下面的圖來(lái)解釋比較清晰：#include#include#include#include#define sf scanf#define pf print

4、fusing name space std;const int Maxn = ;int T,n,s;int sumMaxn;int main() int a; sf(%d,&T); while(T-) int tail = -1,head = -1; sf(%d%d,&n,&s); for(int i = 0;i = s) tail = i; if(tail = -1) pf(0n); continue; int Min = n; while(head =s) head +; Min = min(Min,tail - head); else if(tail n - 1) tail+; else

5、 break; pf(%dn,Min); return 0;POJ 3320題意：一本書(shū)有P頁(yè)，每一頁(yè)都一個(gè)知識(shí)點(diǎn)，求去最少的連續(xù)頁(yè)數(shù)覆蓋所有的知識(shí)點(diǎn)。分析：和上面的題一樣的思路，如果一個(gè)區(qū)間的子區(qū)間滿足條件，那么在區(qū)間推進(jìn)到該處時(shí)，右端點(diǎn)會(huì)固定，左端點(diǎn)會(huì)向右移動(dòng)到其子區(qū)間，且其子區(qū)間會(huì)是更短的，只是需要存儲(chǔ)所選取的區(qū)間的知識(shí)點(diǎn)的數(shù)量，那么使用map進(jìn)行映射以快速判斷是否所選取的頁(yè)數(shù)是否覆蓋了所有的知識(shí)點(diǎn)。#include#include#include#include#include#define MAX #define LL long long#define INF 0 x3f3f3f3f

6、using name space std;int aMAX;map cnt;set t;int p, ans = INF, st, en, sum;int main() scanf(%d, &p); for (int i = 0; i p; i+)scanf(%d, a+i), t.insert(ai); int num = t.size(); while (1) while (enp &sumnum) if (cntaen+ = 0)sum+; if (sum num) break; ans = min(ans, en-st); if (-cntast+ = 0) sum-; printf(

7、%dn, ans); return 0;POJ 2566題意：給定一個(gè)數(shù)組和一個(gè)值t，求一個(gè)子區(qū)間使得其和的絕對(duì)值與t的差值最小，如果存在多個(gè)，任意解都可行。分析：明顯，借用第一題的思路，既然要找到一個(gè)子區(qū)間使得和最接近t的話，那么不斷地找比當(dāng)前區(qū)間的和更大的區(qū)間，如果區(qū)間和已經(jīng)大于等于t了，那么不需要在去找更大的區(qū)間了，因?yàn)槠浜团ct的差值更大，然后區(qū)間左端點(diǎn)向右移動(dòng)推進(jìn)即可。所以，首先根據(jù)計(jì)算出所有的區(qū)間和，排序之后按照上面的思路求解即可。#include#include#include#define INF 0 x3f3f3f3f#define LL long long#define MA

8、X using name space std;typedef pair p;LL aMAX, t, ans, tmp, b;int n, k, l, u, st, en;p sumMAX;LL myabs(LL x) return x=0? x:-x;int main() while (scanf(%d %d, &n,&k), n+k) sum0 = p(0, 0); for (int i = 1; i = n; i+) scanf(%I64d, a+i); sumi = p(sumi-1.first+ai,i); sort(sum, sum+1+n); while (k-) scanf(%I

9、64d,&t); tmp = INF; st = 0, en = 1; while(en = n) b =sumen.first-sumst.first; if(myabs(t-b) t) st+; else if(b t) en+; else break; if(st = en) en+; if (u l) swap(u, l); printf(%I64d %d %dn,ans, l+1, u); return 0;總結(jié)：尺取法的模型便是這樣：根據(jù)區(qū)間的特征交替推進(jìn)左右端點(diǎn)求解問(wèn)題，其高效的原因在于避免了大量的無(wú)效枚舉，其區(qū)間枚舉都是根據(jù)區(qū)間特征有方向的枚舉，如果胡亂使用尺取法的話會(huì)使得枚舉

10、量減少，因而很大可能會(huì)錯(cuò)誤，所以關(guān)鍵的一步是進(jìn)行問(wèn)題的分析！二、折半枚舉折半枚舉不是一般的雙向搜索，當(dāng)問(wèn)題的規(guī)模較大，無(wú)法枚舉所有元素的組合，但能夠枚舉一半元素的組合，此時(shí)將問(wèn)題拆成兩半后分別枚舉，再合并它們的結(jié)果這一方法往往非常有效。POJ 2785給定各有n個(gè)整數(shù)的四個(gè)數(shù)列A,B,C,D。從每個(gè)數(shù)列中各取一個(gè)數(shù)，使四個(gè)數(shù)的和為0.當(dāng)一個(gè)數(shù)列中有多個(gè)相同數(shù)字時(shí)，把它們作為不同的數(shù)字看待。求出這樣的組合的個(gè)數(shù)。已知：1n4000|(數(shù)字的值)|228sampleinputn= 6A= -45,-41,-36,-36,26,-32B= 22,-27,53,30,-38,-54C= 42,56,-

11、37,-75,-10,-6D= -16,30,77,-46,62,45sampleoutput5如果全部枚舉，則有n4種可能性。時(shí)間復(fù)雜度通不過(guò)。因此可以進(jìn)行折半枚舉，計(jì)算A,B之間的組合，共有n2種情況，同樣的，C,D之間也有n2種情況。在取出A,B組合中的一組組合（a + b）時(shí)，為了使和為0，去查找C,D組合中滿足a + b+c+d = 0的組合（c+d），這個(gè)查找可以用二分查找來(lái)實(shí)現(xiàn)，因此最后的復(fù)雜度是O(n2logn)#include#include#include#include#include#include#define sf scanf#define pf printfusi

12、ng name space std;typedef long long LL;const int Maxn = 4010;int AMaxn,BMaxn,CMaxn,DMaxn;int ABMaxn * Maxn,CDMaxn * Maxn;int n;LL solved(int val) int l = 0, r = n * n - 1; LL ans; while(l = r) int mid = (l + r) / 2; if(CDmid = val) l = mid + 1; else r = mid - 1; ans = r; l = 0, r = n * n - 1; while(

13、l = r) int mid = (l + r) / 2; if(CDmid val) l = mid + 1; else r = mid - 1; ans = ans - r; return ans;int main() while(sf(%d,&n) for(int i = 0;i n;i+)sf(%d%d%d%d,&Ai,&Bi,&Ci,&Di); int cnt = 0; for(int i = 0;i n;i +) for(int j = 0;j n;j +) ABcnt = Ai + Bj,CDcnt+= Ci + Dj; sort(CD,CD + cnt); LL ans = 0

14、; for(int i = 0;i cnt;i +) ans += solved(0 - ABi); pf(%lldn,ans); return 0;POJ 3977題意：給你一個(gè)含n(n=35)個(gè)數(shù)的數(shù)組,讓你在數(shù)組中選出一個(gè)非空子集，使其元素和的絕對(duì)值最小，輸出子集元素的個(gè)數(shù)以及元素和的絕對(duì)值，若兩個(gè)子集元素和相等，輸出元素個(gè)數(shù)小的那個(gè)。思路：如果直接暴力枚舉，復(fù)雜度O(2n)，n為35時(shí)會(huì)超時(shí)，故可以考慮折半枚舉，利用二進(jìn)制將和以及元素個(gè)數(shù)存在兩個(gè)結(jié)構(gòu)體數(shù)組中，先預(yù)判兩個(gè)結(jié)構(gòu)體是否滿足題意，再將其中一個(gè)元素和取相反數(shù)后排序，因?yàn)榭傇睾驮浇咏阍胶?，再二分查找即可，用lower_boun

15、d時(shí)考慮查找到的下標(biāo)和他前一個(gè)下標(biāo)，比較元素和以及元素個(gè)數(shù)，不斷更新即可。#include#include#include#includeusing name space std;struct Zlong long int x;int y;bool operator (const Z& b)const if(x!=b.x) return x b.x; return yb.y; a,b;long long int c40;long long int abs1(long long int x)if(xn)&n!=0) for(int i=0;i;i+) ai.x=ai.y=bi.x=bi.y=0;

16、 long long int sum=1e17; int ans=40; for(int i=0;ici; int n1=n/2; for(int i=0;i1n1;i+) for(int j=0;jj&1&(i!=0|j!=0) ai-1.x+=cj; ai-1.y+; int n2=n-n1; for(int i=0;i(1n2);i+) for(int j=0;jj&1&(i!=0|j!=0) bi-1.x+=cj+n1; bi-1.y+; for(int i=0;i(1n1)-1;i+) if(abs1(ai.x)sum) sum=abs1(ai.x); ans=ai.y; elsei

17、f(abs1(ai.x)=sum&ai.yans) ans=ai.y; sum=abs1(ai.x); for(inti=0;i(1n1)-1;i+) ai.x=-ai.x; for(int i=0;i(1n2)-1;i+) if(abs1(bi.x)sum) sum=abs1(bi.x); ans=bi.y; else if(abs1(bi.x)=sum&bi.yans) ans=bi.y; sum=abs1(bi.x); sort(a,a+(1n1)-1); sort(b,b+(1n2)-1); for(int i=0;i(1n1)-1;i+) int t=lower_bound(b,b+(10) if(abs1(bt-1.x-ai.x)sum) sum=abs1(bt-1.x-ai.x