2002年全国青少年信息学〔计算机〕奥林匹克分区联赛复赛试题
注意事项：认真阅读理解，结合历年的真题，总结经验，查不足！重在审题，多思考，多理解！
〔提高组竞赛用时：3小时〕
题一均分纸牌〔存盘名NOIPG1〕
[问题描述]
有N堆纸牌，编号分别为1，2，…,N。每堆上有假设干张，但纸牌总数必为N的倍数。可以在任一堆上取假设于张纸牌，然后移动。
移牌规那么为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如N=4，4堆纸牌数分别为：
①9②8③17④6
移动3次可达到目的：
从③取4张牌放到④〔981310〕->从③取3张牌放到②〔9111010〕->从②取1张牌放到①〔10101010〕。
[输入]：
键盘输入文件名。文件格式：
N〔N堆纸牌，1<=N<=100〕
A1A2…An〔N堆纸牌，每堆纸牌初始数，l<=Ai<=10000〕
[输出]：
输出至屏幕。格式为：
所有堆均达到相等时的最少移动次数。‘
[输入输出样例]
a.in：
4
98176
屏慕显示：
3
题二字串变换〔存盘名:NOIPG2〕
[问题描述]:
有两个字串A$,B$及一组字串变换的规那么〔至多6个规那么〕:
A1$->B1$
A2$->B2$
规那么的含义为：在A＄中的子串A1$可以变换为B1$、A2$可以变换为B2$…。
例如：A$＝'abcd'B$＝'xyz'
变换规那么为：
‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’
那么此时，A$可以经过一系列的变换变为B$，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得A$变换为B$。
[输入]:
键盘输人文件名。文件格式如下：
A$B$
A1$B1$\
A2$B2$ |->变换规那么
....../ 
所有字符串长度的上限为20。
[输出]:
输出至屏幕。格式如下：
假设在10步〔包含10步〕以内能将A$变换为B$，那么输出最少的变换步数；否那么输出“NOANSWER!”
[输入输出样例]
b.in:
abcdwyz
abcxu
udy
yyz
屏幕显示：
3
题三自由落体〔存盘名:NOIPG3〕
[问题描述]:
在高为H的天花板上有n个小球，体积不计，位置分别为0，1，2，…、n-1。在地面上有一个小车〔长为L，高为K，距原点距离为S1〕。小球下落距离计算公式为d＝1/2*g*(t^2)，其中g=10，t为下落时间。地面上的小车以速度V前进。
如下图：
小车与所有小球同时开始运动，当小球距小车的距离<=0.00001时，即认为小球被小车接受〔小球落到地面后不能被接受〕。
请你计算出小车能接受到多少个小球。
[输入]：
键盘输人：
H，S1，V，L，K，n〔l<=H，S1，V，L，K，n<=100000〕
[输出]：
屏幕输出：
小车能接受到的小球个数。
[输入输出样例]
[输入]:
5.09.05.02.51.85
[输出]:
1
题四矩形覆盖〔存盘名NOIPG4〕
[问题描述]:
在平面上有n个点〔n<=50〕，每个点用一对整数坐标表示。例如：当n＝4时，4个点的坐标分另为：p1〔1，1〕，p2〔2，2〕，p3〔3，6〕，P4〔0，7〕，见图一。
这些点可以用k个矩形〔1<=k<=4〕全部覆盖，矩形的边平行于坐标轴。当k=2时，可用如图二的两个矩形sl，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开〔边线与顶点也都不能重合〕。
[输入]:
键盘输人文件名。文件格式为
nk
xly1
x2y2
......
xnyn〔0<=xi,yi<=500)
[输出]:
输出至屏幕。格式为：
一个整数，即满足条件的最小的矩形面积之和。
[输入输出样例]
字符串长度最大是多少d.in:
42
11
22
36
07
屏幕显示：
4
2002年全国青少年信息学〔计算机〕
奥林匹克分区联赛复赛提高组试题解题报告
题一均分纸牌〔存盘名NOIPG1〕
[问题描述]
有N堆纸牌，编号分别为1，2，…,N。每堆上有假设干张，但纸牌总数必为N的倍数。可以在任一堆上取假设干张纸牌，然后移动。
移牌规那么为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如N=4，4堆纸牌数分别为：
①9②8③17④6
移动3次可达到目的：
从③取4张牌放到④〔981310〕->从③取3张牌放到②〔9111010〕->从②取1张牌放到①〔10101010〕。
[输入]：
键盘输入文件名。文件格式：
N〔N堆纸牌，1<=N<=100〕
A1A2…An〔N堆纸牌，每堆纸牌初始数，l<=Ai<=10000〕
[输出]：
输出至屏幕。格式为：
所有堆均达到相等时的最少移动次数。‘
[输入输出样例]
a.in：
4
98176
屏慕显示：
3
分析：如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边〔第2堆〕-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边〔第3堆〕中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边〔第4堆〕中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样
的。
如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起〔从右算起也完全一样〕，第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。
程序清单
programNOIPG1;
constmaxn=100;
vari,j,n,step:integer;ave:longint;
a:axn]ofinteger;
f:text;filename:string;
begin
write('Inputfilename:');readln(filename);
assign(f,filename);reset(f);
readln(f,n);ave:=0;step:=0;
fori:=1tondobegin
read(f,a[i]);inc(ave,a[i]);
end;
ave:=avedivi;
fori:=1tondoa[i]:=a[i]-ave;
i:=1;j:=n;
whilea[i]=0doinc(i);{过滤左边的0}
whilea[j]=0dodec(j);{过滤右边的0}
while(i<j)dobegin
inc(a[i+1],a[i]);{将第i堆牌移到第i+1堆中去}
a[i]:=0;{第i堆牌移走后变为0}
inc(step);{移牌步数计数}
inc(i);{对下一堆牌进行循环操作}
whilea[i]=0doinc(i);{过滤移牌过程中产生的0}
end;
writeln(step);
end.
点评：基此题〔较易〕此题有3点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0〔不是所有的0，如-2，3，0，-1中的0是不能过滤的〕；三是负数张牌
也可以移动，这是辩证法〔关键中的关键〕。

