蓝桥杯 2020年省赛真题 10月第二场 (Java 大学B组)

我是C组的，不过对比一下题目录，大致上也只有三两题的不同

就过程而言，我认为我是爆炸性的。当然，结果也是如此

先挂，自闭会

#A 门牌制作

本题总分：5 分

问题描述

小兰想为一条街的居民制作门牌号。

这条街一共有 2020 住户，门牌号从 1 到 2020 编号。

小蓝制作门牌的方法是先制作门牌 0 到 9 这些数字符最终根据需要将字符

贴在门牌上的符号，比如门牌 1017 要依次粘贴字符 1、0、1、7，即需要 1 个

字符 0，2 个字符 1，1 个字符 7。

制作一切 1 到 2020 号门牌需要多少个字符？ 2？

答案提交

这是一个结果填空的问题，你只需要计算结果并提交。这个问题的结果是一个

提交答案时只填写整数，填写多余内容将无法得分。

624

calcCode：

public class Test {

public static void main(String[] args) {

int cnt = 0;

for (int i = 1, n = 1; i <= 2020; n = i)

do if (n % 10 == 2) cnt ;

while((n /= 10) > 0);

System.out.print(cnt);

}

}

回顾过去，这个问题太幸福了8

#B 寻找 2020

本题总分：5 分

问题描述

小蓝有一个只包含数字矩阵的数字矩阵 0 和 2.小蓝很喜欢 2020，他想找

这个数字矩阵中有多少个？ 2020 。

小蓝只注重三种构成 2020 的方式：

同一行连续四个字符从左到右构成 2020。

连续四个字符从上到下构成同一列 2020。

连续四个字符在从左上到右下的斜线上，从左上到右下构成 2020。

例如，对于下面的矩阵：

220000

000000

002202

000000

000022

002020

一共有 5 个 2020。其中 1 一个在同一行，1 一个在同一列，3 个

在斜线上。

小蓝的矩阵比上面的矩阵要大，由于太大了，他只好将这个矩阵放在了一

在试题目录中有一个文件 2020.txt，里面是小蓝矩阵。

请帮助小兰确定他的矩阵中有多少个 2020。

答案提交

这是一个题的结果，你只需要计算结果并提交。这个问题的结果是一个

提交答案时只填写整数，填写多余内容将无法得分。

16520

calcCode：

首先，确定矩阵的大小

BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("2020.txt")));

System.out.println(in.readLine().length());

动手

import java.io.*;

public class Test {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("2020.txt")));

int[] ioffset = { 0, 1, 1 };

int[] joffset = { 1, 0, 1 };

char[] word = { '2', '0', '2', '0' };

char[][] map = new char[300][];

for (int i = 0; i < 300; i )

map[i] = in.readLine().toCharArray();

int cnt = 0;

for (int n = 0; n < 300; n )

for (int m = 0; m < 300; m )

for (int k = 0; k < 3; k ) {

int temp = 0;

for (int i = n, j = m, step = 0; i >= 0 && i < 300 && j >= 0 && j < 300 && step < 4; i = ioffset[k], j = joffset[k], step )

if (map[i][j] == word[step]) temp ;

if (temp == 4) cnt ;

}

System.out.print(cnt);

}

}

#C 蛇形填数

本题总分：10 分

问题描述

如下图所示，小明用从 1 正整数蛇形开始填充无限矩阵。

1 2 6 7 15 ...

3 5 8 14 ...

4 9 13 ...

10 12 ...

11 ...

...

容易看出矩阵第二行第二列中的数是 5.请计算矩阵中的第一个 20 行第 20 列

数是多少？

答案提交

这是一个题的结果，你只需要计算结果并提交。这个问题的结果是一个

提交答案时只填写整数，填写多余内容将无法得分。

761

calcCode：

public class Test {

public static void main(String[] args) {

int[][] map = new int[201][201];

int n = 0;

for (int k = 1; k <= 200; k )

for (int i = 1; i <= k; i )

map[i][k - i 1] = n;

System.out.print(map[20][20])；

}

}

凭啥啊，B组比C组简单得多

蚂蚁跑了十年，小明跑了二十年

#D 七段码

本题总分：10 分

问题描述

小兰用七段码数码管来表示一种特殊的文字。

上图显示了七段码数码管的图表，共有数码管 7 段能发光的二

极管，分别标记为 a, b, c, d, e, f, g。

小蓝要选择一部分二极管(至少一个)发光来表达字符。设计字符

所有发光的二极管都需要连接在一起。

例如：b 发光，其他二极管不发光可以用来表达一个字符。

例如：c 发光，其他二极管不发光可以用来表达一个字符。该方案与上述方案相匹配

尽管看起来相似，但一行方案可以用来表示不同的字符。

例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一个字符。

例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光

二极管没有连成一片。

小蓝能用七段码数码管表达多少种不同的字符？

答案提交

这是一个题的结果，你只需要计算结果并提交。这个问题的结果是一个

