2014东莞市小学生程序设计复赛试题(题解)

第一题 滔滔吃苹果(apple.pas/c/cpp)

【问题描述】

滔滔的妈妈给滔滔买了n个苹果，每个苹果都有个好坏度K（0<=k<=100）。滔滔早就想吃苹果了，但他是个有孝心的好孩子，他想把好一些的苹果分给妈妈吃，于是他开始挑选起来:当好坏度大于50的苹果，滔滔毫不犹豫地给了妈妈，而小于或等于50的他留给了自己。但好坏度小于15的是不能吃的，滔滔不得不丢掉，请问滔滔最后能吃到几个苹果？

【输入格式】

第一行输入n，指苹果的数量。换行输入每个苹果的好坏度k，用空格隔开。 【输出格式】

一个数，表示滔滔能吃到的苹果数。 【输入样例】 10

100 45 10 3 0 56 49 50 50 68 【输出样例】 4

【数据范围】 30%的数据，n<=10; 100%的数据，n<=100; 【样例说明】

根据题意，滔滔可以吃到的苹果x，必须要满足15<=x<=50，输入中满足条件的苹果有x=45,49,50,50一共四个。 【参考程序】 var

n,i,x,s:longint; begin read(n);

for i:=1 to n do begin read(x);

if (x<=50)and(x>=15) then inc(s); end; write(s); end.

第二题 Kqp的礼物（string.pas/c/cpp)

【题目背景】

mx妹妹要过生日了!作为mx妹妹的好同（peng）学（you），kqp他要送给mx妹妹一样特别的礼物，譬如……项链！

【问题描述】

项链由前n种大写字母组成，每种字母都有不同的爱心值。 Mx妹妹已经知道了：

1、组成整个项链的所有字母串；

2、整个项链的爱心值之和m,

3、以及其中的n-1种字母所带有的爱心值a；

她想知道剩下那种字母的爱心值是多少。

【输入格式】

输入文件名为string.in,

第一行只有一个整数n；

第二行一个字母串s表示kqp的项链，长度<=1000；

第2+1～2+n-1行，每行有个大写母c和一个整数a，之前用个空格隔开,表示字母c所带的爱心值为a；

最后一行只有一个整数表示整个项链的爱心值之和m。

【输出格式】

输出文件名为string.out,

Mx妹妹想了解剩下那个字母c带有的爱心值中多少（保留2位小数）。

【输入样例】 8

CEAAGCGDHFB A 5 C 35 D 18 E 42 F 15 G 17 H 21 661

【输出样例】 451.00 【数据范围】

40%的数据，项链长度<=10,并且没有重复字母； 80%的数据，项链长度<=255,有重复字母；

100%的数据，st长度<=1000，有重复字母，n<=26。 【样例说明】

项链的字母串为CEAAGCGDHFB A=5 C=35 D=18 E=42 F=15 G=17 H=21

则原来的字母串为C(35)E(42)A(5)A(5)G(17)C(35)G(17)D(18)H(21)F(15)B(?) 项链总共爱心值=661 661-35-42-5-5-17-35-17-18-21-15=451 未知的B个数为一个，则B=451/1=451.00 【参考程序】 var

n,i,len,k,t,sum:longint; s:ansistring;

a:array['A'..'Z']of longint; c:char; begin readln(n);

readln(s); //读入字母串 for i:=1 to length(s) do

inc(a[s[i]]); //统计每个字母出现的个数，保存在a数组 len:=length(s); for i:=1 to n-1 do begin readln(c,k);

t:=t+a[c]*k; //t统计已知字母总和 len:=len-a[c]; //统计剩下字母个数 end; read(sum);

write((sum-t)/len:0:2); end.

第三题 穿越丛林(through.pas/c/cpp)

【问题描述】

ljj 是一位富有冒险心又很喜欢研究数学的孩纸，有一天，他到一个丛林冒险，这里的树长有像0、4、6、8、9这样形状的洞，他要想穿过丛林，必须从这些树洞里钻过去。这时他忽然萌生了一个特别的想法，统计穿越丛林道路的条数！现在他已经知道了要经过丛林道路所经过的n棵树的顺序，以及与每棵上的树洞的形状的数字。

【输入格式】

输入文件名为through.in。

文件第一行一个整数n，表示丛林中有洞的数的棵数。

接下来一行有n 个被空格隔开的数t[i]，表示第i 棵树长得像的数字。 【输出格式】

输出文件名为through.out。 文件只有一行，为路径条数。 【样例输入】 5 0 0 0 6 8 【样例输出】 2

