NOIP2008提高組前三題解題報(bào)告

1、NOIP2008提高組前三題解題報(bào)告日期：2008-11-18來源：  作者：張恩權(quán)字體：大 中 小 NOIP2008提高組前三題解題報(bào)告1.笨小猴基本的字符串處理，細(xì)心一點(diǎn)應(yīng)該沒問題的，不過判斷素?cái)?shù)時(shí)似乎需要考慮下0和1的情況。參考程序：program word;const inp='word.in' oup='word.out'var i,j,k,min,max:longint; s:string; ch:char; f:array'a'.'z' of integer;/記錄每個(gè)字符出現(xiàn)的次數(shù)procedure fl

2、ink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(output); end;function judge(k:longint):boolean;/判斷素?cái)?shù)，需考慮0和1的情況 var i:longint; begin if (k=0) or (k=1) then exit(false); for i:=2 to trunc(sqrt(k) do if k mod i = 0 then ex

3、it(false); exit(true); end;begin flink; readln(s); fillchar(f,sizeof(f),0); for i:= 1 to length(s) do /統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù) inc(fsi); min:=1000; max:=0; for ch:= 'a' to 'z' do/統(tǒng)計(jì)最大和最小 begin if ( fch<>0 ) and (fch>max) then max:=fch; if ( fch<>0 ) and (fch<min) then min:=fch;

4、 end; k:=max-min; if judge(k) then/輸出 begin writeln('Lucky Word'); write(k); end else begin writeln('No Answer'); write(0); end; fclose;end.2.火柴棒等式預(yù)處理下，然后枚舉、剪枝，范圍稍微開大點(diǎn)，弄到2000似乎足夠了，剪枝后不會(huì)超時(shí)的。首先預(yù)處理下每個(gè)數(shù)（02000）需要多少個(gè)火柴棒，然后枚舉A和B，再判斷。參考程序：program matches;const inp='matches.in' oup=&#

5、39;matches.out' num:array'0'.'9' of integer=(6,2,5,5,4,5,6,3,7,6);/09需要的火柴棒數(shù) maxn=1000;var f:array0.maxn*2 of longint; i,j,k,n,ans:longint; s:string;procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(inpu

6、t); close(output); end;procedure init;/預(yù)處理02000每個(gè)數(shù)需要的火柴棒數(shù) var i,j,k:longint; s:string; begin for i:= 0 to maxn*2 do begin str(i,s); fi:=0; for j:= 1 to length(s) do inc(fi,numsj); end; end; begin flink; readln(n); init; ans:=0; n:=n-4;/總火柴棒數(shù)減去'+'和'='所需的火柴棒數(shù) for i:= 0 to maxn do/枚舉A b

7、egin if fi>=n then continue;/剪枝 for j:= 0 to maxn do/枚舉B begin if fi+fj>=n then continue;/剪枝 k:=i+j; if fi+fj+fk=n then inc(ans);/符合條件,總數(shù)加一 end; end; write(ans); fclose;end.3.傳紙條從A傳給B，再從B傳給A，中間路徑不相交與某個(gè)人。換種思路，它完全等價(jià)于，從A點(diǎn)傳出2張紙條到B，中間不能經(jīng)過同一人。這么看來似乎就是vijos三取方格數(shù)的簡化版了。解題思想就是雙進(jìn)程的動(dòng)態(tài)規(guī)劃。階段是按傳遞次數(shù)劃分的。F(d,x1

8、,y1,x2,y2）表示第d次傳遞到坐標(biāo)為（x1，y1），（x2，y2）兩個(gè)人手中是得到的最大好心度。那么可以列出方程：F(d,x1,y1,x2,y2)=max f (d-1,x1',y1',x2',y2' )+ax1,y1+ax2,y2 | (x1',y1')為把紙條(x1,y1)的人，（x2' , y2'）為把紙條轉(zhuǎn)給(x2,y2)的人（數(shù)學(xué)不太好，方程列的不專業(yè)，見諒_）這么看來時(shí)間復(fù)雜度是O（maxd*n*m*n*m）,其中maxd=n+m-2。相當(dāng)于505=312500000，超時(shí)是沒得說的了。其實(shí)我們可以把狀態(tài)再壓縮下

9、，先來看下其中的規(guī)律：起點(diǎn) （1，1）第1次傳遞可到達(dá) （1，2）（2，1）第2次傳遞可到達(dá) （1，3）（2，2）（3，1）很快就可以發(fā)展其中的規(guī)律第d次傳遞可到達(dá)的坐標(biāo)(xi,yi)和d之間存在d+2=xi+yi那么我們就可以把上面的狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)化成f(d,x1,x2)=max f(d-1,x1' ,x2' ) +ax1, (d+2-x1) + ax2, (d+2-x2) | x1' , x2' 合法 參考程序：program message;const inp='message.in' oup='message.out'va

