国家集训队作业奶牛围栏解题报告

1、解题广西柳铁一中一、问题概括现有若干种木枓，长度均不超过 3000 且都是整数。木料的数量没有限制，求用这些木料不能拼接成的最大长度；若此最大长度不存在，则输出1。二、朴素的（算法一）要想求出不能得到的最大长度，首先要判断某一个长度是否能得到。定义函数 F(L)，表示长度 L 是否能用现有的木料拼接成，有：F(L) = F(L) or ( F(k) and F(L-k) )显然，F(L) 决定于 F(1)、F(2)、F(L-1)。(1kL-1)而且，仅当 F(k)=false 时，F(2k-1)、F(2k)、F(2k+1) 的值才可能为 false。于是以此为突破口，以当前推导出的 F(k)=

2、false 为基础， 进一步判断 F(2k-1)、F(2k)、F(2k+1)的值。若有为 false 的，具体处理中，可按区间形式速度。下来，作为以后推导的基础，直至找到最大值。函数值为 false 的长度，以减小空间，并加快处理由于长度没有上界，这种算法的时空复杂度都难以估计；而且部分无解情况无法判出，并不理想。但就本题的数据而言，绝大部分都是可以满足要求的。三、数学的(算法二)倘若试图运用数学知识解决此题，不难得到第一个有利结论：若现有木料长度的最大公约数不为 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 的这类长度中，能得到的最小长度。用现有长度对函数 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)为某一现有长度)最后，若存在 H(r)=,表示这类长度均不能得到，无解；否则，result=m

4、inH(r)-P,0rP-1 且 H(r)P。另外，常数P 的设定，当然越小越好，可以赋为现有木料长度的最小值。该算法的性能：空间复杂度 O(n)； 时间复杂度：O(n2)。四、总结显然，两种算法性能的差异很大。而其差别就在于是否运用了数学知识，可见扎实的数学基础能促使解题的飞跃。五、实现(算法一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; 不能得到的长度区间; 现有长度:arr

5、ay1.maxof:long;w为当前要判断得长度t为当前得到的区间数: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个区间w:=ai-1+ai; p:=i-1; q:=i+1; o:=w-bi;Add; j:=0;RepeatInc(j);判断长度w是否能得到，不能则加入区间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.;六、实现(算法二,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是否达到最小值各类长度能得到的最小值现有的木料长度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