NOIP2006普及组复赛试题(附题解)

NOIP2006普及组解题报告NOIP2006普及组解题报告KydDong明明的随机数（random.pas/c/cpp）【问题描述】N个1到1000对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数【输入文件】random.in211的随机数的个数：N2N【输出文件】random.out211M2行为M大排好序的不相同的随机数。【输入样例】102040326740208930040015【输出样例】8152032406789300400【试题分析】简单的映射排序，用一个数组s[1..n]用一个数组a[1..1000]0，在读入s[i]之后，先判断a[s[i]]是1，是则再读下一个数据，不是则把a[s[i]在输出时，则先输出m,再用一个循环输出各个值，即用如下伪代码：Fori←1to1000do{Ifa[i]=1Then 打印i；}1NOIP2006普及组解题报告当然还有许多不同的方法，这里只给出代码，供读者自己研究。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:存最大数，l:不同数字的个数}

fori:=1tondobeginread(input,a);ifp[a]=0thenbegin p[a]:=1;l:=l+1end;{当前数未重复，则标记并记数}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; 当前数已有标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;{用第一个数建立链首指针}for i:=2 to n do{插入其余的数}beginread(input,k);ifk<h^.datathenbeginnew(t);t^.data:=k;t^.next:=h;h:=t;g:=g+1end{链首插入}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],''); {输出当前父结点}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)【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间NN51~55N（N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第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请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件happy.in的第1行，为两个正整数，用一个空格隔开：Nm（）2m+1jj-12vp（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）【输出文件】7NOIP2006普及组解题报告happy.out格与重要度乘积的总和的最大值<10000000。【输入样例】1000580024005300540032002【输出样例】3900【试题分析】0/1规划与深度优先搜索。S[b+w]=MAX{S[b+w],S[b]+w*z}(n-w<=b<=1)最后S[n]即为题目中所求的最大值。其次是深搜，先初始化，每次递归一件物品，只递归这件物品选与不选，当到第m件物品时，判断其是否为最大值即可，是则保存。但又仔细一想，它是否也可以去用二进制模拟呢？答案是可以的，先构造一个由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{动态规化}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;{二进制数模拟}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，英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为JamJam210{b,c,d,e,f,g,h,i,j}这些字5Jambdfij”之后的bdgh（如果我们用V依次表示Jam“bdfi”与bdghU<，且不存在Jam数字P，使U<P<对于从文件读入的一个Jam5个Jam数字，如果后面没有那么多Jam【输入文件】输入文件counting.in21311NOIP2006普及组解题报告隔开：stw（其中sw32≤w≤t-s2wJam所给的数据都是正确的，不必验证。【输出文件】输出文件counting.out5Jam5个JamJamJamw串，不要有多余的空格。【输入样例】2105bdfij【输出样例】bdghibdghjbdgijbdhijbefgh【试题分析】这是个经典的组合问题，这个问题化简后就是在m个字母中选n个字母，不能重复选取，并且要按照字典顺序。为了方便，建议使用生成法生成组合。在生成法中，数组a的初值定为输入值，并最好是把字母转换成数字。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:当前待确定字符位置}12NOIP2006普及组解题报告beginifc=0thenq:=ord(a[k])-96 {当前第k符从初值qelseq:=q0; 前第kk-1fori:=qtot-w+kdo 第ki，并置标志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 {逐个字符读入,并将字符转换为1-26的数值,顺序存入a数组}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);{计数}j:=w;whilea[j]=t-w+jdodec(j);{确定当前可改变字符的位置j}inc(a[j]);j后续字符}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普及组解题报告数列（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，正确答案应该是981。【输入文件】输入文件sequence.in12kN（kN3k1510≤100。【输出文件】输出文件sequence.out为计算结果，是一个正整数（测试数据中，结果均不超过2.1*109（整数前不要有空格和其他符号。【输入样例】3100【输出样例】981【试题分析】这是一道数学与计算机算法结合的典型试题，具体方法见程序，其规律，从而失分。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:当前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

为位数}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，而没有出现=30+3，因此，对于k的任意次幂，只10k成是k以k＝3n二进制数数列中的第n项拆分1 0011 302 0103 313 0114 31+304 1009 325 1011032+306 1101232+317 1111332+31+30}3.3.programsequence;{利用二进制数模拟}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