noip复赛模拟练习29答案.docx
《noip复赛模拟练习29答案.docx》由会员分享，可在线阅读，更多相关《noip复赛模拟练习29答案.docx（15页珍藏版）》请在冰点文库上搜索。
noip复赛模拟练习29答案
辉辉、姗姗和佳佳是好朋友，他们一起参加了在湖南长沙长郡中学举办的第二十一届全国青少年信息学奥林匹克竞赛（NOI2004）。
他们很早就来到了长沙，可是报名还没有开始。
怎么办呢？
他们决定分头出去玩一天，晚上回到宿舍以后给大家说说自己这一天做了什么有意义的事情。
你一定想不到辉辉干嘛去了——他睡了一天。
他想：
“比赛前几天老是写程序到深夜，头晕晕的……没关系，好好睡一觉，然后我会精神抖擞。
醒了之后，我要做有意义的事情。
”这一睡可不得了，辉辉从早上a点b分c秒一直睡到了下午d点e分f秒。
他睡了多少秒钟呢？
六个非负整数a,b,c,d,e,f（1<=a,d<=11,0<=b,c,e,f<=59）。
例如，a=6,b=5,c=4,d=3,e=2,f=1表示辉辉从06:
05:
04睡到15:
02:
01。
【样例输入】
654321
【样例输出】
32217
vara,b,c,d,e,f:
longint;
begin
readln（a,b,c,d,e,f）;
d:
=d+12;
writeln（（d*3600+e*60+f）-（a*3600+b*60+c））;
readln
end.
将a,b,c,……n个字符,按顺时针方向排成一圈，然后从任意位置开始按顺时针方向连续取k个字符组成一个k位字符串。
（kn=3k=2按顺时针方向排成如下一圈：
a
cb
此时，可组成：
ab，bc，ca。
当给出n,k后，输出n个k位字符串
输入：
nk输出：
n个k位字符串
输入输出样例:
输入：
54输出：
abcd
bcde
cdea
deab
eabc
varn,k,i,j,a,b:
longint;
beginreadln（n,k）;
fori:
=1tondo
begin
a:
=i;b:
=0;
forj:
=1tokdo
begin
write（chr（96+a））;
ifa+1<>nthena:
=（a+1）modn
elsea:
=n;
end;
writeln;
end;
readln;
end.
问题描述：
计算机软件版本通常被用来区分某种软件在不同时间的发布。
大部分软件版本号都是用“.”分隔的非负数的序列。
对两个不同的版本A=a1.a2.a3…an和B=b1.b2.b3…bm，如果下面两个条件之一成立，我们认为版本A要比版本B新：
1．对某个i，我们有：
对所有jbi和aj=bj；
2．n比m大，而且对所有i（ai和bi都不超过LONGINT）
在这个问题里，你要对给定的一组版本号，按照上面的定义从旧到新排序。
输入文件（VERSIONS.IN）：
输入文件第一行是一个整数N（N<=20），表示要排序的版本数。
接下来的N行每行一个版本号。
每个版本号是长度不超过50的字符串。
输出文件（VERSIONS.OUT）：
将排好序的结果以每行一个版本号输出。
输入输出样例：
VERSIONS.IN
4
3.0.5
1
2.4
2.4.6
VERSIONS.OUT
1
2.4
2.4.6
3.0.5
varn,i:
integer;
scan:
array[1..30]ofstring;
functioncheck（aa,bb:
string）:
boolean;
var
a,b:
longint;
i,j:
integer;
code:
integer;
begin
aa:
=aa+'.';bb:
=bb+'.';
i:
=pos（'.',aa）;j:
=pos（'.',bb）;
while（i>0）and（j>0）dobegin
val（copy（aa,1,i-1）,a,code）;
val（copy（bb,1,j-1）,b,code）;
ifaifa>bthenexit（false）;
delete（aa,1,i）;
delete（bb,1,j）;
i:
=pos（'.',aa）;
j:
=pos（'.',bb）;
end;
if（i=0）and（j>0）thenexit（true）elseexit（false）;
end;
procedureqsort（l,r:
integer）;
var
i,j:
integer;
t:
string;
begin
ifl>=rthenexit;
i:
=random（r-l）+l;
t:
=scan[i];scan[i]:
=scan[l];
i:
=l;j:
=r;
repeat
while（iifi=jthenbreak;scan[i]:
=scan[j];
while（iifi=jthenbreak;scan[j]:
=scan[i];
untili=j;
scan[i]:
=t;
qsort（l,i-1）;
qsort（i+1,r）;
end;
begin
readln（n）;
fori:
=1tondoreadln（scan[i]）;
qsort（1,n）;
fori:
=1tondowriteln（scan[i]）;
end.
上学路线（route．pas／c／cpp）
【题目描述】
你所在城市的街道好像一个棋盘，有a条南北方向的街道和b条东西方向的街道。
南北方向的a条街道从西到东依次编号为l到a，而东西方向的b条街道从南到北依次编号为l到b，南北方向的街道i和东西方向的街道j的交点记为（i，j）。
你住在（1，1）处，而学校在（a，b）处，你骑自行车去上学，自行车只能沿着街道走，而且为了缩短时间只允许沿着向东和北的方向行驶。
现在有N个交叉路口在施工（X1，Yl）、（X2，Y2）……，（Xn，Yn），这些路口是不能通车的。
问你上学一共有多少走法?
【输入格式】
第一行包含两个整数a和b，并且满足1≤a，b≤16。
第二行包含一个整数N，表示有N个路口在维修（1≤N≤40）。
接下来N行，每行两个整数X_i，Y_i，描述路口的位置。
【输出格式】
输出一个整数表示从（1，1）到（a，b）的行车路线总数。
【样例输入输出】
Route．in
Route．out
54
3
22
23
42
5
【样例数据解释】
JOIHighSchool
（5,4）
（1,1）
Taro’sHome
题解：
1、递推，设F[I,J]表示从（1，1）到（i,j）的方法数，根据考虑最后一步是如何走的，
分两种情况：
（1）最后一步由（i-1,j）向东走过去，方法数是f[I-1,J]
（2）最后一步由（i,j-1）向北走过去，方法数是f[I,J-1]
当然，如果（i,j）处在施工，那么F[I,J]=0.
综上所述得到如下递推式：
F[I,J]={
（1）（I,J）在施工：
f[I,J]=0；
（2）（i,j）没有施工：
F[I,J]=F[I-1,J]+F[I,J-1];
边界条件为F[1,1]=1;
【标程】
programgfj;
vari,j,n,m:
longint;
a,b:
array[-1..52,-1..20]oflongint;
procedureinit;
vari,l,x,y:
longint;
begin
readln（n,m）;
readln（l）;
fillchar（a,sizeof（a）,0）;
fillchar（b,sizeof（b）,0）;
fori:
=1toldo
begin
readln（x,y）;
b[x,y]:
=maxlongint;
end;
end;
begin
assign（input,'route.in'）;
reset（input）;
assign（output,'route.out'）;
rewrite（output）;
init;
fori:
=1tondo
begin
ifb[i,1]=maxlongintthenbreak;
a[i,1]:
=1;
end;
fori:
=1tomdo
begin
ifb[1,i]=maxlongintthenbreak;
a[1,i]:
=1;
end;
fori:
=2tondo
forj:
=2tomdo
ifb[i,j]<>maxlongintthena[i,j]:
=a[i-1,j]+a[i,j-1];
writeln（a[n,m]）;
close（input）;
close（output）;
end.
遗址（ruin．pas／c／cpp）
【题目描述】
很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，由4个角上竖立的圆柱搭建而成。
现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。
写一个程序，给出圆柱的坐标，找出由4个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。
注意正方形的边不一定平行于坐标轴。
例如右上图有l0根柱子，其中（4，2），（5，2），（5，3），（4，3）可以形成一个正方形，（1，1），（4，O），（5，3），（2，4）也可以，后者是其中最大的，面积为l0。
【输入格式】
第一行包含一个N（1≤N≤3000），表示柱子的数量。
接下来N行，每行有两个空格隔开的整数表示柱子的坐标（坐标值在0到5000之间），柱子的位置互不相同。
【输出格式】
如果存在正方形，输出最大的面积，否则输出0。
【样例输入输出】
Ruin．in
Ruin．out
10
94
43
11
42
24
58
40
53
05
52
10
【数据范围】
30％满足：
1≤N≤100
60％满足：
1≤N≤500。
枚举两个点（X1,Y1）,（X2,Y2）,易得
X2-X1=Y3-Y1Y3=Y1+（X2-X1）
Y2-Y1=X1-X3X3=X1-（Y2-Y1）
（X3,Y3）求出以后，可根据同样的方法求出（X4,Y4）
X1+X4=X2+X3
Y1+Y4=Y2+Y3
从而求出（X4,Y4），再判断（X3,Y3）,（X4,Y4）是否存在即可
【标程】
programruin;
Varn,x1,x2,y1,y2,i,j,dx,dy:
word;
x,y:
array[1..3000]ofword;
b:
array[0..5000,0..5000]ofboolean;
s,max:
longint;
Begin
assign（input,'ruin.in'）;
reset（input）;
assign（output,'ruin.out'）;
rewrite（output）;
max:
=0;
readln（n）;
fillchar（b,sizeof（b）,false）;
Fori:
=1tondo
begin
readln（x[i],y[i]）;
b[x[i],y[i]]:
=true;
end;
Fori:
=1ton-1do
begin
forj:
=i+1tondo
begin
s:
=sqr（x[j]-x[i]）+sqr（y[j]-y[i]）;
ifs>maxthen
begin
y1:
=y[i]+x[j]-x[i];
x1:
=x[i]-y[j]+y[i];
x2:
=x1+x[j]-x[i];
y2:
=y1+y[j]-y[i];
if（x1>=0）and（x2>=0）and（y1>=0）and（y2>=0）and（x1<=5000）and（x2<=5000）and（y1<=5000）and（y2<=5000）andb[x1,y1]andb[x2,y2]then
max:
=s
end;
end;
end;
writeln（max）;
close（input）;
close（output）;
End.
最轻的天平（mobile．pas／c／cpp）
【题目描述】
天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情况和它们之间的连接关系，要求使得所有天平都能平衡所需物品的总重量最轻，一个天平平衡当且仅当“左端点的重量*左端点到支点的距离=右端点的重量*右端点到支点的距离”。
注意题目中的输入保证这些天平构成一个整体。
【输入格式】
第一行包含一个N（N≤100），表示天平的数量，天平编号为l到N，接下来包含N行描述天平的情况，每行4个整数P、Q、R、B，P和Q表示横杆上支点到左边的长度与到右边的距离的比例为P：
Q，R表示左边悬挂的情况，如果R=0说明悬挂的是物品，否则表示左边悬挂的是天平R；B表示右边的悬挂情况，如果B=O表示右边悬挂的是物品，否则右边悬挂着天平B。
对于所有的输入，保证W*L<2^31，其中w为最轻的天平重量，而L为输入中描述左右比例时出现的最大值。
【输出格式】
输出一个整数表示使得所有天平都平衡所需最轻的物品总重量。
递归
要想一个天平平衡，首先要使得左右天平两边平衡。
假设左右两边的最轻重量
分别为W1,W2，设该天平左右两边的比例为L1:
L2，要想使得该天平衡，可能左边要放大倍数
X，右边要放大倍数Y，则有以下关系式：
W1*X*L1=W2*L2*Y;
即X/Y=（W2*L2）/（W1*L1）,要想使天平重量最小，必须把X/Y化为最简分数，所以需要求出
W2*L2和W1*L1的最大公约数P，则X=W2*L2DIVP，Y=W1*L1DIVP，整个天平的重量为
W1*X+W2*Y
【标程】
programhjd;
vari,ro,n:
longint;
p,q,l,r:
array[1..100]oflongint;
f:
array[1..100]ofboolean;
functiongcd（x,y:
longint）:
longint;
begin
ify=0thengcd:
=x
elsegcd:
=gcd（y,xmody）;
end;
functionss（x:
longint）:
longint;
varle,ri,g:
int64;
begin
ifx=0thenss:
=1
else
begin
le:
=ss（l[x]）;
ri:
=ss（r[x]）;
g:
=gcd（ri*q[x],le*p[x]）;
ss:
=le*（ri*q[x]divg）+ri*（p[x]*ledivg）;
end;
end;
begin
assign（input,'mobile.in'）;
reset（input）;
assign（output,'mobile.out'）;
rewrite（output）;
fillchar（f,sizeof（f）,false）;
readln（n）;
fori:
=1tondo
begin
readln（p[i],q[i],l[i],r[i]）;
ifl[i]<>0thenf[l[i]]:
=true;
ifr[i]<>0thenf[r[i]]:
=true;
end;
fori:
=1tondo
ifnotf[i]then
begin
ro:
=i;
break;
end;
writeln（ss（ro））;
close（input）;
close（output）;
end.
升级会员 