期初测试解题报告安阳一中2009-2010学年第一学期
信息学奥赛期初考试2008级(高二)试题
时间 2009年8月23日 15:00~18:00
题目一览:
题目名称
锻炼计划
细胞
飞翔
单词划分
提交文件
exercise.pas
cell.pas
fly.pas
word.pas
输入文件
exercise.in
cell.in
fly.in
word.in
输出文件
exercise.out
cell.out
fly.out
word.out
分 值
100
100
...
安阳一中2009-2010学年第一学期
信息学奥赛期初考试2008级(高二)试题
时间 2009年8月23日 15:00~18:00
题目一览:
题目名称
锻炼计划
细胞
飞翔
单词划分
提交文件
exercise.pas
cell.pas
fly.pas
word.pas
输入文件
exercise.in
cell.in
fly.in
word.in
输出文件
exercise.out
cell.out
fly.out
word.out
分 值
100
100
100
100
时间限制
1s
1s
1s
1s
题一 锻炼计划(exercise.pas)
问题描述
身体是革命的本钱, OIers 不要因为紧张的学习和整天在电脑前而忽视了健康问题。小 x 设计了自己的锻炼计划,但他不知道这个计划是否可行,换句话说如果计划不当可能会让他的体力超支,所以小 x 请你帮助他。
一天有 1440 分钟,所以小 x 列出的是这一整天第 1 至第 1440 分钟的计划。小 x 的体力用一个整数来表示,他会按照计划表进行锻炼,同时,每分钟小 x 的体力会自动增加 1 。如果某一分钟末小 x 的体力小于等于零,那么可怜的小 x 就累死了 ……
输入(exercise.in)
第一行是用空格分开的两个整数 n,m ,分别表示小 x 的初始体力值和计划的项目数量。从第二行开始的 m 行,每行描述一个锻炼项目:名称、开始时间 a 、结束时间 b 、每分钟耗费的体力 ( 用空格分隔 ) ,表示此项目从第 a 分钟初开始,第 b 分钟末结束。锻炼项目按照开始时间递增顺序给出,不会出现两个项目时间冲突的情况。
输出(exercise.out)
输出包括两行,如果计划可行,第一行输出 "Accepted" ,第二行输出这一天过后最后剩余的体力;否则在第一行输出 "Runtime Error" ,第二行输出在第几分钟累死。
样例1
exercise.in
exercise.out
10 1
Basketball 1 10 1
Accepted
1440
样例2
exercise.in
exercise.out
1 1
Nunchakus 1 1 2
Runtime Error
1
数据范围
0
0) and (x<=m) and (y>0) and (y<=n) and bz[x,y]
then begin inc(tail);h[tail,1]:=x;h[tail,2]:=y;bz[x,y]:=false;end;{为细胞的入队}
end;
inc(head);{队头指针加1}
until head>tail;{直至队空为止}
end;
begin
fillchar(bz,sizeof(bz),true);num:=0;
assign(input,'cell.in');
assign(output,'cell.out');
reset(input);
rewrite(output);
readln(m,n);
for i:=1 to m do
begin readln(s);
for j:=1 to n do
begin pic[i,j]:=ord(s[j])-ord('0');
if pic[i,j]=0 then bz[i,j]:=false;
end;
end;
for i:=1 to m do
for j:=1 to n do if bz[i,j] then floodfill(i,j);{在矩阵中寻找细胞}
writeln(num);
close(input);
close(output);
end.
题三 飞翔(fly.pas)
问题描述
鹰最骄傲的就是翱翔,但是鹰们互相都很嫉妒别的鹰比自己飞的快,更嫉妒其他的鹰比自己飞行的有技巧。于是,他们决定举办一场比赛,比赛的地方将在一个迷宫之中。
这些鹰的起始点被设在一个N*M矩阵的左下角map[1,1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角,有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示:
没有障碍,也没有死路。这样设计主要是为了高速飞行的鹰们不要发现死路来不及调整而发生意外。潘帕斯雄鹰冒着减RP的危险从比赛承办方戒备森严的基地中偷来了的地图。但是问题也随之而来,他必须在比赛开始之前把地图的每一条路都搞清楚,从中找到一条到达终点最近的路。(哈哈,笨鸟不先飞也要拿冠军)但是此鹰是前无古鹰,后无来鹰的吃菜长大的鹰--菜鸟。他自己没有办法得出最短的路径,于是紧急之下找到了学OI的你,希望找到你的帮助。
输入(fly.in)
首行为n,m,第2行为k表示有多少个特殊的边。以下k行为两个数,i,j表示map[i,j]是可以直接穿越的。
输出(fly.out)
仅一行,1,1-->n,m的最短路径的长度,四舍五入保留到整数即可
样例
fly.in
fly.out
3 2
3
1 1
3 2
1 2
383
数据范围
20%的数据,0a[j+1,1]) or (a[j,2]>a[j+1,2]) then
begin
temp:=a[j,1];
a[j,1]:=a[j+1,1];
a[j+1,1]:=temp;
temp:=a[j,2];
a[j,2]:=a[j+1,2];
a[j+1,2]:=temp;
end;
end;
procedure main;
begin
for i:=1 to k do
begin
temp:=0;
for j:=0 to i do
begin
if (a[j,1]temp)
then temp:=f[j]+1;
end;
f[i]:=temp;
end;
temp:=0;
for i:=1 to k do
if f[i]>temp
then temp:=f[i];
end;
begin
init;
main;
assign(fil,'fly.out');
rewrite(fil);
writeln(fil,(m+n-2*temp+sqrt(2)*temp)*100:0:0);
close(fil);
end.
题四 单词划分(word.pas)
问题描述
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析,需要将它划分成若干个部分,每个部分称为一个单词。出于减少分析量的目的,我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。
输入(word.in)
第一行,一个字符串。(字符串的长度不超过100)
第二行一个整数n,表示单词的个数。(n<=100)
第3~n+2行,每行列出一个单词。
输出(word.out)
一个整数,表示字符串可以被划分成的最少的单词数。
样例
word.in
word.out
realityour
5
real
reality
it
your
our
2
(样例解释:原字符串可拆成real+it+your或reality+our,由于reality+our仅为两个部分,因此最优解为2,另外注意,单词列表中的每个单词都可以重复使用多次,也可以不用)
数据范围
40%的数据,字符串的长度不超过20,n<=10
100%的数据,字符串的长度不超过100,n<=100
问题分析:
设一个一维的状态数组f[i],以每个字母划分,f[i] 表示前 i 个字母最少分的单词数。
那么相应的状态转移方程就是
f[i]=min(f[i-length(word[j])]+1) (其中,word[j]=s[i-length(word[j])+1] ~s[i])
1<=i<=length(s),1<=j<=n
初值f[0]=0,f[i]=maxint(i>=1)
问题的关键还在于单词表与字符串的匹配,若单词表规模比较大,匹配的时候也会比较耗时,可以改进一下匹配的算法,以获得更高的效率。本问题的单词规模和字符串长度均不太大,直接匹配就行了。
参考程序:
program word(input, output);
var s : string;
w : array [1..100] of string;
st : array [0..100] of integer;
n, i, j : integer;
begin
assign(input, 'word.in'); reset(input);
assign(output,'word.out');rewrite(output);
readln(s);
readln(n);
for i := 1 to n do
readln(w[i]);
fillchar(st, sizeof(st), $7F);
st[0] := 0;
for i := 1 to length(s) do
for j := 1 to n do
if (length(w[j]) <= i) and (st[i - length(w[j])] +1< st[i])
and (copy(s, i - length(w[j]) + 1, length(w[j])) = w[j])
then st[i] := st[i - length(w[j])] + 1;
writeln(st[length(s)])
close(input);
close(output);
end.
本文档为【期初测试解题报告】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。