题二字串变换〔存盘名:NOIPG2〕
[问题描述]:
有两个字串A$,B$及一组字串变换的规那么〔至多6个规那么〕:
A1$->B1$
A2$->B2$
规那么的含义为：在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…。
例如：A$＝'abcd'B$＝'xyz'
变换规那么为：
‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’
那么此时，A$可以经过一系列的变换变为B$，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得A$变换为B$。
[输入]:
键盘输人文件名。文件格式如下：
A$B$
A1$B1$\
A2$B2$ |->变换规那么
....../ 
所有字符串长度的上限为20。
[输出]:
输出至屏幕。格式如下：
假设在10步〔包含10步〕以内能将A$变换为B$，那么输出最少的变换步数；否那么输出“NOANSWER!”
[输入输出样例]
b.in:
abcdxyz
abcxu
udy
yyz
屏幕显示：
3
分析：此题是典型的广度优先搜索的例子，但如果只采用正向搜索，某些情况下计算量过大，速度过慢，故采取双向搜索且判重并适当剪枝，效果较好。
程序清单
{$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-}
{$M8192,0,655360}
programNOIPG2;
constmaxn=2300;
type
node=record{定义节点数据类型}
str:string[115];dep:byte;
end;{str表示字串，其长度不会超过115〔长度超过115的字串
不可能通过变换成为目标字串，因为题目限定变换10次之内，且串长
不超过20，即起始串最多可经过5次变换时增长，中间串的最大长度
为20+5*19=115，否那么经过余下的步数不可能变为长度不超过20的
目标串〕，dep表示深度}
ctype=axn]of^node;
bin=0..1;
var
maxk:byte;c:array[0..1]ofctype;
x0:array[0..6,0..1]ofstring[20];
filename:string;
open,closed:array[0..1]ofinteger;
procedureInit;{读取数据，初始化}
varf:text;temp:string;i,j:integer;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。