提交答案时只填写整数，填写多余内容将无法得分。

80

calcCode：

import java.util.Arrays;

public class Test {

static int cnt;

static boolean[] select, marked, graph[];

public static void main(String[] args) {

// 0: a, 1: b, 2: c, 3:d, 4: e, 5: f, 6: g

select = new boolean[7];

marked = new boolean[7];

graph = new boolean[7][7];

graph[0][1] = graph[1][0] = true;

graph[0][5] = graph[5][0] = true;

graph[1][6] = graph[6][1] = true;

graph[1][2] = graph[2][1] = true;

graph[2][6] = graph[6][2] = true;

graph[2][3] = graph[3][2] = true;

graph[3][4] = graph[4][3] = true;

graph[4][5] = graph[5][4] = true;

graph[4][6] = graph[6][4] = true;

graph[5][6] = graph[6][5] = true;

dfs(0, 0);

System.out.print(cnt);

}

static void dfs(int d, int len) {

if (d == 7) {

if (len == 0) return;

int v = 0;

while (!select[v]) v++;

Arrays.fill(marked, false);

if (findPath(v) == len) cnt++;

} else {

select[d] = true;

dfs(d + 1, len + 1);

select[d] = false;

dfs(d + 1, len);

}

}

static int findPath(int v) {

marked[v] = true;

int len = 1;

for (int w = 0; w < 7; w++) {

if (!select[w] || marked[w] || !graph[v][w]) continue;

len += findPath(w);

}

return len;

}

}

因为这个图存在环，所以不能正常回溯，但全排列下来也只有 127 种组合，索性就不回溯了

#E 排序

本题总分：15 分

问题描述

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。

在冒泡排序中，每次只能交换相邻的两个元素。

小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，

则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。

例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，

总共需要 4 次交换。

小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交

换，可是他忘了吧这个字符串记下来，现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对

该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中不可以包含相同的字符。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个只包含小写英文字母的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

NULL

首先确定范围，冒泡交换的次数是根据逆序数来看的，要交换100次的话，元素个数必须大于等于15个，然后枚举就行，先吃个饭

calcCode：

import java.util.Arrays;

public class Test {

static final int len = 15;

public static void main(String[] args) {

char[] a = new char[len];

for (int i = 0; i < len; i++)

a[i] = (char)('a' + i);

do {

int cnt = 0;

for (int i = 0; i < len; i++)

for (int j = 0; j < i; j++)

if (a[i] < a[j]) cnt++;

if (cnt == 100) {

System.out.println(a);

return;

}

} while (next(a));

}

static boolean next(char[] a) {

int i = a.length - 2;

while (i >= 0 && a[i] > a[i + 1]) i--;

if (i < 0) return false;

int j = i + 1;

char t = a[i];

while (j < a.length && a[j] > t) j++;

a[i] = a[j - 1];

a[j - 1] = t;

Arrays.sort(a, i + 1, a.length);

return true;

}

}

写出来后发现时间复杂度直接拉满

先放放

#F 成绩分析

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

问题描述

小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是

一个 0 到 100 的整数。

请计算这次考试的最高分、最低分和平均分。

输入格式

输入的第一行包含一个整数 n，表示考试人数。

接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。

输出格式

输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

测试样例1

Input：

7

80

92

56

74

88

99

10

Output：

99

10

71.29

评测用例规模与约定

对于 50% 的评测用例，1 ≤ n ≤ 100。

对于所有评测用例，1 ≤ n ≤ 10000。

code：

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.StreamTokenizer;

public class Main {

public static void main(String[] args) throws IOException {

StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

in.nextToken();

int n = (int)in.nval, sum = 0, max = 0, min = 128;

for (int i = 0, t; i < n; i++) {

in.nextToken();

sum += t = (int)in.nval;

if (t > max) max = t;

if (t < min) min = t;

}

System.out.printf("%d\n%d\n%.2f", max, min, (double)sum / n);

}

}

#G 单词分析

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

问题描述

小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组

成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不

住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得

最多来分辨单词。

现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这

个字母出现的次数。

输入格式

输入一行包含一个单词，单词只由小写英文字母组成。

输出格式

输出两行，第一行包含一个英文字母，表示单词中出现得最多的字母是哪

个。如果有多个字母出现的次数相等，输出字典序最小的那个。

第二行包含一个整数，表示出现得最多的那个字母在单词中出现的次数。

测试样例1

Input：

lanqiao

Output：

a

2

测试样例2

Input：

longlonglongistoolong

Output：

o

6

评测用例规模与约定

对于所有的评测用例，输入的单词长度不超过 1000。

code：

import java.io.IOException;

public class Main {

public static void main(String[] args) throws IOException {

byte[] buff = new byte[1024];

int l = System.in.read(buff), max = 0;

int[] cnt = new int[128];

for (int i = 0; i < l; i++)

cnt[buff[i]]++;

for (char i = 'z'; i >= 'a'; i--)

if (cnt[i] >= max) {

max = cnt[i];

l = i;

}

System.out.println((char)l + "\n" + max);

}

}

