全国青少年信息学计算机奥林匹克分区联赛提高组复赛试题文档格式.docx
- 文档编号:5942465
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:27
- 大小:49.11KB
全国青少年信息学计算机奥林匹克分区联赛提高组复赛试题文档格式.docx
《全国青少年信息学计算机奥林匹克分区联赛提高组复赛试题文档格式.docx》由会员分享,可在线阅读,更多相关《全国青少年信息学计算机奥林匹克分区联赛提高组复赛试题文档格式.docx(27页珍藏版)》请在冰点文库上搜索。
有两个字串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
屏幕显示:
题三自由落体〔存盘名:
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
2002年全国青少年信息学〔计算机〕
奥林匹克分区联赛复赛提高组试题解题报告
可以在任一堆上取假设干张纸牌,然后移动。
分析:
如果你想到把每堆牌的张数减去平均张数,题目就变成移动正数,加到负数中,使大家都变成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:
array[1..maxn]ofinteger;
f:
text;
filename:
string;
begin
write('
Inputfilename:
'
);
readln(filename);
assign(f,filename);
reset(f);
readln(f,n);
=0;
step:
fori:
=1tondobegin
read(f,a[i]);
inc(ave,a[i]);
end;
=avedivi;
=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]:
{第i堆牌移走后变为0}
inc(step);
{移牌步数计数}
inc(i);
{对下一堆牌进行循环操作}
{过滤移牌过程中产生的0}
writeln(step);
end.
点评:
基此题〔较易〕此题有3点比较关键:
一是善于将每堆牌数减去平均数,简化了问题;
二是要过滤掉0〔不是所有的0,如-2,3,0,-1中的0是不能过滤的〕;
三是负数张牌也可以移动,这是辩证法〔关键中的关键〕。
在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…。
abcdxyz
此题是典型的广度优先搜索的例子,但如果只采用正向搜索,某些情况下计算量过大,速度过慢,故采取双向搜索且判重并适当剪枝,效果较好。
{$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;
{str表示字串,其长度不会超过115〔长度超过115的字串
不可能通过变换成为目标字串,因为题目限定变换10次之内,且串长
不超过20,即起始串最多可经过5次变换时增长,中间串的最大长度
为20+5*19=115,否那么经过余下的步数不可能变为长度不超过20的
目标串〕,dep表示深度}
ctype=array[1..maxn]of^node;
bin=0..1;
var
maxk:
c:
array[0..1]ofctype;
x0:
array[0..6,0..1]ofstring[20];
open,closed:
array[0..1]ofinteger;
procedureInit;
{读取数据,初始化}
varf:
temp:
i,j:
=0to1do
forj:
=1tomaxndonew(c[i,j]);
whilenoteof(f)and(i<
=6)dobegin
readln(f,temp);
x0[i,0]:
=copy(temp,1,pos('
temp)-1);
x0[i,1]:
=copy(temp,pos('
temp)+1,length(temp));
=i-1;
close(f);
procedurecalc;
vari,j,k:
st:
bin;
d:
procedurebool(st:
bin);
{判断是否到达目标状态或双向搜索相遇}
vari:
ifx0[0,1-st]=c[st,closed[st]]^.strthenbegin
{如果到达目标状态,那么输出结果,退出}
writeln(c[st,closed[st]]^.dep);
halt;
=1toclosed[1-st]do
ifc[st,closed[st]]^.str=c[1-st,i]^.strthenbegin
{如果双向搜索相遇〔即得到同一节点〕,
那么输出结果〔2个方向搜索的步数之和〕,退出}
writeln(c[st,closed[st]]^.dep+c[1-st,i]^.dep);
procedurecheckup(st:
{判断节点是否与前面重复}
=1toclosed[st]-1do
ifc[st,i]^.str=c[st,closed[st]]^.strthenbegin
dec(closed[st]);
exit;
{如果节点重复,那么删除本节点}
bool(st);
{如果节点不重复,再判断是否到达目标状态}
procedureexpand(st:
{扩展产生新节点}
vari,j,k,lx,ld:
inc(open[st]);
=c[st,open[st]]^.str;
{队首节点出队}
k:
=c[st,open[st]]^.dep;
ld:
=length(d);
=1tomaxkdobegin
{从队首节点〔父节点〕出发产生新节点〔子节点〕}
lx:
=length(x0[i,st]);
=1tolddobegin
if(copy(d,j,lx)=x0[i,st])and(length(copy(d,1,j-1)+x0[i,1-st]
+copy(d,j+lx,ld))<
=115)thenbegin
{如果新节点的串长超过115,那么不扩展!
即剪掉此枝}
ifclosed[st]>
=maxnthenexit;
{如果队列已满,只好退出}
inc(closed[st]);
{新节点入队}
c[st,closed[st]]^.str:
=copy(d,1,j-1)+x0[i,1-st]+copy(d,j+lx,ld);
c[st,closed[st]]^.dep:
=k+1;
{子节点深度=父节点深度+1}
checkup(st);
{检查新节点是否重复}
Begin
forst:
=0to1dobegin{正向(st=0)逆向(st=1)搜索节点队列初始化}
open[st]:
closed[st]:
=x0[0,st];
repeat
{选择节点数较少且队列未空、未满、深度未达到10的方向先扩展}
if(open[0]<
=open[1])andnot((open[0]>
=closed[0])or
(closed[0]>
=maxn)or(c[0,closed[0]]^.dep>
10))thenexpand(0);
if(open[1]<
=open[0])andnot((open[1]>
=closed[1])or
(closed[1]>
=maxn)or(c[1,closed[1]]^.dep>
10))thenexpand
(1);
{如果一方搜索终止,继续另一方的搜索,直到两个方向都终止}
ifnot((open[0]>
=closed[0])or(closed[0]>
=maxn)or
(c[0,closed[0]]^.dep>
ifnot((open[1]>
=closed[1])or(closed[1]>
(c[1,closed[1]]^.dep>
until(open[0]>
=closed[0])or(c[0,closed[0]]^.dep>
10)or(closed[0]>
=maxn)
and(closed[1]>
=maxn)or(open[1]>
=closed[1])or(c[1,closed[1]]^.dep>
10);
{终止条件:
任一方队空〔无解〕或搜索深度超过10〔10步内无解〕
或双方均溢出〔可能有解也可能无解,应尽量避免,要尽量把节
点数组开大一点,采用双向搜索,采取剪枝措施等〕}
End;
BEGIN
init;
calc;
writeln('
NOANSWER!
)
END.
基此题〔较难〕考察队列、〔双向〕广度优先搜索算法及字符串的运算,基本上可以考察出参赛者的数据结构和算法水平。
显然,小车太慢〔即V<
=Vmin〕或太快〔V>
Vmax〕时,一个球也接不到。
即在V<
=Vmin或V>
Vmax时输出为0。
下面分别求Vmin和Vmax。
当第n-1个小球落地的瞬间,小车在小球的右端离小球尚有e=0.00001的距离,小车的这个极小速度就是Vmin。
小车从天花板落到地面的时间t1=
这段时间内小车走了S1-〔n-1〕-e,所以Vmin=
。
当第1个小球落到距小车的上表面为e的瞬间,小车在小球的左端离小球距离为e,小车的这个极大速度就是Vmax。
小球从天花板落到离小车上表面为e的距离的时间为t2=
小车移动的距离为S1+L+e,所以Vmax=
那么,当Vmin<
V<
=Vmax时,就可接到球了。
显然,时间段[t2,t1]是小车接球的时间,在t2时刻,小车的位置为:
左表面离原点距离为S1-V*t2,右表面离原点距离为S1-V*t2+L;
在t1时刻,小车的位置为:
左表面离原点距离为S1-V*t1,右表面离原点距离为S1-V*t1+L;
故小车的接球范围(在小车运动范围外扩展e)为[S1-V*t1-e,S1-V*t2+L+e],球的个数就等于接球范围内所包含的0~n-1之间的整数的个数.
programNOIPG3;
constg=10{重力加速度};
e=1E-5;
{小车接受小球的极限距离}
varH,s1,v,l,k,t1,t2,Vmin,Vmax:
real;
n2,n1,num,n:
readln(h,s1,v,l,k,n);
num:
=-1;
t1:
=sqrt(2*h/g);
{小球落地时间}
ifh<
=k+ethent2:
=0elset2:
=sqrt(2*(h-k-e)/g);
{小球落到小车上的最短时间}
ifs1-v*t2+L+e<
thennum:
=0
elsen2:
=trunc(s1-v*t2+L+e);
{小车接受的球的最大编号为n2}
ifn2>
n-1thenn2:
=n-1;
{n2取trunc(s1-v*t2+L+e)与n-1的较小值}
ifs1-v*t1-e<
thenn1:
elseifs1-v*t1-e>
n-1
elseif(s1-v*t1-e)=trunc(s1-v*t1-e)
=trunc(s1-v*t1-e){小车接受的球的最小编号为n1}
elsen1:
=trunc(s1-v*t1-e)+1;
ifnum=-1thennum:
=n2-n1+1;
{小车接受的球的个数为num}
writeln(num);
送分题此题“物理味”有余而“信息味”不足,连循环语句都用不上!
难见的“送分题”,可物理较差的人也得不到多少分哦!
分析
1、此题的难度较大。
如果你这样认为:
即在假定已用i个矩形〔面积和满足最小〕覆盖所有点的基础上,穷举所有2个矩形合并成1个矩形〔条件是:
在所有合并方案中使合并后面积最小〕,从而使矩形个数减少为i-1——那就错了,可是却可以通过前4组测试数据!
正确的做法是对不同的K值分别进行计算,好在K值较小,否那么...
讨论:
k=1,只要求出n个点坐标的最大、最小值,就可求得矩形的位置与面积;
k=2,有2个矩形,它们只有2种分布形式:
左右式〔flag=0〕,上下式〔flag=1〕
对于左右式,显然要先将所有点按横坐标升序排列,可将点1~点i-1放入矩形1中,将点i~点n放入矩形2中,求两矩形的面积之和;
如果面积和比上一个值小,记下;
让i从2循环到n,就可完成左右式的全部搜索;
对于上下式,先将所有点按纵坐标升序排列,依此类推。
k=3,有3个矩形,它们有6种分布形式:
要用两重循环进行搜索:
设i,j为循环变量,将点1~i-1放入矩形1中,点i~j-1放入矩形2中,点j~n放入矩形3中;
点必须在放入前排好序〔均为升序〕:
对于flag=0,所有点按横坐标排序;
对于flag=1,所有点按纵坐标排序;
对于flag=2,所有点先按横坐标排序,然后点i~n按纵坐标排序;
对于flag=3,所有点先按横坐标排序,然后点1~j-1按纵坐标排序;
对于flag=4,所有点先按纵坐标排序,然后点1~j-1按横坐标排序;
对于flag=5,所有点先按纵坐标排序,然后点i~n按横坐标排序;
至于k=4,4个矩形有22种分布形式,实在太复杂!
幸好测试数据中没有K=4的情形(似乎有意放了一马?
)。
据说此题全国没有一人全对!
〔只要求K=1,2,3〕
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M65520,0,6
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国青少年 信息学 计算机 奥林匹克 分区 联赛 提高 复赛 试题
![提示](https://static.bingdoc.com/images/bang_tan.gif)