10、r a:array1.50,1.50 of longint; f:array0.200,1.100,1.100 of longint; tmp,i,j,k,n,m,d,x1,x2,y1,y2:longint;procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(output); end;function max(a,b:longint):longint; begin i

11、f a>b then exit(a); exit(b); end;begin flink; readln(n,m); for i:= 1 to n do begin for j:= 1 to m do read(ai,j); readln; end; fillchar(f,sizeof(f),0); f0,1,1:=a1,1; f1,1,2:=a2,1+a1,2; f1,2,1:=a1,2+a2,1; /邊界，因?yàn)橹虚g需要判斷點(diǎn)不重合，所以把必須重合的狀態(tài)單獨(dú)考慮 for d:= 2 to (n+m-3) do for x1:= 1 to n do begin y1:=(d+2)-x1;

12、 if (y1<=0) or (y1>m) then continue; / 排除不合法的x1 for x2:= 1 to n do begin if x1=x2 then continue;/排除不合法的x1,x2 y2:=(d+2) - x2; if (y2<=0) or (y2>m) then continue; / 排除不合法的x2 tmp:=fd-1,x1,x2; /各自從上方取,即從(x1,y1-1)傳到（x1,y1),（x2,y2-1)傳到(x2,y2) if (x1-1>0) and (x2-1>0) then tmp:=max(tmp,fd

13、-1,x1-1,x2-1); /從(x1-1,y1) 傳到（x1,y1),（x2-1,y2)傳到(x2,y2) if (x1-1>0) and (x1-1<>x2) then tmp:=max(tmp,fd-1,x1-1,x2); /從(x1-1,y1) 傳到（x1,y1),（x2,y2-1)傳到(x2,y2) if (x2-1>0) and (x1<>x2-1) then tmp:=max(tmp,fd-1,x1,x2-1); /從(x1,y1-1) 傳到（x1,y1),（x2-1,y2)傳到(x2,y2) fd,x1,x2:=tmp+ax1,y1+ax2

14、,y2; end; end; write(fn+m-3,n,n-1); / 終點(diǎn)的只可能從兩個(gè)點(diǎn)來，所以終點(diǎn)狀態(tài)前移一個(gè)階段。 fclose;end.4.雙棧排序難，寫不出滿分程序，所以還是不寫了NOIP2008提高組復(fù)賽 解題思路1、字符串中統(tǒng)計(jì)字母出現(xiàn)次數(shù) 最大減最小的 然后判斷質(zhì)數(shù) 字符串長度<=1002、給出n<=24個(gè)火柴棍，求最多能擺出多少a+b=c形式的等式。數(shù)字的擺法和計(jì)算器相同，a,b,c>=03、雙進(jìn)程方格取數(shù)：m*n的棋盤，m,n<=50，不需使用高精度4、給出1.n的排列，兩個(gè)棧S1、S2，入棧出棧共4個(gè)操作：（n<=1000） 

15、   A：輸入隊(duì)列頭入S1    B：彈出S1棧頂元素，進(jìn)入輸出隊(duì)列    C：輸入隊(duì)列頭入S2    D：彈出S2棧頂元素，進(jìn)入輸出隊(duì)列    要求將1.n的排列排序，采用字典序最小的操作方法個(gè)人感覺是，單就難度來看，奧賽歷史最簡單，由于類似2，3題的模型大多數(shù)能拿一等的同學(xué)們都見過。我的想法：1、水題，最多40分鐘搞定2、如果是考試的話，10000*10000的枚舉，差不多寫程序+跑+打表=10+3+2min就夠了吧（不過我用的是騙分手段，一個(gè)一個(gè)手算

16、。然后IF-THEN,IF-THEN，最后15分鐘搞定）。3、經(jīng)典題目，斜向劃分階段。35分鐘搞定（前三個(gè)題目1小時(shí)思路+編程+檢查夠了）4、本屆唯一挑戰(zhàn)性題目?？紤]到要求字典序最小，那么按照ABCD的順序貪心即可。對于當(dāng)前的狀態(tài)，設(shè)該進(jìn)入到輸出序列中的是p，輸入隊(duì)列頭是q，S1棧頂是t1，S2棧頂是t2，那么依次判斷，容易知道q>=pi)如果q<t1或者t1不存在，執(zhí)行A，continue;ii)如果t1=p，執(zhí)行B，continue;iii)如果q<t2或者t2不存在，執(zhí)行C，continue;iv)如果q=t2，執(zhí)行D，continue;v)輸出無解信息，halt;這個(gè)

