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

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.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2014东莞市小学生程序设计复赛试题(题解)(2)在线全文阅读。