#H 数字三角形

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

问题描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。

对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入格式

输入的第一行包含一个整数 N (1 < N ≤ 100)，表示三角形的行数。下面的

N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数

输出格式

输出一个整数，表示答案。

测试样例1

Input：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Output：

27

code：

#I 子串分值和

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

问题描述

对于一个字符串 S，我们定义 S 的分值 f(S ) 为 S 中出现的不同的字符个

数。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。

现在给定一个字符串 S [0…n − 1](长度为 n)，请你计算对于所有 S 的非空

子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是多少。

输入格式

输入一行包含一个由小写字母组成的字符串 S。

输出格式

输出一个整数表示答案。

测试样例1

Input：

ababc

Output：

28

Explanation：

子串 f值

a 1

ab 2

aba 2

abab 2

ababc 3

b 1

ba 2

bab 2

babc 3

a 1

ab 2

abc 3

b 1

bc 2

c 1

评测用例规模与约定

对于 20% 的评测用例，1 ≤ n ≤ 10；

对于 40% 的评测用例，1 ≤ n ≤ 100；

对于 50% 的评测用例，1 ≤ n ≤ 1000；

对于 60% 的评测用例，1 ≤ n ≤ 10000；

对于所有评测用例，1 ≤ n ≤ 100000。

code：

#J 装饰珠

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

问题描述

在怪物猎人这一款游戏中，玩家可以通过给装备镶嵌不同的装饰珠来获取

相应的技能，以提升自己的战斗能力。

已知猎人身上一共有 6 66 件装备，每件装备可能有若干个装饰孔，每个装饰

孔有各自的等级，可以镶嵌一颗小于等于自身等级的装饰珠 (也可以选择不镶

嵌)。

装饰珠有 M MM 种，编号 1 11 至 M MM，分别对应 M MM 种技能，第 i ii 种装饰珠的等级

为 L i L_{i}Li​，只能镶嵌在等级大于等于 L i L_iLi​ 的装饰孔中。

对第 i ii 种技能来说，当装备相应技能的装饰珠数量达到 K i K_{i}Ki​ 个时，会产生

W i ( K i ) W_{i}(K_{i})Wi​(Ki​) 的价值。镶嵌同类技能的数量越多，产生的价值越大，即 W i ( K i − 1 ) < W i ( K i ) W_{i}(K_{i} - 1) < W_{i}(K_{i})Wi​(Ki​−1)

会产生 W i ( P i ) W_{i}(P_{i})Wi​(Pi​) 的价值。

对于给定的装备和装饰珠数据，求解如何镶嵌装饰珠，使得 6 件装备能得

到的总价值达到最大。

输入格式

输入的第 1 11 至 6 66 行，包含 6 66 件装备的描述。其中第 i ii 的第一个整数 N i N_{i}Ni​ 表示

第 i ii 件装备的装饰孔数量。后面紧接着 N i N_{i}Ni​ 个整数，分别表示该装备上每个装饰

孔的等级 L ( 1 ≤ L ≤ 4 ) L(1 ≤ L ≤ 4)L(1≤L≤4)。

第 7 77 行包含一个正整数 M MM，表示装饰珠 (技能) 种类数量。

第 8 88 至 M + 7 M + 7M+7 行，每行描述一种装饰珠 (技能) 的情况。每行的前两个整数

L j ( 1 ≤ L j ≤ 4 ) L_{j}(1 ≤ L_{j} ≤ 4)Lj​(1≤Lj​≤4) 和 P j ( 1 ≤ P i ≤ 7 ) P_{j}(1 ≤ P_{i} ≤ 7)Pj​(1≤Pi​≤7) 分别表示第 j jj 种装饰珠的等级和上限。接下来

P j P_jPj​ 个整数，其中第 k kk 个数表示装备该中装饰珠数量为 k kk 时的价值 W j ( k ) W_{j}(k)Wj​(k)。

输出格式

输出一行包含一个整数，表示能够得到的最大价值。

测试样例1

Input：

1 1

2 1 2

1 1

2 2 2

1 1

1 3

3

1 5 1 2 3 5 8

2 4 2 4 8 15

3 2 5 10

Output：

20

Explanation：

按照如下方式镶嵌珠子得到最大价值 18，括号内表示镶嵌的装饰珠的种类编号：

1: (1)

2: (1) (2)

3: (1)

4: (2) (2)

5: (1)

6: (2)

4 颗技能 1 装饰珠，4 颗技能 2 装饰珠 W1(4) + W2(4) = 5 + 15 = 20。

评测用例规模与约定

对于 30% 的评测用例，1 ≤ Ni ≤ 10, 1 ≤ M ≤ 20, 1 ≤ Wj(k) ≤ 500；

对于所有评测用例，1 ≤ Ni ≤ 50, 1 ≤ M ≤ 10000, 1 ≤ Wj(k) ≤ 10000。

code：