2012年南京市复赛模拟测试题3(普及)
| 题目 | 地铁 | 墙壁 | 舞台 | 门票 |
| 程序名(*. pas/c/cpp) | metro | wall | drama | tickets |
| 输入文件 | metro.in | wall.in | drama.in | tickets.in |
| 输出文件 | metro.out | wall.out | drama.out | tickets.out |
| 用时 | 1s | 1s | 1s | 1s |
| 内存限定 | 128M | 128M | 128M | 128M |
第一题：地铁（metro）
【问题描述】
亚青奥会、青奥会将在2013、2014南京开幕，为了当好东道主，南京加快了地铁建设，地铁一号线、二号线均建成通车，作为信息学选手的你，很想为地铁的售票系统编制一个程序，经考察，发现两条线路中间有个换乘站，也就是这个车站是两条线的交点，第一条线路的N个车站依次用A1、A2……An表示，第二条线路的M个车站依次用B1、B2……Bm表示，再告诉你两条线路的交点站，计费的方法是：8站以内（包括8站，如A1站到A8站就算成8站），收费2元，9站至12站，收费3元，13站至16站，收费4元，16站以上5元。当然，刷公交卡是有优惠的，成人卡打95折，学生卡打5折，老人卡免费，刷卡时会产生一系列数据来反应上面的情况，从而完成计费工作。
【输入格式】
共三行，所有数据与数据之间有一个空格。
第一行是一个整数，是0表示是学生卡，是1表示是成人卡，2表示老人卡。
第二行是换乘站，分别是1、2号线的某个站点。
第三行是刷卡的数据，分别是入站名与出站名。
【输出格式】
乘车费用，精确到小数点后面两位。
【输入样例】
1
A5 B6
A2 B7
【输出样例】
1.90
样例说明：
从A2站坐到A5站，然后再到B7站，总共是5站路，收2元，成人卡0.95折，实收1.90元。
【数据规模】
N，M <= 30
【算法分析】
【我的程序】（Accepted）
2 #include<iostream>
3 #include<cstdlib>
4 #include<algorithm>
5 using namespace std;
6 int main()
7 {
8 int n,b,e,k,B,E;
9 char ch;
10 float ans;
11 freopen( " metro.in ", " r ",stdin);
12 freopen( " metro.out ", " w ",stdout);
13 scanf( " %d ",&k);
14 if(k== 2)
15 {
16 printf( " 0.00 ");
17 fclose(stdin);
18 fclose(stdout);
19 return 0;
20 }
21 cin>>ch>>b;
22 if(ch== ' A ')b+= 10;
23 else b+= 20;
24 cin>>ch>>e;
25 if(ch== ' A ')e+= 10;
26 else e+= 20;
27 if(b>e)swap(b,e);
28 cin>>ch>>B;
29 if(ch== ' A ')B+= 10;
30 else B+= 20;
31 cin>>ch>>E;
32 if(ch== ' A ')E+= 10;
33 else E+= 20;
34 if(B>E)swap(B,E);
35 n=abs(b-B)+abs(E-e)+ 1;
36 if(n<= 8)n= 2;
37 if(n>= 9&&n<= 12)n= 3;
38 if(n>= 13&&n<= 16)n= 4;
39 if(n> 16)n= 5;
40 if(k== 1)ans=n* 0.95;
41 else ans=n* 0.5;
42 printf( " %.2lf ",ans);
43 fclose(stdin);
44 fclose(stdout);
45 return 0;
46 }
【标程】
2 st1,st2:string;
3 i,x,y,A,B:integer;
4 ans,s,p:real;
5
6 begin
7 assign(input, ' metro.in ');reset(input);
8 assign(output, ' metro.out ');rewrite(output);
9 readln(n);
10 readln(st1);
11 readln(st2);
12 i:= 1;
13 while st1[i]<> ' ' do i:=i+ 1;
14 val(copy(st1, 2,i- 2),a);
15 val(copy(st1,i+ 2,length(st1)-i- 1),b);
16 if n= 0 then p:= 0.5 else if n= 1 then p:= 0.95 else p:= 0;
17 i:= 1;
18 while st2[i]<> ' ' do i:=i+ 1;
19 val(copy(st2, 2,i- 2),x);
20 val(copy(st2,i+ 2,length(st2)-i- 1),y);
21 if st2[ 1]= ' A ' then begin
22 if st2[i+ 1]= ' A ' then s:=abs(y-x)+ 1;
23 if st2[i+ 1]= ' B ' then s:=abs(x-a)+ 1+abs(y-b);
24 end
25 else begin
26 if st2[i+ 1]= ' B ' then s:=abs(y-x)+ 1;
27 if st2[i+ 1]= ' A ' then s:=abs(x-b)+ 1+abs(y-a);
28 end;
29 if s<= 8 then ans:= 2 else
30 if s<= 12 then ans:= 3 else
31 if s<= 16 then ans:= 4 else ans:= 5;
32 ans:=ans*p;
33 if p= 0 then writeln( ' 0.00 ') else writeln(ans: 0: 2);
34
35 close(input);close(output);
36 end.
第二题：墙壁(wall)
【题目描述】
青奥会场馆的墙壁是一快长N米，宽1.5m的长方形区域，现在用宽0.5m和宽1m的正方形墙砖来铺。问有多少种铺垫方案呢？
注意：1、墙砖不可重叠铺放。
2、如果长方形区域只有0.5m长，则只能用三块0.5m宽的墙砖铺，但方案数算一种。
3、长方形区域一定能用墙砖完整铺完。
4、剩下的墙砖的数量很多，足够你使用。
【输入格式】
一行，N（0.5<=N<=500）。
【输出格式】
一行，方案数。
【样例输入】
1
【样例输出】
3
| |||||
| |||||
|
|
|
|
|
|
|
|
|
方案① 方案② 方案③
方案① 用一块1×1铺上面和二块0.5×0.5铺下面
方案② 用6块0.5×0.5铺满
方案③ 用二块0.5×0.5铺上面，1×1铺下面
【算法分析】先将N扩大2倍，再取整。
当然要采用高精度了。
oeis规律地址：http://oeis.org/A001045
【吐槽】
规律找错了，找成 F(n)=F(n-1)+F(n-2)+1（N>=3）
了我去
【标程】
2 var
3 a1,a,b,c: array[ 1..max] of integer ;
4 s,n,i,g,j:longint;
5 n0:real;
6
7 begin
8 assign(input, ' wall.in ');
9 reset(input);
10 assign(output, ' wall.out ');
11 rewrite(output);
12 readln(n0);
13 n:=trunc(n0* 2);
14 a[max]:= 1; b[max]:= 3;
15
16 for i:= 3 to n do
17 begin
18 fillchar(a1,sizeof(a1), 0);
19 g:= 0;
20 for j:=max downto 1 do
21 begin
22 s:=a[j]* 2+g;
23 a1[j]:=s mod 10;
24 g:=s div 10
25 end;
26 g:= 0;
27 for j:=max downto 1 do
28 begin
29 s:=a1[j]+b[j]+g;
30 c[j]:=s mod 10;
31 g:=s div 10
32 end;
33 a:=b; b:=c;
34 end;
35 if n= 1 then writeln( 1) else
36 if n= 2 then writeln( 3)
37 else begin
38 i:= 1;
39 while c[i]= 0 do inc(i);
40 for j:=i to max do
41 write(c[j]); end;
42 close(input);
43 close(output);
44 end.
第三题: 舞台(TYVJ1939)
(drama.pas/c/cpp)
【问题描述】
青奥会开幕式表演的舞台需要足够的空间，这样才可以挤得下尽可能多的观众。现选择了一个可以看做一个N*M个格子的矩形的地方，每个格子中标着“R”或“F”，分别表示该格有建筑物或该格为平地可以使用。现希望舞台能够表演在一块矩形的只包含平地的区域上，并且希望其面积最大。
请你帮助找出面积最大的那块只含平地的矩形，输出其面积。
【输入格式】
输入文件第一行包含了两个整数分别表示N,M。
接下来N行，每行包含M个用空格隔开的字符“F”或“R”，描述了地形。
【输出格式】
输出文件包含且仅包含一行，一个整数表示最大的矩形面积。
【样例】
| drama.in | drama.out |
| 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F | 15 |
【数据规模】
对于50%的数据，1<=N,M<=200
【算法分析】
Ans:=max{(r[j]-L[j]-1)*b[j] }
【我的程序】
2 #include<algorithm>
3 #include<cstring>
4 #include<iostream>
5 #define rep(a,b,c) for(int a=b;a<=c;++a)
6 #define max 1010
7 int t,n,m,map[max][max],heght[max][max],l[max][max],r[max][max];
8 using namespace std;
9 int main()
10 {
11 freopen( " drama.in ", " r ",stdin);
12 freopen( " drama.out ", " w ",stdout);
13 char ch;
14 scanf( " %d%d ",&m,&n);
15 memset(heght, 0, sizeof(heght));
16 for( int i= 1;i<=m;++i)
17 for( int j= 1;j<=n;++j)
18 {
19 cin>>ch;
20 if(ch== ' F '){map[i][j]= 1;heght[i][j]=heght[i- 1][j]+ 1;}
21 else {map[i][j]= 0;heght[i][j]= 0;}
22 }
23 rep(i, 1,m){heght[i][ 0]=- 1;heght[i][n+ 1]=- 1;}
24 int res= 0;
25 for( int i= 1;i<=m;++i)
26 for( int j= 1;j<=n;++j)
27 {
28 if(heght[i][j]>heght[i][j- 1]){l[i][j]=j- 1;}
29 else
30 {
31 int tmp=j- 1;
32 i=i;
33 j=j;
34 while(heght[i][j]<=heght[i][tmp])tmp=l[i][tmp];
35 l[i][j]=tmp;
36 }
37 }
38 for( int i= 1;i<=m;++i)
39 for( int j=n;j>= 1;--j)
40 {
41 if(heght[i][j]>=heght[i][j+ 1]){r[i][j]=j+ 1;}
42 else{
43 int tmp=j+ 1;
44 while(heght[i][j]<=heght[i][tmp])tmp=r[i][tmp];
45 r[i][j]=tmp;
46 }
47 if((r[i][j]-l[i][j]- 1)*heght[i][j]>res)res=(r[i][j]-l[i][j]- 1)*heght[i][j];
48 }
49 printf( " %d ",res);
50 fclose(stdin);
51 fclose(stdout);
52 return 0;
53 }
【标程】
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 using namespace std;
6 int n,m,a[ 2000];
7 int map[ 2000][ 2000],l[ 2000],r[ 2000];
8 int main()
9 {
10 freopen( " drama.in ", " r ",stdin);
11 freopen( " drama.out ", " w ",stdout);
12 scanf( " %d%d ",&n,&m);getchar();
13 memset(map, 0, sizeof(map));
14 for( int i= 1;i<=n;i++)
15 {
16 for( int j= 1;j<=m;j++)
17 {
18 char c=getchar();
19 if(c== ' F ')map[i][j]= 1;
20
21 c=getchar();
22 if(j==m)
23 {
24 while(c== ' ')c=getchar();
25 }
26 }
27 }
28
29
30
31 int ans= 0;memset(a, 0, sizeof(a));
32 for( int i= 1;i<=n;i++)
33 {
34 for( int j= 1;j<=m;j++)
35 if(map[i][j]== 1)a[j]++;
36 else a[j]= 0;
37
38 a[ 0]=a[m+ 1]=- 1;
39
40 l[ 1]= 0;
41 for( int j= 2;j<=m;j++)
42 {
43 l[j]=j- 1;
44 while(a[l[j]]>=a[j])l[j]=l[l[j]];
45 }
46
47 r[m]=m+ 1;
48 for( int j=m- 1;j>= 1;j--)
49 {
50 r[j]=j+ 1;
51 while(a[r[j]]>=a[j])r[j]=r[r[j]];
52 }
53
54 for( int j= 1;j<=m;j++)
55 {
56 int c=(r[j]-l[j]- 1)*a[j];
57 ans=max(ans,c);
58 }
59 }
60 cout<<ans<<endl;
61 return 0;
62
63 }
2 map: array[ 0.. 2000, 0.. 2000] of boolean;
3 a,L,r: array[ 0.. 2000] of longint;
4 s:ansistring;
5 begin
6 assign(input, ' drama.in ');
7 assign(output, ' drama.out ');
8 reset(input);rewrite(output);
9 readln(n,m);
10 for i:= 1 to n do
11 begin
12 readln(s); j:= 0;
13 for k:= 1 to length(s) do
14 if (s[k]= ' R ') or (s[k]= ' F ') then
15 begin
16 inc(j);
17 if s[k]= ' R ' then map[i,j]:=false else map[i,j]:=true;
18 end;
19 end;
20
21 for i:= 1 to n do
22 begin
23 for j:= 1 to m do
24 if map[i,j] then a[j]:=a[j]+ 1 else a[j]:= 0;
25 a[ 0]:=- 1; a[m+ 1]:=- 1;
26
27 L[ 1]:= 0;
28 for j:= 2 to m do
29 begin
30 L[j]:=j- 1;
31 while a[l[j]]>=a[j] do l[j]:=l[l[j]];
32 end;
33
34 r[m]:=m+ 1;
35 for j:=m- 1 downto 1 do
36 begin
37 r[j]:=j+ 1;
38 while a[r[j]]>=a[j] do r[j]:=r[r[j]];
39 end;
40
41 for j:= 1 to m do
42 begin
43 c:=(r[j]-L[j]- 1)*a[j];
44 if c>ans then ans:=c;
45 end;
46 end;
47 writeln(ans);
48 close(input);
49 close(output);
50 end.
第四题：门票(tickets )
【问题描述】：
青奥会吉祥物“中华曙猿”近日在河西分校亮相，接下准备进行开幕式门票的销售，假设售票点前聚集了N个人购买门票。
有M组出现第X个人帮助第Y个人买票(X可以等于Y，此时第X个人可以给自己买票)，这时消耗时间W[X,Y]（1<=W[x,y]<=20000）。
当然，这种帮助是相互的，也就是说如果第Y个人帮助第X个人买票，也将花费W[X,Y]个单位时间。
注意：
1.每个人帮助别人买票的时候必须要求自己已经购得开幕式门票。
2.X帮Y买票的时间有可能多次出现，必须从中选择较小的。
求解这N个人购买票的最短时间和，对于每个数据都保证N个人都获得开幕式门票。
【输入格式】：
第一行两个正整数分别为N,M；
以后M行，每行三个正整数X,Y,W[X,Y]；
【输出格式】：
一行一个整数，为N个人都购得开幕式门票的最短时间，这个时间<=50000.
【样例输入】：
3 5
1 1 5
2 2 2
2 1 4
3 3 3
3 2 6
【样例输出】：
9
【样例解释】：
第2个人给自己买票花费2个单位时间，然后第3个人给自己买票花费3个单位时间，最后第2个人给第1个人买票花费4个单位时间，总共花费9个单位时间。
【数据范围】：
对于30%的数据保证N<=10,M<=100；
对于100%的数据保证N<=2000,M<=12000；
【算法分析】：
【吐槽】
完全忘了怎么写，直接打了一个骗分的（非暴力，此题卡暴力），结果骗了10分，这是一道原题，我就不说在哪了- -
【标程】
2 #include<cstdio>
3 #include<iostream>
4 #include<cstring>
5 int a[ 2001][ 2001],d[ 2001],n,m;
6 bool b[ 2001];
7 void prim()
8 {
9 int i,j,min,p,ans= 0;
10 memset(b, false, sizeof(b));
11 memset(d, 100, sizeof(d));
12 for (i= 1;i<=n;++i)
13 d[i]=a[i][i];
14 for (i= 1;i<=n;++i)
15 {
16 min=d[ 0];
17 for (j= 1;j<=n;++j)
18 if ((d[j]<min)&&(b[j]== false))
19 {
20 min=d[j];
21 p=j; }
22 b[p]= true;
23 ans=ans+min;
24 for (j= 1;j<=n;++j)
25 if ((b[j]== false)&&(a[p][j]<d[j]))
26 d[j]=a[p][j];
27 }
28 if (ans>d[ 0]) printf( " Can't\n ");
29 else
30 printf( " %d\n ",ans);
31 }
32 int main()
33 {
34 int i,x,y,w;
35 freopen( " tickets.in ", " r ",stdin);
36 freopen( " tickets.out ", " w ",stdout);
37 memset(a, 100, sizeof(a));
38 scanf( " %d%d\n ",&n,&m);
39 for (i= 1;i<=m;++i)
40 {
41 scanf( " %d%d%d\n ",&x,&y,&w);
42 if (w<a[x][y])
43 {
44 a[x][y]=w;
45 a[y][x]=w;
46 }
47 }
48 prim();
49 return 0;
50 }
2 d,b: array[ 0.. 2001] of longint;
3 min,p,ans,n,m,i,j,x,y,z:longint;
4
5 begin
6 assign(input, ' tickets.in '); reset(input);
7 assign(output, ' tickets.out '); rewrite(output);
8 readln(n,m);
9 for i:= 1 to n do
10 for j:= 1 to n do
11 a[i,j]:=maxlongint;
12 for i:= 1 to m do
13 begin
14 readln(x,y,z);
15 if a[y,x]>z then begin
16 a[y,x]:=z;
17 a[x,y]:=z; end;
18 end;
19
20 for i:= 1 to n do b[i]:=a[i,i];
21
22 for i:= 1 to n do
23 begin
24 min:=maxlongint;
25 for j:= 1 to n do
26 if (b[j]<min) and (d[j]= 0) then begin
27 min:=b[j];
28 p:=j
29 end;
30 d[p]:= 1;
31 ans:=ans+min;
32 for j:= 1 to n do
33 if (d[j]= 0) and (a[p,j]<b[j]) then b[j]:=a[p,j];
34 end;
35
36 writeln(ans);
37 close(input);
38 close(output);
39 end.
