Pascal历届NOIP复赛试题-分析.docVIP

二中信息学奥赛培训讲义中级班第12讲-历届NOIP复赛试题(1)模拟试题中文名英文名题型分值时限Cantorcanor传统题1001s回文数huiwen传统题1001s装箱问题pack传统题1001s单词接龙dcjl传统题1001s1. Cantor表（cantor.pas/c/cpp）【问题描述】现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，【输入】整数N（1N10000000）【输出】表中的第N项【样例输入】7【样例输出】1/4【分析】基础题，模拟。首先确定所在斜行，然后针对奇数行和偶数行进行计算。【参考代码】var n,x:longint;begin assign(input,cantor.in); reset(input); assign(output,cantor.out); rewrite(output); readln(n); x:=0; repeat /确定所在的斜行 inc(x); n:=n-x; until n=0; if x mod 2=0 then write (x+n),/,(1-n) /确定如何输出 else writeln(1-n),/,(x+n); close(input); close(output);end.2. 回文数（huiwen.pas/c/cpp）【问题描述】若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N（2=N=10，N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”【输入】两行，第一行N（2=N=n then begin dec(bi,n); inc(bi+1); end; if bl+10 then inc(l); for i:=1 to l do ai:=bi;end;function judge:boolean; / 判断是否是回文数var i:longint;begin for i:=1 to (l div 2) do if aial+1-i then begin judge:=false; exit; end; judge:=true;end;begin assign(input,huiwen.in); assign(output,huiwen.out); reset(input);rewrite(output); readln(n); readln(m); l:=length(m); i:=1; step:=0; / 记录转换的步数 while i=l do / 将进制数转换为十进制数 begin if ord(mi)=30) or judge; if step=30 then writeln(Impossible!) else writeln(STEP=,step); close(input); close(output);end.3. 装箱问题（pack.pas/c/cpp）【问题描述】有一个箱子容量为v(正整数，ov20000)，同时有n个物品(on30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。【输入】第一行，一个整数，表示箱子容量；第二行，一个整数，表示有n个物品；接下来n行，分别表示这n个物品的各自体积。【输出】一个整数，表示箱子剩余空间。【样例输入】2468312797【样例输出】0【分析】本题是经典问题：0-1背包的特殊例子（加强了已知条件）。用整型数组v存储各件物品的体积，用布尔型函数f(i,k)表示前i个物品通过组合能否恰好装满容量k的空间，则考虑第i件物品，如果没有被选中，则问题转化为f(i-1,k);如果第i件物品被选中了，则问题转化为f(i-1,k-vi),因此有如下的表达式：f(i,k)=f(i-1,k-vi) or f(i-1,k);k从V开始递减，判断f(n,k)是否为真，第一个符号要求的k即为剩余空间最小时消耗的体积。参考代码：program pack;var f: array 0.30,0.20000 of boolean; c: array 1.30 of longint; i,j,n,v: longint;begin assign(input,pack.in); reset(input); assign(output,pack.out); rewrite(output); readln(v); readln(n); fillchar(f,sizeof(f),false); for i:=1 to n do readln(ci); for i:=0 to n do fi,0:=true; / 初始化 for i:=1 to n do for j:=0 to v do if j=ci then fij:=fi-1j-ci or fi-1j / fi,j表示第i个数经过前面的组合能否等于j else fij:=fi-1j; for i:=v downto 0 do if fn,i then begin / fn,i为真，表示对这n个数的组合恰好和为i（最大） writeln(v-i); / 剩余值 break; end; close(input); close(output);end.如果此时直接编写程序，就要定义一个二维数组，空间复杂度时n*v,注意到了n,v的取值范围很大，所以用二维数组存储就会有问题。我们注意到，f(i,k)的取值仅与f(i-1,0)f(i-1,k)有关，且如果f(i-1,k)=true,必然有f(i,k)=true,f(i,k)的值存在继承性，而程序结束时，我们也只关心f(n,k),因此，我们可以用一维数组h(k)来存储中间信息。为了避免重复计算，可以让k从大到小变化，为了避免出现负数，k的变化范围为Vvi。参考代码：program pack2;var f: array 0.20000 of boolean; c: array 1.30 of longint; i,j,n,v: longint;begin assign(input,pack.in); reset(input); assign(output,pack.out); rewrite(output); readln(v); readln(n); fillchar(f,sizeof(f),false); for i:=1 to n do readln(ci); f0:=true; for i:=1 to n do for j:=v downto ci do / 注意这里是vci降序 fj:=fj-ci or fj; for i:=v downto 0 do if fi then begin writeln(v-i); break; end; close(input); close(output);end. 4. 单词接龙（dcjl.pas/c/cpp）【问题描述】单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。【输入】输入的第一行为一个单独的整数n(n=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。【输出】只需输出以此字母开头的最长的“龙”的长度【样例输入】5attouchcheatchoosetacta【样例输出】23（说明：连成的“龙”为atoucheatactactouchoose） 【分析】DFS或BFS，字符串处理。注意： 每个字符串最多能用2次； 当串1是串2的子串，则两个串不能相接。【参考代码】program word;var max,i,n:integer; f:text; a:array1.30 of string; time:array1.30 of byte; head,fin:string;procedure lj(tail:string;lins:integer); / DFSvar i,len1,len2,p:integer; next:string;begin len1:=length(tail); for i:=1 to n do if (pos(tail,ai)=1) and (timei2) then begin len2:=length(ai); inc(timei); / 记录使用次数 p:=1; lins:=lins+len2-len1; / 接上新串后的长度 while pmax then max:=lins;end;= main =begin assign(input,dcjl.in); reset(i