17、算法應(yīng)該是錯(cuò)誤的。 一個(gè)反例是：7 2 5 1 4 6 3。在上述四個(gè)判斷條件中，能夠產(chǎn)生沖突的只有i和iii，在i和iii沖突的時(shí)候需要判斷。所以我對上述算法進(jìn)行修改：i)如果(q<t1或者t1不存在)and(輸入隊(duì)列中不存在x，使得q<t2<x<t1) ，執(zhí)行A，continue;ii)如果t1=p，執(zhí)行B，continue;iii)如果q<t2或者t2不存在，執(zhí)行C，continue;iv)如果q=t2，執(zhí)行D，continue;v)輸出無解信息，halt;歸納法證明算法正確性：當(dāng)n很小的時(shí)候（至少我沒舉出反例）算法是正確的。設(shè)n<k成立，考慮n=k的

18、情況。當(dāng)q=k時(shí)，顯然(不存在x，使得q<t2<x<t1)，也沒有q<t1或者q<t2的情況，所以k能夠入棧的充要條件是t1不存在或者t2不存在。只要最大的數(shù)k放在了棧底，對其他的數(shù)都是沒有影響的。所以算法依然正確。證畢。（表述的很不規(guī)范。）NOIP2008提高組解題報(bào)告angwuy1 word這道題完全是送分題，只需要直接統(tǒng)計(jì)，再判斷素?cái)?shù)。參考程序：var st:string; max,min,i:longint; a:array'a'.'z'of longint; ch:char;function fun(n:longint):

19、boolean;var i:longint;begin if n<2 then begin fun:=false;exit;end; for i:=2 to n-1 do if n mod i=0 then begin fun:=false;exit;end; fun:=true;end;begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(st); fillchar(a,sizeof(a),0); for i:=1 t

20、o length(st) do inc(asti); max:=0; min:=101; for ch:='a' to 'z' do if ach>0 then begin if ach>max then max:=ach; if ach<min then min:=ach; end; if fun(max-min) then begin writeln('Lucky Word'); writeln(max-min); end else begin writeln('No Answer'); writeln(0)

21、; end; close(input); close(Output);end.2 matches搜索題，由于輸入的情況只有25種，所以打表也是一種可行的方法。在數(shù)據(jù)最大時(shí)，經(jīng)過人工和電腦證明是不會(huì)到達(dá)四位數(shù)的，所以可以直接用O(1000*1000)的搜索算法參考程序:const mat:array0.9of longint=(6,2,5,5,4,5,6,3,7,6);function fun(m:longint):longint;var t:longint;begin t:=0; while m>0 do begin inc(t,matm mod 10); m:=m div 10; en

22、d; fun:=t;end;var a:array0.1000 of longint; n,i,j,ans:longint;begin assign(input,'matches.in'); reset(input); assign(output,'matches.out'); rewrite(output); readln(n); if n<10 then begin writeln(0);close(output);exit;end; a0:=6; for i:=1 to 1000 do ai:=fun(i); dec(n,4); for i:=0 t

23、o 1000 do if ai<n then begin for j:=0 to 1000-i do if ai+aj+ai+j=n then inc(ans); end; writeln(ans); close(input); close(output);end.3 messageDP題，兩條路線必定一上一下，而且，當(dāng)?shù)竭_(dá)某一列后，前面對后面的不會(huì)有影響，符合動(dòng)態(tài)規(guī)劃的無后效性，方程如下：用dpI,j,k表示當(dāng)?shù)竭_(dá)I列時(shí)，上路線在j行到，下路線在k行到的最大值。另外加一個(gè)預(yù)處理，sumI,j1,j2表示在第I列j1到j(luò)2行的數(shù)加起來的和。邊界條件：dp2,1,k:=sum1,1,k;遞推方程:dpI,j,k:=max(dpI-1,j2,k2+sumI-1,j,j2+sumI-1,k,k2) j<=j2<k<=k2答案：max(dpm,j,n+summ,j,n)參考程序：const maxn=10;var a:array1.maxn,1.maxnof longint; dp,sum:array1.maxn,1.maxn,1.maxnof longint; n,m,i,j,k,i1,i2,j1,j2,k1,k2:longint;fun