版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、NOIP2008提高組前三題解題報告日期:2008-11-18來源: 作者:張恩權字體:大 中 小 NOIP2008提高組前三題解題報告1.笨小猴基本的字符串處理,細心一點應該沒問題的,不過判斷素數(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;/記錄每個字符出現(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;/判斷素數(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)計每個字符出現(xiàn)的次數(shù) inc(fsi); min:=1000; max:=0; for ch:= 'a' to 'z' do/統(tǒng)計最大和最小 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.火柴棒等式預處理下,然后枚舉、剪枝,范圍稍微開大點,弄到2000似乎足夠了,剪枝后不會超時的。首先預處理下每個數(shù)(02000)需要多少個火柴棒,然后枚舉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;/預處理02000每個數(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,中間路徑不相交與某個人。換種思路,它完全等價于,從A點傳出2張紙條到B,中間不能經(jīng)過同一人。這么看來似乎就是vijos三取方格數(shù)的簡化版了。解題思想就是雙進程的動態(tài)規(guī)劃。階段是按傳遞次數(shù)劃分的。F(d,x1
8、,y1,x2,y2)表示第d次傳遞到坐標為(x1,y1),(x2,y2)兩個人手中是得到的最大好心度。那么可以列出方程:F(d,x1,y1,x2,y2)=max f (d-1,x1',y1',x2',y2' )+ax1,y1+ax2,y2 | (x1',y1')為把紙條(x1,y1)的人,(x2' , y2')為把紙條轉給(x2,y2)的人(數(shù)學不太好,方程列的不專業(yè),見諒_)這么看來時間復雜度是O(maxd*n*m*n*m),其中maxd=n+m-2。相當于505=312500000,超時是沒得說的了。其實我們可以把狀態(tài)再壓縮下
9、,先來看下其中的規(guī)律:起點 (1,1)第1次傳遞可到達 (1,2)(2,1)第2次傳遞可到達 (1,3)(2,2)(3,1)很快就可以發(fā)展其中的規(guī)律第d次傳遞可到達的坐標(xi,yi)和d之間存在d+2=xi+yi那么我們就可以把上面的狀態(tài)轉移方程轉化成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; /邊界,因為中間需要判斷點不重合,所以把必須重合的狀態(tài)單獨考慮 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); / 終點的只可能從兩個點來,所以終點狀態(tài)前移一個階段。 fclose;end.4.雙棧排序難,寫不出滿分程序,所以還是不寫了NOIP2008提高組復賽 解題思路1、字符串中統(tǒng)計字母出現(xiàn)次數(shù) 最大減最小的 然后判斷質數(shù) 字符串長度<=1002、給出n<=24個火柴棍,求最多能擺出多少a+b=c形式的等式。數(shù)字的擺法和計算器相同,a,b,c>=03、雙進程方格取數(shù):m*n的棋盤,m,n<=50,不需使用高精度4、給出1.n的排列,兩個棧S1、S2,入棧出棧共4個操作:(n<=1000)
15、 A:輸入隊列頭入S1 B:彈出S1棧頂元素,進入輸出隊列 C:輸入隊列頭入S2 D:彈出S2棧頂元素,進入輸出隊列 要求將1.n的排列排序,采用字典序最小的操作方法個人感覺是,單就難度來看,奧賽歷史最簡單,由于類似2,3題的模型大多數(shù)能拿一等的同學們都見過。我的想法:1、水題,最多40分鐘搞定2、如果是考試的話,10000*10000的枚舉,差不多寫程序+跑+打表=10+3+2min就夠了吧(不過我用的是騙分手段,一個一個手算
16、。然后IF-THEN,IF-THEN,最后15分鐘搞定)。3、經(jīng)典題目,斜向劃分階段。35分鐘搞定(前三個題目1小時思路+編程+檢查夠了)4、本屆唯一挑戰(zhàn)性題目??紤]到要求字典序最小,那么按照ABCD的順序貪心即可。對于當前的狀態(tài),設該進入到輸出序列中的是p,輸入隊列頭是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;這個
17、算法應該是錯誤的。 一個反例是:7 2 5 1 4 6 3。在上述四個判斷條件中,能夠產(chǎn)生沖突的只有i和iii,在i和iii沖突的時候需要判斷。所以我對上述算法進行修改:i)如果(q<t1或者t1不存在)and(輸入隊列中不存在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;歸納法證明算法正確性:當n很小的時候(至少我沒舉出反例)算法是正確的。設n<k成立,考慮n=k的
18、情況。當q=k時,顯然(不存在x,使得q<t2<x<t1),也沒有q<t1或者q<t2的情況,所以k能夠入棧的充要條件是t1不存在或者t2不存在。只要最大的數(shù)k放在了棧底,對其他的數(shù)都是沒有影響的。所以算法依然正確。證畢。(表述的很不規(guī)范。)NOIP2008提高組解題報告angwuy1 word這道題完全是送分題,只需要直接統(tǒng)計,再判斷素數(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ù)最大時,經(jīng)過人工和電腦證明是不會到達四位數(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題,兩條路線必定一上一下,而且,當?shù)竭_某一列后,前面對后面的不會有影響,符合動態(tài)規(guī)劃的無后效性,方程如下:用dpI,j,k表示當?shù)竭_I列時,上路線在j行到,下路線在k行到的最大值。另外加一個預處理,sumI,j1,j2表示在第I列j1到j2行的數(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年私人車輛抵押融資租賃管理服務協(xié)議范本3篇
- 玩具主題項目課程設計
- 綜合認知早教課程設計
- 2025年度城市基礎設施建設設備搬運合同3篇
- 2025年度地下管網(wǎng)安裝與檢測服務合同2篇
- 二零二五年度公租房建設項目合同終止與解除合同3篇
- 2025年度酒店管理SaaS系統(tǒng)服務合同模板2篇
- 算力網(wǎng)絡培訓課程設計
- 2024木材購銷合同范文
- 未來書房課程設計
- 2024年新人教版七年級上冊地理課件 第二章 地圖 第二節(jié) 地形圖的判讀
- 2024至2030年中國汽摩配行業(yè)發(fā)展狀況及競爭格局分析報告
- 濰柴天然氣發(fā)動機結構及工作原理
- 國家開放大學《理工英語2》形考任務1-8參考答案
- 2024年電大勞動與社會保障法期末考試題庫及答案
- 人教版九年級數(shù)學上冊21.1《一元二次方程》教學設計
- 2025屆高考政治一輪復習:統(tǒng)編版必修4《哲學與文化》必背知識點考點提綱
- 從古至今話廉潔-大學生廉潔素養(yǎng)教育智慧樹知到期末考試答案章節(jié)答案2024年吉林大學
- 高中英語外刊-小貓釣魚50篇
- 【打油詩】72則創(chuàng)意期末評語模板-每頁8張
- 傳承傳統(tǒng)文化教育教案(3篇模板)
評論
0/150
提交評論