NOIP2006普及組復(fù)賽試題(附題解)

NOIP2006普及組解題報告NOIP2006普及組解題報告KydDong明明的隨機數(shù)（random.pas/c/cpp）【問題描述】N個1到1000對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉，不同的數(shù)【輸入文件】random.in211的隨機數(shù)的個數(shù)：N2N【輸出文件】random.out211M2行為M大排好序的不相同的隨機數(shù)。【輸入樣例】102040326740208930040015【輸出樣例】8152032406789300400【試題分析】簡單的映射排序，用一個數(shù)組s[1..n]用一個數(shù)組a[1..1000]0，在讀入s[i]之后，先判斷a[s[i]]是1，是則再讀下一個數(shù)據(jù)，不是則把a[s[i]在輸出時，則先輸出m,再用一個循環(huán)輸出各個值，即用如下偽代碼：Fori←1to1000do{Ifa[i]=1Then 打印i；}1NOIP2006普及組解題報告當(dāng)然還有許多不同的方法，這里只給出代碼，供讀者自己研究。1.【程序代碼】1.programrandom;{映射排序}varp:array[1..1000]ofshortint; n,l:shortint;a,max,i:integer;input,output:text;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);fillchar(p,sizeof(p),0);max:=-1;l:=0; {max:存最大數(shù)，l:不同數(shù)字的個數(shù)}

