蓝桥杯
2020 年省赛真题（Java 大学 B 组 ）
#A 解密
本题总分：5 分
问题描述
小明设计了一种文章加密的方法：对于每个字母
c
c
c
，将它变成某个另外的
字符
T
c
T_c
T
c
。下表给出了字符变换的规则：
例如，将字符串 YeRi 加密可得字符串 EaFn。
小明有一个随机的字符串，加密后为
EaFnjISplhFviDhwFbEjRjfIBBkRyY
（由 30 个大小写英文字母组成，不包含换行符），请问原字符串是多少？
（如果你把以上字符串和表格复制到文本文件中，请务必检查复制的内容
是否与文档中的一致。在试题目录下有一个文件 str.txt，第一行为上面的字符
串，后面 52 行依次为表格中的内容。）
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
只包含
30
30
3
0
个大小写英文字母的字符串，在提交答案时只填写这个字符串，填写
多余的内容将无法得分。
YeRikGSunlRzgDlvRwYkXkrGWWhXaA
calcCode：
import java.io.*;
public class Test {
public static void main(String[] args) throws IOException {
InputReader in = new InputReader(System.in, 200);
int[] str = new int[30], table = new int[128];
for (int i = 0; i < 30; i++)
str[i] = in.nextChar();
for (int i = 0; i < 52; i++) {
int v = in.nextChar(), w = in.nextChar();
table[w] = v;
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < 30; i++)
out.appendCodePoint(table[str[i]]);
System.out.print(out);
}
static class InputReader {
InputStream in;
int next, len;
byte[] buff;
InputReader(InputStream in) { this(in, 8192); }
InputReader(InputStream in, int buffSize) {
this.buff = new byte[buffSize];
this.next = this.len = 0;
this.in = in;
}
int getByte() {
if (next >= len)
try {
next = 0;
len = in.read(buff);
if (len == -1) return -1;
} catch (IOException e) { }
return buff[next++];
}
int nextChar() {
int c = getByte();
while (c <= 32 || c == 127) c =getByte();
return c;
}
}
}
写了个输入流
再打个表，结果就出来了
#B 纪念日
本题总分：5 分
问题描述
2020 年 7 月 1 日是中国共产党成立 99 周年纪念日。
中国共产党成立于 1921 年 7 月 23 日。
请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包
含多少分钟？
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
52038720
calcCode：
import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
public class Test {
public static void main(String[] args) throws ParseException {
DateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date start = format.parse("1921-7-23 12:00:00");
Date end = format.parse("2020-7-1 12:00:00");
System.out.print(((end.getTime() - start.getTime()) / 1000 / 60 / 60) * 60);
}
}
精度有点问题，但不知道问题在哪
#C 合并检测
本题总分：10 分
问题描述
新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情，A 国准
备给大量民众进病毒核酸检测。
然而，用于检测的试剂盒紧缺。
为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k
个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k
个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明
至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看，
如果检测前 k − 1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中
不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用
了 k + 1 个试剂盒完成了 k 个人的检测。
A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能
最节省试剂盒？
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
10
calcCode：
public class Main {
public static void main(String[] args) {
int MAX = 10000, min = 0x7ffffff, res = 0;
for (int i = 2; i <= MAX; i++) {
int cnt = MAX / i + MAX / 100 * i + (MAX % i == 0? 0: 1);
if (cnt < min) {
min = cnt;
res = i;
}
}
System.out.print(res);
}
}
因为没给出具体人数，所以读半天没读读懂题
枚举就完事了
#D 分配口罩
本题总分：10 分
问题描述
某市市长获得了若干批口罩，每一批口罩的数目如下：（如果你把以下文
字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目
录下有一个文件 mask.txt，内容与下面的文本相同）
9090400
8499400
5926800
8547000
4958200
4422600
5751200
4175600
6309600
5865200
6604400
4635000
10663400
8087200
4554000
现在市长要把口罩分配给市内的 2 所医院。由于物流限制，每一批口罩只
能全部分配给其中一家医院。市长希望 2 所医院获得的口罩总数之差越小越好。
请你计算这个差最小是多少？
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
2400
calcCode：
import java.util.Scanner;
public class Test {
static int sum, cnt = 0x3f3f3f3f, value[] = new int[15];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for (int i = 0; i < 15; i++)
sum += value[i] = in.nextInt();
dfs(0, 0);
System.out.print(cnt);
}
static void dfs(int d, int v) {
if (d == 15) cnt = min(cnt, abs(sum - v - v));
else {
dfs(d + 1, v + value[d]);
dfs(d + 1, v);
}
}
static int min(int a, int b) { return a < b? a: b; }
static int abs(int a) { return a > 0? a: -a; }
}
调试半天，最后才发现少输入一个数，我™
#E 斐波那契数列最大公约数
本题总分：15 分
问题描述
斐波那契数列满足
F
1
=
F
2
=
1
F_1 = F_2 = 1
F
1
=
F
2
=
1
，从
F
3
F_3
F
3
开始有
F
n
=
F
n
−
1
+
F
n
−
2
F_n = F_{n−1} + F_{n−2}
F
n
=
F
n
−
1
+
F
n
−
2
。请你计算
G
C
D
(
F
2020
,
F
520
)
GCD(F_{2020}, F_{520})
G
C
D
(
F
2
0
2
0
,
F
5
2
0
)
，其中
G
C
D
(
A
,
B
)
GCD(A, B)
G
C
D
(
A
,
B
)
表示
A
A
A
和
B
B
B
的最大公约数。
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
6765
calcCode：
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger F520 = BigInteger.ZERO;
BigInteger F1 = BigInteger.ONE, F2 = BigInteger.ONE, F3 = BigInteger.ZERO;
for (int i = 3; i <= 2020; i++) {
F3 = F1.add(F2);
F1 = F2;
F2 = F3;
if (i == 520) F520 = F3;
}
System.out.println(gcd(F3, F520));
}
static BigInteger gcd (BigInteger a, BigInteger b) { return b.compareTo(BigInteger.ZERO) == 0? a: gcd(b, a.mod(b)); }
}
#F 分类计数
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
问题描述
输入一个字符串，请输出这个字符串包含多少个大写字母，多少个小写字
母，多少个数字。
输入格式
输入一行包含一个字符串。
输出格式
输出三行，每行一个整数，分别表示大写字母、小写字母和数字的个数。
测试样例
1
Input：
1+a=Aab
Output：
1
3
1
评测用例规模与约定
对于所有评测用例，字符串由可见字符组成，长度不超过 100。
code：
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
byte[] buff = new byte[100];
int len = System.in.read(buff), a = 0, b = 0, c = 0;
for (int i = 0; i < len; i++) {
if (buff[i] >= 'a' && buff[i] <= 'z') b++;
else if (buff[i] >= 'A' && buff[i] <= 'Z') a++;
else if (buff[i] >= '0' && buff[i] <= '9') c++;
}
System.out.print(a + "\n" + b + "\n" + c);
}
}
#G 八次求和
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
问题描述
给定正整数
n
n
n
, 求
1
8
+
2
8
+
⋅
⋅
⋅
+
n
8
1^8 + 2^8 + · · · + n^8
1
8
+
2
8
+
⋅
⋅
⋅
+
n
8
mod 123456789 。其中 mod 表示取余。
输入格式
输入的第一行包含一个整数 n。
输出格式
输出一行，包含一个整数，表示答案
测试样例
1
Input：
2
Output：
257
测试样例
2
Input：
987654
Output：
43636805
评测用例规模与约定
对于 20% 的评测用例，1 ≤ n ≤ 20。
对于 60% 的评测用例，1 ≤ n ≤ 1000。
对于所有评测用例，1 ≤ n ≤ 1000000。
code：
import java.io.*;
public class Main {
static final int mod = 123456789;
public static void main(String[] args) throws IOException {
long n = nextInt(System.in), cnt = 0;
for (long i = 1, k = 1; i <= n; k = ++i) {
for (int j = 0; j < 3; j++)
k = (k * k) % mod;
cnt = (cnt + k) % mod;
}
System.out.print(cnt);
}
static int nextInt(InputStream in) throws IOException {
int n = 0, c = in.read();
while (c < '0' || c > '9') c = in.read();
while (c >='0' && c <='9') {
n = n * 10 + (c & 0xf);
c = in.read();
}
return n;
}
}
考啥？mod交换律？
下面写了 Python 的校验方法可以参考一下，虽然我们老师说J组不允许使用 python
print(sum([reduce(lambda x,y:x + y ** 8,range(0, int(input()) + 1))]) % 123456789)
#H 字符串编码
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
问题描述
小明发明了一种给由全大写字母组成的字符串编码的方法。对于每一个大
写字母，小明将它转换成它在 26 个英文字母中序号，即 A → 1, B → 2, … Z →
26。
这样一个字符串就能被转化成一个数字序列：
比如 ABCXYZ → 123242526。
现在给定一个转换后的数字序列，小明想还原出原本的字符串。当然这样
的还原有可能存在多个符合条件的字符串。小明希望找出其中字典序最大的字
符串。
输入格式
一个数字序列
输出格式
一个只包含大写字母的字符串，代表答案
测试样例
1
Input：
123242526
Output：
LCXYZ
评测用例规模与约定
对于 20% 的评测用例，输入的长度不超过 20。
对于所有评测用例，输入的长度不超过 200000。
code：
import java.io.*;
public class Main {
static byte[] chars = { 0, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90 };
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String line = in.readLine();
int flag = 0;
if (line.charAt(line.length() - 1) == '0') flag = 2;
int pre = 0;
for (int i = 0, h = line.length() - flag; i < h; i++) {
pre = pre * 10 + (line.charAt(i) & 0xf);
if (pre < 10) continue;
if (pre > 26) {
out.write(chars[pre / 10]);
pre %= 10;
} else if (pre > 10) {
out.write(chars[pre]);
pre = 0;
}
}
if (pre != 0) out.write(chars[pre]);
if (flag > 0) out.write(chars[(line.charAt(line.length() - 2) - '0') * 10]);
out.close();
}
}
打了个表，做了两个特判
一个是否输出完的判断，一个是结尾是否能单独组成一个字母的判断
#I BST 插入节点问题
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
给定一棵包含 N 个节点的二叉树，节点编号是 1 ∼ N。其中 i 号节点具有
权值 Wi，并且这些节点的权值恰好形成了一棵排序二叉树 (BST)。
现在给定一个节点编号 K，小明想知道，在这 N 个权值以外，有多少个整
数 X (即 X 不等于任何 Wi ) 满足：给编号为 K 的节点增加一个权值为 X 的子
节点，仍可以得到一棵 BST。
例如在下图中，括号外的数字表示编号、括号内的数字表示权值。即编号
1 ∼ 4 的节点权值依次是 0、10、20、30。
如果 K = 1，那么答案为 0。因为 1 号节点已经有左右子节点，不能再增
加子节点了。
如果 K = 2，那么答案为无穷多。因为任何一个负数都可以作为 2 的左子
节点。
如果 K = 3，那么答案为 9。因为 X = 11, 12, · · · , 19 都可以作为 3 的左子
节点。
输入格式
第一行包含 2 个整数 N 和 K。
以下 N 行每行包含 2 个整数，其中第 i 行是编号为 i 的节点的父节点编号
Pi 和权值 Wi 。注意 Pi = 0 表示 i 是根节点。
输入保证是一棵 BST。
输出格式
一个整数代表答案。如果答案是无穷多，输出 −1。
测试样例
1
Input：
4 3
0 10
1 0
1 20
3 30
Output：
9
评测用例规模与约定
对于 60% 的评测用例，1 ≤ K ≤ N ≤ 100，0 ≤ Wi ≤ 200，且 Wi 各不相同。
对于所有评测用例，1 ≤ K ≤ N ≤ 10000，0 ≤ Wi ≤ 100000000，且 Wi 各不
相同。
code：
import java.io.*;
import java.util.Arrays;
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, v, w;
in.nextToken();
int k = (int)in.nval;
Node[] tree = new Node[n + 1];
tree[0] = new Node(0);
for (int i = 1; i <= n; i++){
in.nextToken();
w = (int)in.nval;
in.nextToken();
v = (int)in.nval;
if (v < tree[w].value) tree[i] = tree[w].left = new Node(v);
else tree[i] = tree[w].right = new Node(v);
}
if (tree[k].left != null && tree[k].right!= null) System.out.print('0');
else {
Node node = tree[k];
Arrays.sort(tree);
int left = 1, right = n, mid = 0;
while (left <= right) {
mid = (left + right) / 2;
if (tree[mid].value < node.value) left = mid + 1;
else if (tree[mid].value > node.value) right = mid - 1;
else break;
}
if (mid == 1 || mid == n) System.out.print("-1");
else {
left = node.left == null? tree[mid - 1].value: node.value;
right = node.right == null? tree[mid + 1].value: node.value;
System.out.print(right - left - 1);
}
}
}
static class Node implements Comparable<Node> {
int value;
Node left, right;
Node(int value) { this.value = value; }
public int compareTo(Node node) {
return this.value - node.value;
}
}
}
只要二叉树是中缀遍历有序的，那么每个节点就必须满足，小于第一个比它大的，大于第一个比它小的
只要二叉树是中缀遍历有序，那么对一个节点值的改动都可以满足这么画出的区间。
少了两个效验，懒的写
#J 网络分析
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
小明正在做一个网络实验。
他设置了 n 台电脑，称为节点，用于收发和存储数据。
初始时，所有节点都是独立的，不存在任何连接。
小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信
了。两个节点如果存在网线连接，称为相邻。
小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送
到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接
或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。
一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小。
输入格式
输入的第一行包含两个整数 n, m，分别表示节点数量和操作数量。节点从
1 至 n 编号。
接下来 m 行，每行三个整数，表示一个操作。
如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 a = b
时，表示连接了一个自环，对网络没有实质影响。
如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。
输出格式
输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示进行
完上述操作后节点 1 至节点 n 上存储信息的大小。
测试样例
1
Input：
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1
Output：
13 13 5 3
评测用例规模与约定
对于 30% 的评测用例，1 ≤ n ≤ 20，1 ≤ m ≤ 100。
对于 50% 的评测用例，1 ≤ n ≤ 100，1 ≤ m ≤ 1000。
对于 70% 的评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 10000。
对于所有评测用例，1 ≤ n ≤ 10000，1 ≤ m ≤ 100000，1 ≤ t ≤ 100。
code：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
static int[] link, lazy, value;
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
in.nextToken();
int n = (int)in.nval;
in.nextToken();
int m = (int)in.nval;
value = new int[n + 1];
lazy = new int[n + 1];
link = new int[n + 1];
for (int i = 1; i <= n; i++) link[i] = i;
while (m-- > 0) {
in.nextToken();
int i = (int)in.nval;
in.nextToken();
int v = (int)in.nval;
in.nextToken();
int w = (int)in.nval;
if (i == 1) {
v = find(v);
w = find(w);
if (v != w) {
link[v] = w;
lazy[v] = value[v] - value[w];
}
} else value[find(v)] += w;
}
for (int i = 1; i <= n; i++)
out.print((value[find(i)] + lazy[i]) + " ");
out.close();
}
static int find(int x) {
if (link[x] != x) {
int t = link[x];
link[x] = find(link[x]);
lazy[x] += lazy[t];
}
return link[x];
}
}
带权并查集，两个父节点之间的差
非带权版本，用错语言了，先挂这里。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) { new Main().run(); }
List<Integer>[] graph;
boolean[] visited;
int[] linked;
long[] lazy;
void run() {
int n = nextInt(), m = nextInt(), p, x, y;
PrintWriter out = new PrintWriter(System.out);
visited = new boolean[n + 1];
graph = new List[n + 1];
linked = new int[n + 1];
lazy = new long[n + 1];
for (int i = 1; i <= n; ++i)
graph[linked[i] = i] = new ArrayList();
while (m-- > 0) {
p = nextInt();
x = nextInt();
y = nextInt();
if (p == 1) {
x = find(x);
y = find(y);
if (x != y) {
lazy[y] -= lazy[x];
graph[x].add(y);
linked[y] = x;
}
} else lazy[find(x)] += y;
}
for (int i = 1; i <= n; ++i) {
dfs(find(i));
out.print(lazy[i]);
out.write(' ');
}
out.flush();
}
void dfs(int root) {
if (visited[root]) return;
visited[root] = true;
for (int v : graph[root]) {
lazy[v] += lazy[root];
dfs(v);
}
}
int find(int x) { return x == linked[x] ? x : (linked[x] = find(linked[x])); }
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int nextInt() {
try {
in.nextToken();
} catch (IOException e) {
e.printStackTrace();
}
return (int)in.nval;
}
}