Pascal历届NOIP复赛试题(1)-分析.doc

二中信息学奥赛培训讲义——中级班
第12讲-历届NOIP复赛试题(1)
模拟试题
中文名
英文名
题型
分值
时限
Cantor
canor
传统题
100
1s
回文数
huiwen
传统题
100
1s
装箱问题
pack
传统题
100
1s
单词接龙
dcjl
传统题
100
1s
1. Cantor表
（cantor.pas/c/cpp）
【问题描述】
现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，…
【输入】
整数N（1≤N≤10000000）
【输出】
表中的第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<=10，N=16），表示进制；第二行M。
【输出】
一行，STEP=最少的步数
【样例输入】
87
【样例输出】
STEP=4
【分析】高精度计算，可以分以下几步进行考虑：
　　① 由于输入的数据可能是二至十六进制的数，可以将每位数转换为十进制数后，按位存放在a[i]数组中。
② 利用高精度计算的方法，按位计算两个数的和。
③ 判断这个数是否是回文数，如果不是，再看是否超过30步，超过则结束程序，否则再转至第②步执行。
【参考代码】
program huiwen;
var a:array[1..10000] of integer;
l,step,i,n:longint;
m:string;

procedure work; // 求两个数的和
var b:array[1..10000] of integer;
i:longint;
begin
fillchar(b,sizeof(b),0);
for i:=1 to l do
b[i]:=a[i]+a[l+1-i];
for i:=1 to l do
if b[i]>=n then begin
dec(b[i],n);
inc(b[i+1]);
end;
if b[l+1]>0 then inc(l);
for i:=1 to l do a[i]:=b[i];
end;

function judge:boolean; // 判断是否是回文数
var i:longint;
begin
for i:=1 to (l div 2) do
if a[i]<>a[l+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(m[i])<ord('A') then
a[l+1-i]:=ord(m[i])-ord('0')　// 这里可以直接赋给a[i]吗？
else
a[l+1-i]:=ord(m[i])-ord('A')+10;
inc(i);
end;
repeat
inc(step);
work;
until (step>=30) or judge;
if step>=30 then
writeln('Impossible!')
else
writeln('STEP=',step);
close(input);
close(output);
end.
3. 装箱问题
（pack.pas/c/cpp）
【问题描述】
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
【输入】
第一行，一个整数，表示箱子容量；第二行，一个整数，表示有n个物品；接下来n行，分别表示这n个物品的各自体积。
【输出】
一个整数，表示箱子剩余空间。
【样例输入】
24
6
8
3
12
7
9
7
【样例输出】
0
【分析】
本题是经典问题：0-1背包的特殊例子（加强了已知条件）。用整型数组v存储各件物品的体积，用布尔型函数f(i,k)表示前i个物品通过组合能否恰好装满容量k的空间，则考虑第i件物品，如果没有被选中，则问题转化为f(i-1,k);如果第i件物品被选中了，则问题转化为f(i-1,k-v[i]),因此有如下的表达式：
f(i,k)=f(i-1,k-v[i]) 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(c[i]);
for i:=0 to n do f[i,0]:=true; // 初始化
for i:=1 to n do
for j:=0 to v do
if j>=c[i] then
f[i][j]:=f[i-1][j-c[i]] or f[i-1][j] // f[i,j]表示第i个数经过前面的组合能否等于j
else
f[i][j]:=f[i-1][j];
for i:=v downto 0 do
if f[n,i] then begin // f[n,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的变化范围为V～v[i]。
参考代码：
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(c[i]);
f[0]:=true;
for i:=1 to n do
for j:=v downto c[i] do // 注意这里是v→c[i]降序
f[j]:=f[j-c[i]] or f[j];
for i:=v downto 0 do
if f[i] 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行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
【输出】
只需输出以此字母开头的最长的“龙”的长度
【样例输入】
5
at
touch
cheat
choose
tact
a
【样例输出】
23　（说明：连成的“龙”为atoucheatactactouchoose）
【分析】DFS或BFS，字符串处理。
　　注意：① 每个字符串最多能用2次；② 当串1是串2的子串，则两个串不能相接。
【参考代码】
program word;
var
max,i,n:integer;
f:text;
a:array[1..30] of string;
time:array[1..30] of byte;
head,fin:string;
procedure lj(tail:string;lins:integer); // DFS
var
i,len1,len2,p:integer;
next:string;
begin
len1:=length(tail);
for i:=1 to n do
if (pos(tail,a[i])=1) and (time[i]<2) then begin
len2:=length(a[i]);
inc(time[i]); // 记录使用次数
p:=1;
lins:=lins+len2-len1; // 接上新串后的长度
while p<len2 do
begin
next:=copy(a[i],len2+1-p,p);
lj(next,lins);
inc(p);
end;
lins:=lins-len2+len1; // 回溯
dec(time[i]);
end;
if lins>max then max:=lins;
end;
{======================== main ==============================}
begin
assign(input,'dcjl.in');
reset(input);
readln(n);
for i:=1 to n do readln(a[i]);
readln(head);
close(input);
max:=0;
for i:=1 to n do time[i]:=0;
lj(head,length(head));
assign(output,'dcjl.out');
rewrite(output);
writeln(max);
close(output);
end.

- 9 -