fori:=1tondobeginread(input,a);ifp[a]=0thenbegin p[a]:=1;l:=l+1end;{當(dāng)前數(shù)未重復(fù)，則標(biāo)記并記數(shù)}ifa>maxthenmax:=a;end;rewrite(output);writeln(output,l);fori:=1tomaxdoifp[i]=1thenwrite(output,i,'');close(input);close(output);gramrandom;{插入排序}varp:array[1..1000]ofboolean;a:array[1..100]ofinteger;i,n,j,g:integer;input,output:text;2NOIP2006普及組解題報告procedureswap(vara,b:integer);varc:integer;beginc:=a;a:=b;b:=c;end;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);fillchar(p,sizeof(p),false);g:=2;read(input,a[1]);p[a[1]]:=true;fori:=2tondobeginread(input,a[g]);ifp[a[g]]=falsethenbeginp[a[g]]:=true; 當(dāng)前數(shù)已有標(biāo)j:=g; 插入排}whilej>1dobeginifa[j]<a[j-1]thenswap(a[j-1],a[j]);j:=j-1;end;g:=g+1;end;end;rewrite(output);writeln(output,g-1);fori:=1tog-1do write(output,a[i],'close(output);close(input);end.3.3.3NOIP2006普及組解題報告programrandom;{插入排序}vara:array[1..100]ofinteger;i,j,k,l,n,g:integer;input,output:text;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);g:=1;read(input,a[1]);fori:=2tondobeginread(input,k);j:=1;while(k>a[j])and(j<=g)doj:=j+1;{找插入位置}ifk<a[j]then{中間插入}beging:=g+1;forl:=gdowntoj+1doa[l]:=a[l-1];a[j]:=k;end;ifj>gthenbeging:=g+1;a[g]:=kend; end;rewrite(output);writeln(output,g);fori:=1tog-1dowrite(output,a[i],'');writeln(output,a[g]);close(output);close(input);gramrandom;{鏈表插入排序}typelink=^node;node=recorddata:integer;4NOIP2006普及組解題報告next:link;end;varh,t,r,s:link;i,g,n,k:integer;input,output:text;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);g:=1;new(t);read(input,t^.data);t^.next:=nil;h:=t;{用第一個數(shù)建立鏈?zhǔn)字羔榼for i:=2 to n do{插入其余的數(shù)}beginread(input,k);ifk<h^.datathenbeginnew(t);t^.data:=k;t^.next:=h;h:=t;g:=g+1end{鏈?zhǔn)撞迦雧elsebeginr:=h;while(k>r^.data)and(r^.next<>nil)dobegins:=r;r:=r^.nextend;{在鏈中查找插入位置}ifk<r^.datathenbeginnew(t);t^.data:=k;s^.next:=t;t^.next:=r;g:=g+1end elseif(k<>r^.data)and(r^.next=nil)thenbeginnew(t);t^.data:=k;r^.next:=t;t^.next:=nil;g:=g+1end{處理在鏈尾插入}end;end;rewrite(output);writeln(output,g);5NOIP2006普及組解題報告r:=h;repeatwrite(output,r^.data,'');r:=r^.next;untilr=nil;close(output);close(input);gramrandom;{樹排序}vara:array[1..100,1..3]ofinteger;i,n,g:integer;input,output:text;procedurepx(s:integer); ,s入點}beginif a[i,2]<a[s,2] then if a[s,1]=0 then a[s,1]:=i;g:=g+1endelse begins:=a[s,1];px(s)end;if a[i,2]>a[s,2] then if a[s,3]=0 then a[s,3]:=i;g:=g+1endelse begins:=a[s,3];px(s)end;end;procedureprint(s:integer); beginifa[s,1]<>0thenprint(a[s,1]);左子樹不空，則遞write(output,a[s,2],''); {輸出當(dāng)前父結(jié)點}ifa[s,3]<>0thenprint(a[s,3]);{右子樹不空，則遞歸}end;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);fillchar(a,sizeof(a),0);6NOIP2006普及組解題報告g:=1;read(input,a[g,2]);fori:=2tondobeginread(input,a[i,2]);px(1)end;rewrite(output);writeln(output,g);print(1);close(output);close(input);end.開心的金明(happy.pas/c/cpp)【問題描述】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間NN51~55N（N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j件物品的價格為v[jw[j]k件物品，編號依次為j1

，??，j2

，則所求的總和為：kv[j

]*w[j]+v[j]*w[j+v[j]*w[j（*為乘號）1 1 2 2 k k請你幫助金明設(shè)計一個滿足要求的購物單。【輸入文件】輸入文件happy.in的第1行，為兩個正整數(shù)，用一個空格隔開：Nm（）2m+1jj-12vp（其中v表示該物品的價格(v<=10000)，p表示該物品的重要度(1~5)）【輸出文件】7NOIP2006普及組解題報告happy.out格與重要度乘積的總和的最大值<10000000?！据斎霕永?000580024005300540032002【輸出樣例】3900【試題分析】0/1規(guī)劃與深度優(yōu)先搜索。S[b+w]=MAX{S[b+w],S[b]+w*z}(n-w<=b<=1)最后S[n]即為題目中所求的最大值。其次是深搜，先初始化，每次遞歸一件物品，只遞歸這件物品選與不選，當(dāng)?shù)降趍件物品時，判斷其是否為最大值即可，是則保存。但又仔細(xì)一想，它是否也可以去用二進制模擬呢？答案是可以的，先構(gòu)造一個由m0m1151.【程序代碼】1.programhappy; vars:array[1..30000]of0..100000000;w,z:integer;max:longint;a,b,c,n,m:integer;input,output:text;beginassign(input,'happy.in');assign(output,'happy.out');reset(input);fillchar(s,sizeof(s),0);readln(input,n,m);8NOIP2006普及組解題報告fora:=1tomdo{動態(tài)規(guī)化}beginreadln(input,w,z);forb:=n-wdownto1doifs[b]+w*z>s[b+w]thens[b+w]:=s[b]+w*z;end;rewrite(output);writeln(output,s[n]);close(input);close(output);gramhappy;{遞歸}vara:array[1..25,1..2]ofinteger;max,s:longint;i,n,m:integer;input,output:text;proceduredg(n:integer;s:longint;k:integer);vari:integer;beginfori:=0to1dobeginif(i=1)and(n-a[k,1]>0)thenbeginn:=n-a[k,1];s:=s+a[k,1]*a[k,2];ifs>maxthenmax:=s;end;ifk<mthendg(n,s,k+1);end;end;beginassign(input,'happy.in');assign(output,'happy.out');reset(input);readln(input,n,m);fori:=1tomdoreadln(input,a[i,1],a[i,2]);s:=0;9NOIP2006普及組解題報告dg(n,s,1);rewrite(output);writeln(output,max);close(input);close(output);gramhappy;{二進制數(shù)模擬}usesmath;vara:array[1..25]ofinteger;i,j,t:longint;max,s,s0:qword;n1,n2:longint;n,m:integer;v,q:array[1..25]oflongint;input,output:text;beginassign(input,'happy.in');assign(output,'happy.out');reset(input);readln(input,n,m);fori:=1tomdobeginreadln(input,n1,n2);q[i]:=n1;v[i]:=n1*n2;end;close(input);fillchar(a,sizeof(a),0);max:=0;fori:=1to(2**m)do2^mbegina[1]:=a[1]+1;j:=1;whilea[j]=2do begina[j]:=0;a[j+1]:=a[j+1]+1;j:=j+1;10NOIP2006普及組解題報告end;

end;s:=0;s0:=0;forj:=1tomdobegins:=s+a[j]*v[j];s0:=s0+a[j]*q[j]if(s0<=n)and(s>max)thenmax:=s;end;rewrite(output);writeln(output,max);close(output);end.{注：物品多于15個時超時}Jam（count.pas/c/cpp）【問題描述】Jam，英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為JamJam210{b,c,d,e,f,g,h,i,j}這些字5Jambdfij”之后的bdgh（如果我們用V依次表示Jam“bdfi”與bdghU<，且不存在Jam數(shù)字P，使U<P<對于從文件讀入的一個Jam5個Jam數(shù)字，如果后面沒有那么多Jam【輸入文件】輸入文件counting.in21311NOIP2006普及組解題報告隔開：stw（其中sw32≤w≤t-s2wJam所給的數(shù)據(jù)都是正確的，不必驗證?！据敵鑫募枯敵鑫募ounting.out5Jam5個JamJamJamw串，不要有多余的空格?！据斎霕永?105bdfij【輸出樣例】bdghibdghjbdgijbdhijbefgh【試題分析】這是個經(jīng)典的組合問題，這個問題化簡后就是在m個字母中選n個字母，不能重復(fù)選取，并且要按照字典順序。為了方便，建議使用生成法生成組合。在生成法中，數(shù)組a的初值定為輸入值，并最好是把字母轉(zhuǎn)換成數(shù)字。1.【程序代碼】1.programcount;varc,s,t,w:integer; a:string;x:array[0..26]ofinteger;input,output:text;proceduredfs(k,q0:integer); vari,q:integer;beginifc<=5then beginifk<=wthen{k:當(dāng)前待確定字符位置}12NOIP2006普及組解題報告beginifc=0thenq:=ord(a[k])-96 {當(dāng)前第k符從初值qelseq:=q0; 前第kk-1fori:=qtot-w+kdo 第ki，并置標(biāo)志x[i]=1beginx[i]:=1;dfs(k+1,i+1);x[i]:=0end;endelsebeginifc>0then beginfori:=stotdoifx[i]>0thenwrite(output,chr(i+96));writeln(output);end;inc(c); end;end;end;beginc:=0;fillchar(x,sizeof(x),0);assign(input,'count.in');reset(input);readln(input,s,t,w);readln(input,a);close(input);assign(output,'count.out');rewrite(output);dfs(1,0);close(output);gramcount;vari,j,k,total,s,t,w:integer;13NOIP2006普及組解題報告a:array[0..26]ofinteger;ch:char;beginassign(input,'count.in');reset(input);assign(output,'count.out');rewrite(output);readln(input,s,t,w);a[0]:=0;fori:=1towdo {逐個字符讀入,并將字符轉(zhuǎn)換為1-26的數(shù)值,順序存入a數(shù)組}beginread(input,ch);a[i]:=ord(ch)-ord('a')+1;end;readln(input);close(input);total:=0;while(a[0]=0)and(total<5)do begininc(total);{計數(shù)}j:=w;whilea[j]=t-w+jdodec(j);{確定當(dāng)前可改變字符的位置j}inc(a[j]);j后續(xù)字符}fork:=j+1towdoa[k]:=a[k-1]+1;jifa[0]=0then {a[0]=15beginfori:=1towdo write(output,chr(a[i]+ord('a')-1));writeln(output);end;end;close(output);end.14NOIP2006普及組解題報告數(shù)列（sequence.pas/c/cpp）【問題描述】k(3≤k≤15),k不相等的kk=3序列是：1，3，4，9，10，12，13，?15NOIP2006普及組解題報告（3313+333+323+323+3+32?）請你求出這個序列的第N（10。例如，對于k=3，N=100，正確答案應(yīng)該是981?！据斎胛募枯斎胛募equence.in12kN（kN3k1510≤100?！据敵鑫募枯敵鑫募equence.out為計算結(jié)果，是一個正整數(shù)（測試數(shù)據(jù)中，結(jié)果均不超過2.1*109（整數(shù)前不要有空格和其他符號?！据斎霕永?100【輸出樣例】981【試題分析】這是一道數(shù)學(xué)與計算機算法結(jié)合的典型試題，具體方法見程序，其規(guī)律，從而失分。1.【程序代碼】1.programsequence;{遞推計算}vara:array[1..2000]ofqword;w:integer;f:qword;i,j,n:integer;k:qword;input,output:text;beginassign(input,'sequence.in');assign(output,'sequenc.out');reset(input);read(input,k,n);close(input);fillchar(a,sizeof(a),0);w:=1; i:=1; a[1]:=1;16NOIP2006普及組解題報告f:=1;repeatf:=f*k; {計算kw:=w+1;a[w]:=f;j:=0;while(w<n)and(j<i)do k3^0+3^1,}beginj:=j+1;w:=w+1; {j:當(dāng)前k指針，k:ka[w]:=a[j]+f;end;i:=w;untilrewrite(output);writeln(output,a[n]);close(output);end.2.2.Programsequence;vari,j,k,n:longint;w,t:int64;a:array[0..10000]ofinteger;input,output:text;beginassign(input,'sequence.in');reset(input);assign(output,'sequence.out');rewrite(output);readln(input,k,n);fillchar(a,sizeof(a),0);j:=0;whilen>0do {將n2begina[j]:=nmod2;n:=ndiv2;17

為位數(shù)}NOIP2006普及組解題報告Inc(j);end;t:=0;w:=1;fori:=0tojdo2k10t}beginInc(t,w*a[i]);w:=w*k;end;writeln(output,t);close(input);close(output);end.n2k十進制就可以了。分析：k＝31（=30）和（=3，而沒有出現(xiàn)=30+3，因此，對于k的任意次冪，只10k成是k以k＝3n二進制數(shù)數(shù)列中的第n項拆分1 0011 302 0103 313 0114 31+304 1009 325 1011032+306 1101232+317 1111332+31+30}3.3.programsequence;{利用二進制數(shù)模擬}usesmath;vara:array[1..10]ofinteger;n,i,j:integer;18NOIP2006普及組解題報告k,s,f:int64;input,output:text;beginassign(input,'sequence.in');assign(output,'sequence.out');reset(input);rewrite(output);readln(input,k,n);close(input);fillchar(a,sizeof(a),0);fori:=1tondo {將nbegina[1]:=a[1]+1;j:=1;while(a[j]=2)do begina[j]:=0;a[j+1]:=a[j+1]+1;j:=j+1;end;end;s:=0;f:=1;fori:=1to10do kf