【样例说明】最后一棵树的树洞长得像8，表示两个树洞，有以下两条路径可以穿越丛林,见下图：

【数据范围】 30%的数据，1<=n<=50;

60%的数据，1<=n<=500; 90%的数据，1<=n<=5000； 100%的数据，1<=n<=50000；

其中：t[i]∈(0,4,6,8,9)，即t[i]属于(0,4,6,8,9)中的某个数。 【题目分析】

根据题意，可知：只有8时有两种路径，这样就是一个乘法原理。当8的个数为s时，路径数=2的s次方。但是，因为100%的数据，1<=n<=50000，使用普通高精度必然会超时。所以可以用2的25次方*（s div 25）*2的(s mod 25)次方，这样速度就会快得多。

【样例说明】

0 0 0 6 8共有1个八，2的1次=2. 【参考程序】 var

n,i,s,x,l,j,k:longint; a:array[1..100000]of longint; begin read(n); for i:=1 to n do begin read(x); if x=8 then inc(s); end; a[1]:=1; l:=1;

for i:=1 to s div 25 do //2的25次方*（s div 25） begin

for j:=1 to l do a[j]:=a[j]*33554432; for j:=1 to l do if a[j]>=10 then begin

a[j+1]:=a[j+1]+a[j] div 10; a[j]:=a[j] mod 10; end; k:=l+10; while a[k]=0 do dec(k);

while (l<=k)or(a[l]>0) do begin

a[l+1]:=a[l+1]+a[l] div 10;

a[l]:=a[l] mod 10; l:=l+1; end; dec(l); end;

for i:=1 to s mod 25 do //2的(s mod 25)次方 begin

for j:=1 to l do a[j]:=a[j]*2; for j:=1 to l do if a[j]>=10 then begin

a[j+1]:=a[j+1]+a[j] div 10; a[j]:=a[j] mod 10; end; k:=l+2; while a[k]=0 do dec(k);

while (a[l]>0)or(l<=k) do begin

a[l+1]:=a[l+1]+a[l] div 10; a[l]:=a[l] mod 10; l:=l+1; end; dec(l); end;

for i:=l downto 1 do write(a[i]); end.

第四题 打砖块（brick.pas/c/cpp）

【问题描述】

KXT是一个很无聊的小朋友，一天到晚都在打坐......

一天，被他发现了一个比打坐更无聊的事情——打砖块。很多块砖分布在一个m*m的矩阵中，他可以消掉以他为左上角顶点的一个n*n的矩阵里的所有砖块。

喜欢偷懒的他请来了你帮他计算可以消掉最多的砖块数（只能消一次）。 【输入格式】

输入文件brick.in中，第一行：用空格隔开的三个整数n、m、k。

接下来k行，每行2个用空格隔开的整数Xi、Yi，表示第i块砖在Xi行、Yi列的位置。 【输出格式】

输出文件brick.out中，为可以消掉最多的砖块数。 【样例输入】 5 10 11 2 1 4 6 4 9 3 9 9 7 9 9 7 9 8 10 8 8 8 6 10 2

【样例输出】 6

【样例解释】

站在第4行、6列的位置，可以消除6个方块。 【数据范围】 n<=m; k<=m*m

60%：n<=70; m<=70; k<=4900

100%：n<=1000; m<=1000; k<=1000000; 【题目分析】

在m*m的矩阵中选n*n的一块区域，使砖块数量最多。可以使用前缀和，a[I,j]统计右上角前I行前j列的砖块总数，a[I+n,j+n]:=a[I,j]-a[I-n,j]-a[I,j-n]+a[I-n,j-n];

【样例解释】

如图，n*n的区域中方块最多为6个

【参考程序】

var n,m,k,i,x,y,j,max:longint;

a:array[-5..1005,-5..1005]of longint; b:array[1..1000,1..1000]of boolean; begin

read(n,m,k);

fillchar(b,sizeof(b),false); for i:=1 to k do begin

read(x,y); b[x,y]:=true; end;

for i:=1 to m do for j:=1 to m do if b[i,j] then

a[i,j]:=a[i-1,j]+a[i,j-1]-a[i-1,j-1]+1 else

a[i,j]:=a[i-1,j]+a[i,j-1]-a[i-1,j-1]; for i:=n to m do for j:=n to m do

if a[i,j]-a[i-n,j]-a[i,j-n]+a[i-n,j-n]>max then max:=a[i,j]-a[i-n,j]-a[i,j-n]+a[i-n,j-n]; write(max); end.

本文来源：https://www.bwwdw.com/article/95x6.html