慈溪市小学生计算机程序设计竞赛复赛试题解题报告Word文件下载.docx
《慈溪市小学生计算机程序设计竞赛复赛试题解题报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《慈溪市小学生计算机程序设计竞赛复赛试题解题报告Word文件下载.docx（14页珍藏版）》请在冰点文库上搜索。
1021
【样例1解释】
输入的黑白图片的大小为6行6列，第1行0个黑色方格，第2行3个黑色方格，第3行2个黑色方格，第4行2个黑色方格，第5行3个黑色方格，第6行0个黑色方格。
所以总共有10个黑色方格，黑色方格最多且行号最小的行是第2行，黑色方格最少且行号最小
的行是第1行。
【输入输出样例2】
1718
111111001100111111
111110110011011111
111111000000111111
111100111111001111
111011111111110111
110111111111111011
110111011110111011
100111111111111001
011111111111111110
011111101101111110
011111110011111110
101111111111111101
110111110011111011
6035
【样例2解释】
样例2如题目描述。
【数据范围约定】
所有的输入数据保证1≤n,m≤100。
【问题分析】
给出一张黑白图片，输出黑色方格的总数，黑色方格数目最多的行的行号及黑色方格数目最少的行的行号。
具体见【问题描述】。
【算法分析】
直接模拟，枚举每一行。
【参考程序】
varn,m,max,min,v1,v2,i,j,x,s,tot:
longint;
begin
assign（input,'
count.in'
）;
reset（input）;
assign（output,'
count.out'
rewrite（output）;
max:
=-1;
min:
=101;
read（n,m）;
fori:
=1tondo
begin
s:
=0;
forj:
=1tomdo
read（x）;
ifx=0then
inc（s）;
inc（tot）;
end;
ifs>
maxthen
max:
=s;
v1:
=i;
ifs<
minthen
v2:
writeln（tot,'
'
v1,'
v2）;
close（input）;
close（output）;
end.
2．转圈游戏（circle.pas）
n个小朋友（小朋友从0到n-1进行编号）围坐一圈玩游戏。
按照顺时针方向依次给n
个位置编号，也是从0到n-1。
最初，第0号小朋友在第0号位置，第1号小朋友在第1号
位置，……，依此类推。
游戏规则如下：
每一轮给出两个整数a、b。
若a的值等于1，则所有小朋友依次逆时针转b个位置；
若a的值等于2，则所有小朋友依次顺时针转b个位置。
比如：
a=2，b=3，那么第0号位置上的小朋友顺时针转到第3号位置，第1号位置上的小朋友顺时针转到第4号位置，……，第n-3号位置上的小朋友顺时针转到第0号位置，第n-2号位置上的小朋友顺时针转到第1号位置，第n-1号位置上的小朋友顺时针转到第2号位置，一轮转圈结束。
依照上面的游戏规则，请问进行q轮后，第0到n-1号位置上的小朋友的编号分别是什么？
输入文件circle.in：
输入从文件中读取，输入共q+1行。
第1行是两个整数n和q（1≤n≤100000,0≤q≤200000），表示n个小朋友要进行q轮转圈游戏，两个整数间用空格分隔。
第2行到第q+1行，每行两个用空格分隔的整数。
其中第i+1行两个整数为ai和bi（ai=1
或者ai=2,0≤bi≤n-1），表示第i轮转圈的信息。
若ai=1，则所有小朋友依次向逆时针
方向转bi个位置，若ai=2，则所有小朋友依次向顺时针方向转bi个位置。
输出文件circle.out：
输出共n行，每行包含一个整数，第i行整数表示经过转圈后第i-1号位置上的小朋友的编号。
circle.in
41
23
circle.out
1
2
3
【样例1解释】
4个小朋友参加转圈游戏，转圈共进行了1轮，在这轮转圈游戏中，所有小朋友依次向顺时针方向转了3个位置，第0号小朋友转到第3号位置，第1号小朋友转到了第0号位置，第2号小朋友转到了第1号位置，第3号小朋友转到了第2号位置，所以最后第0号位置到第3号位置上的小朋友编号分别是1，2，3，0。
53
11
22
13
4
【样例2解释】
5个小朋友参加转圈游戏，转圈共进行了3轮。
在第1轮转圈游戏中，所有小朋友依次向逆时针方向转了1个位置。
在第2轮转圈游戏中，所有小朋友依次向顺时针方向转了2个位置。
在第3轮转圈游戏中，所有小朋友依次向逆时针方向转了3个位置。
所以最后第0号位置到第4号位置上的小朋友编号分别是2，3，4，0，1。
对于70%的数据，1≤n≤1000，0≤q≤2000。
对于100%的数据，1≤n≤100000，0≤q≤200000。
求n个人按输入规则进行q轮转圈后，每个位置上的人对应的编号。
模拟，只要统计出每个人最后相当于逆时针转了多少距离即可。
varx,i,v,n,m,a,b:
circle.in'
circle.out'
read（a,b）;
ifa=1thenv:
=（v-b）modnelsev:
=（v+b）modn;
=0ton-1do
x:
=（i-v）modn;
whilex<
0dox:
=x+n;
writeln（x）;
3．排队（queue.pas）
【问题描述】
按身高排队是我们最常用的一种排队方法，一伙小朋友已经非常厌倦了这种排队方式，这次他们打算按每个人的姓名排队，但如果按照姓名的字典序进行排队似乎有点麻烦，所以他们找了一种比较简单的排队方法：
根据姓名的长度进行排队，姓名长的排在最前面，姓名短的排在最后面。
姓名的长度他们有这样的约定：
每个人的姓名只能由“a”（ASCII码为97）到“z”（ASCII码为122）这26个小写英文字母构成，姓名的长度就是姓名中字母的总个数。
由于小朋友人数比较多，请根据他们的排队方法，编程帮助他们排队吧！
【输入数据】
输入文件queue.in：
第1行是一个整数n（1≤n≤15000），表示总共有n个小朋友参加排队（编号为1到n）。
第2行到第n+1行，每行一个字符串，其中第i+1行表示第i个小朋友的姓名，数据保证每个小朋友都有姓名，并且姓名的长度不超过255。
【输出数据】
输出文件queue.out：
输出共n行，表示经过排队后的小朋友的姓名情况，姓名长的先输出，姓名短的后输出。
注意，当小朋友的姓名长度一样时，输出的顺序同输入的顺序（参考样例解释）。
【输入输出样例】
queue.in
aoteman
guaishou
jiqiren
queue.out
【样例解释】
有3个小朋友参加了排队，第1个小朋友的姓名长度为7，第2个小朋友的姓名长度为8，第3个小朋友的姓名长度为7。
因为第2个小朋友的姓名最长，所以最先输出，第1个小朋友和第3个小朋友的姓名长度都为7，但在输入中，小朋友“aoteman”在小朋友“jiqiren”的前面，所以先输出“aoteman”，然后输出“jiqiren”。
60%的输入数据保证1≤n≤1000，且每个小朋友的姓名长度不超过100。
80%的输入数据保证1≤n≤8000，且每个小朋友的姓名长度不超过255。
100%的输入数据保证1≤n≤15000，且每个小朋友的姓名长度不超过255。
给出一些字符串，按要求进行排序。
排序，可采用双关键字快排。
varn,i:
a,b:
array[1..15000]oflongint;
array[1..15000]ofstring;
proceduresort（l,r:
longint）;
vari,j,t,mid,m:
i:
=l;
j:
=r;
mid:
=a[（i+j）div2];
m:
=b[（i+j）div2];
repeat
while（a[i]>
mid）or（a[i]=mid）and（b[i]<
m）doinc（i）;
while（a[j]<
mid）or（a[j]=mid）and（b[j]>
m）dodec（j）;
ifI<
=jthen
t:
=a[i];
a[i]:
=a[j];
a[j]:
=t;
=b[i];
b[i]:
=b[j];
b[j]:
inc（i）;
dec（j）;
untili>
j;
ifl<
jthensort（l,j）;
ifi<
rthensort（i,r）;
end;
queue.in'
queue.out'
readln（n）;
readln（s[i]）;
=length（s[i]）;
sort（1,n）;
writeln（s[b[i]]）;
4.寻找子矩阵（matrix.pas）
一个由n行m列构成的矩阵（从上到下对行1到n编号，从左到右对列1到m编号），
第i行第j列中有一个正整数Wij。
例如下面是一个3行4列的矩阵。
现在从中选取一个p行q列的子矩阵，例如下面黑框中选取的是一个2行3列的子矩阵。
仔细观察会发现，从上面的矩阵中选取2行3列的子矩阵共有4种不同的方法。
现在请你找这样一个子矩阵，满足以下条件：
将子矩阵的q列从左到右编号为1到q，删除子矩阵中所有编号为奇数的列，或者删除子矩阵中所有编号为偶数的列，然后用子矩阵中剩下的数之和减掉子矩阵中被删除的数之和，得到一个结果S，S最大的子矩阵就是我们要找的子矩阵，注意，这样的子矩阵可能有多个。
例如上面黑框中的子矩阵，删除编号为奇数的列（下图1）或删除编号为偶数的列（下图2）。
（阴影部分为删除的列）
按照计算规则，图1中剩下的数之和为8，被删除的数之和为9，所以S=－1，图2中剩下的数之和为9，被删除的数之和为8，所以S=1，也就是说当选择这个子矩阵时，S的最大值为1。
当然可以选择其他子矩阵来获取更大的S。
输入文件matrix.in：
第一行包含4个整数n、m、p、q（1≤n，m≤1000，1≤p≤n，1≤q≤m），每两个整数之间用一个空格隔开。
接下来n行，每行包含m个整数。
第i+1行的第j个整数为Wij（1≤Wij≤100），表示矩
阵中的第i行第j列的数，每两个整数之间用一个空格隔开。
输出文件matrix.out：
输出共一行，包含一个整数，表示最大的S。
注意不需要输出你选择的子矩阵。
matrix.in
3423
1523
2342
8243
matrix.out
13
【样例解释】
当选择如下子矩阵时，S的值为13，满足最大。
【数据范围约定】
对于30%的数据保证1≤n≤50，1≤m≤50。
对于70%的数据保证1≤n≤300，1≤m≤300。
对于100%的数据保证1≤n≤1000，1≤m≤1000。
另外，所有的数据保证1≤p≤n，1≤q≤m，1≤Wij≤100。
给出一个二维矩阵，要求从中选取一个p行q列的子矩阵，使奇数列的和与偶数列的和
的差最大。
对于30%的数据，暴力枚举，时间复杂度为O（n*m*p*q）。
对于70%的数据，用前缀和进行优化，然后进行暴力枚举，时间复杂度为O（n*m*q）。
对于100%的数据，用前缀和进行优化，进行枚举时，不暴力求值，因为只要把左边那列去掉，把右边那列加上即可，时间复杂度为O（n*m）。
var
n,m,p,q,i,j,s1,s2,ans:
a:
array[0..1000,1..1000]oflongint;
assign（input,'
matrix.in'
assign（output,'
matrix.out'
read（n,m,p,q）;
fori:
read（a[i,j]）;
a[i,j]:
=a[i,j]+a[i-1,j]
=1ton-p+1do
s1:
s2:
=1toqdo
ifodd（j）then
=s1+a[i+p-1,j]-a[i-1,j]
else
=s2+a[i+p-1,j]-a[i-1,j];
ifabs（s1-s2）>
ansthen
ans:
=abs（s1-s2）;
=q+1tomdo
ifodd（j-q）then
=s1-a[i+p-1,j-q]+a[i-1,j-q]
=s2-a[i+p-1,j-q]+a[i-1,j-q];
=abs（s1-s2）
end
writeln（ans）;
close（input）;
close（output）
升级会员 