國家集訓隊作業(yè)奶牛圍欄解題報告

1、解題廣西柳鐵一中一、問題概括現(xiàn)有若干種木枓，長度均不超過 3000 且都是整數。木料的數量沒有限制，求用這些木料不能拼接成的最大長度；若此最大長度不存在，則輸出1。二、樸素的（算法一）要想求出不能得到的最大長度，首先要判斷某一個長度是否能得到。定義函數 F(L)，表示長度 L 是否能用現(xiàn)有的木料拼接成，有：F(L) = F(L) or ( F(k) and F(L-k) )顯然，F(xiàn)(L) 決定于 F(1)、F(2)、F(L-1)。(1kL-1)而且，僅當 F(k)=false 時，F(xiàn)(2k-1)、F(2k)、F(2k+1) 的值才可能為 false。于是以此為突破口，以當前推導出的 F(k)=

2、false 為基礎， 進一步判斷 F(2k-1)、F(2k)、F(2k+1)的值。若有為 false 的，具體處理中，可按區(qū)間形式速度。下來，作為以后推導的基礎，直至找到最大值。函數值為 false 的長度，以減小空間，并加快處理由于長度沒有上界，這種算法的時空復雜度都難以估計；而且部分無解情況無法判出，并不理想。但就本題的數據而言，絕大部分都是可以滿足要求的。三、數學的(算法二)倘若試圖運用數學知識解決此題，不難得到第一個有利結論：若現(xiàn)有木料長度的最大公約數不為 1，則無解。(證明略)通過對算法一的分析，可知本題難點在于，長度沒有上限，可無窮以處理。那么是不是可以把長度分為幾大類，再進行處理

3、？于是想到利用“剩余類”解決此題。設 P 為一常數：若 F(ap+r)=true則有 F(b*(ap+r)=true，其中 b1, a、b、p、rZ。定義：H(r)=minap+r,F(ap+r)=true表示除以 P 余數為 r 的這類長度中，能得到的最小長度。用現(xiàn)有長度對函數 H 進行初始化后，再采用類似最短路的方法，求出 h 的終值。H(r)= min H(r), H(i)+Length(j)(0=r,i=P-1, r i , (H(i)+Length(j) mod P=r ,Length(j)為某一現(xiàn)有長度)最后，若存在 H(r)=,表示這類長度均不能得到，無解；否則，result=m

4、inH(r)-P,0rP-1 且 H(r)P。另外，常數P 的設定，當然越小越好，可以賦為現(xiàn)有木料長度的最小值。該算法的性能：空間復雜度 O(n)； 時間復雜度：O(n2)。四、總結顯然，兩種算法性能的差異很大。而其差別就在于是否運用了數學知識，可見扎實的數學基礎能促使解題的飛躍。五、實現(xiàn)(算法一Const maxmax_abfence1.pas)=3000;=30000;filenameoutname=fence.in;=fence.out;Var a,bl w tmax_l，o，p，q n,mresult:array1.max_ab of long; 不能得到的長度區(qū)間; 現(xiàn)有長度:arr

5、ay1.maxof:long;w為當前要判斷得長度t為當前得到的區(qū)間數:eger; eger;eger;:long;procedure pr;var fbegin:text;assign(f,outname);rewrite(f);wrin(f,result);close(f);end;procedure add;var rbegin:;if w0) or (q0) and (bp=o-1) then beginr:=true;if apo then o:=ap; dec(p);end;(q=o-1) then beginr:=true;if w-bqo then o:=w-bq; inc(q

6、);end;ifend;if obt+1 thenbegininc(t);at:=w; end;bt:=w;end;end;Procedure main; Var i,j :long;Begini:=0;RepeatInc(i);枚舉到第i個區(qū)間w:=ai-1+ai; p:=i-1; q:=i+1; o:=w-bi;Add; j:=0;RepeatInc(j);判斷長度w是否能得到，不能則加入區(qū)間Inc(w); p:=i-1; q:=i+1;If aiw-bi then o:=aielseo:=w-bi;Add;同上Inc(w); p:=i-1; q:=i+1;If aibt+1) begin

7、inc(t); at:=i; end;bt:=i;end;thenend;function judge:var k,i,j,r:eger; begin;for k:=1 to max_l doif lk for i:=k+1 if libeginthen break;to max_l do thenr:=i mod k; while r0 dobeginj:=k;k:=r;r:=j mod k; end;if k=1 then break; end;if k=1 then judge:=trueelse judge:=false;end;procedure init;var i,j,k:ege

8、r;fbegin:text;assign(f,filename); reset(f); readln(f,n,m);fillchar(l,sizeof(l),false); max_l:=0;for i:=1 to n do beginreadln(f,j);if jmax_l then max_l:=j;for k:=0 to m doif k0 then main;PrEnd.;六、實現(xiàn)(算法二,fence2.pas)const filenameoutname max=fence.in;=fence.out;=3000;Var l min lenresult t,n,mw:array0.m

9、ax:array0.max:array1.maxof ofof;對應的min是否達到最小值各類長度能得到的最小值現(xiàn)有的木料長度longeger;:：eger; eger;eger； 設定剩余類procedure pr;var fbegin:text;assign(f,outname);rewrite(f);wrin(f,result);close(f);end;Procedure Var i,j,k oBeginmain;:eger;Fillchar(l,sizeof(l),true); i:=0;Repeatli:=false;For k:=1 to t doBeginj:=(mini+le

10、nk) mod w;If minjmini+lenk then 更新minj minj:=mini+lenk;End; i:=-1;For k:=1 to w-1 doIf lk and (i=-1) or (minkresultresult:=mini-w;then break elsethen無解If result=0 then result:=-1;End;procedure ready;var ibegin:eger;w:=len1;for i:=0 to w-1 do mini:=maxlongfor i:=1 to t do;if minleniminlenimod wleni t

11、henmod w:=leni;end;function judge:;var k,i,j,r:begineger;k:=len1;for i:=2 to t do beginr:=leni mod k; while r0 dobeginj:=k;k:=r;r:=j mod k; end;if k=1 then break;end;if k=1 then judge:=trueelse judge:=false;end;procedure init;var f:text;i,j,k:begineger;assign(f,filename); reset(f); readln(f,n,m);fillchar(l,sizeof(l),false); for i:=1 to n dobeginreadln(f,j);for k:=0 to m if kj the