蓝桥杯 2022年国赛真题
^{Java 大学B组}

 试题 A: 重合次数
 试题 B: 数数
 试题 C: 左移右移
 试题 D: 窗口
 试题 E: 迷宫
 试题 F: 小球称重
 试题 G: 背包与魔法
 试题 H: 修路
 试题  I: 围栏
 试题 J: 好数之和

---

  防查重，成绩公示再写编程题。

---

试题 A: 重合次数

本题总分：5 分

【问题描述】

  在同一天中，从上午 $6$ 点 $13$ 分 $22$ 秒到下午 $14$ 点 $36$ 分 $20$ 秒，钟表上的分针和秒针一共重合了多少次？

  注意时针、分针、秒针都围绕中心做匀速运动。

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

---

494

---

import java.time.LocalTime;

public class Test {

	public static void main(String[] args) { new Test().run(); }
	
	LocalTime start = LocalTime.of(6, 13, 22);
	
	LocalTime end = LocalTime.of(14, 36, 20);
	
	void run() {
		int cnt = 0;
		for (; start.compareTo(end) <= 0; start = start.plusSeconds(1))
			if (start.getMinute() == start.getSecond() && start.getSecond() != 0) ++cnt;
		System.out.println(cnt);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  按秒枚举时间，然后注意一下接近整点时，分针与秒针非常接近一直重合，而题面指出分针、秒针都围绕中心做匀速运动，故而这个地方需要特判一下。

---

试题 B: 数数

本题总分：5 分

【问题描述】

  任何一个大于 $1$ 的正整数都能被分解为若干个质数相乘，比如 $28=2\times 2\times 7$ 被分解为了三个质数相乘。请问在区间 $[$$2333333$$,$$23333333$$]$ 中有多少个正整数 可以被分解为 $12$ 个质数相乘？

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

25606

---

import java.util.ArrayList;
import java.util.List;

public class Test {

	public static void main(String[] args) { new Test().run(); }
	
	int cnt = 0, start = 2333333, end = 23333333;
	
	void run() {
		int[] factor = new int[end + 1];
		List<Integer> prime = new ArrayList();
		for (int i = 2; i <= end; ++i) {
			if (factor[i] == 0) {
				factor[i] = 1;
				prime.add(i);
			}
			if (i >= start &&
				factor[i] == 12) ++cnt;
			for (int p : prime) {
				if (i * p > end) break;
				factor[i * p] = factor[i] + 1;
				if (i % p == 0) break;
			}
		}
		System.out.print(cnt);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

  欧拉筛模板题，没啥好说的。

---

试题 C: 左移右移

时间限制：3.0s 内存限制：512.0MB 本题总分：10 分

【问题描述】

  小蓝有一个长度为 $N$ 的数组，初始时从左到右依次是 $1,2,3,\cdots ,N$。

  之后小蓝对这个数组进行了 $M$ 次操作，每次操作可能是以下 $2$ 种之一$：$

  $1.$ 左移 $x$，即把 $x$ 移动到最左边。
  $2.$ 右移 $x$，即把 $x$ 移动到最右边。

  请你回答经过 $M$ 次操作之后，数组从左到右每个数是多少？

【输入格式】

  第一行包含 $2$ 个整数，$N$ 和 $M$。

  以下 $M$ 行每行一个操作，其中 $“Lx”$ 表示左移 $x$，$“Rx”$ 表示右移 $x$。

【输出格式】

  输出 $N$ 个数，代表操作后的数组。

【样例输入】

5 3
L 3
L 2
R 1
1
2
3
4

【样例输出】

2 3 4 5 1
1

【样例说明】

  样例中的数组变化如下$：$
  $[1,2,3,4,5]\to [3,1,2,4,5]\to [2,3,1,4,5]\to [2,3,4,5,1]$

【评测用例规模与约定】

  对于 $50\%$ 的评测用例，$1\le N,M\le 10000.$
  对于 $100\%$ 的评测用例，$1\le N,M\le 200000,1\le x\le N.$

---

试题 D: 窗口

时间限制：3.0s 内存限制：512.0MB 本题总分：10 分

---

【问题描述】

  在平时使用电脑的过程中，经常会打开各种各样的窗口，各个窗口会在桌面上重叠，并按照一定的层次关系显示。有的窗口能够看到全部内容，而有的窗口只能看到局部。

  现在给定一组操作桌面窗口的过程序列，请你通过 $\mathrm{A}\mathrm{S}\mathrm{C}\mathrm{I}\mathrm{I}$ 艺术图来绘制最后桌面的状态。

  已知桌面的大小为 $N\times M$，即桌面高度为 $N$ 个像素，宽度为 $M$ 个像素，其中左上角坐标为 $(0,0)$，右下角坐标为 $(N-1,M-1)$。

  对于窗口的操作有如下 $5$ 种$：$

  $1.$ $\mathbf{n}\mathbf{e}\mathbf{w}$ 操作 - 打开一个新窗口
  $\text{new [PID] [top] [left] [height] [width]}$
  如$：$$\text{new 12 20 30 80 100}$
  表示打开一个 $PID$ 为 $12$ 的窗口，窗口左上角的坐标为 $(20,30)$，该窗口宽度为 $100$ 个像素，高度为 $80$ 个像素；新创建的窗口，其层级为顶层。

  $2.$ $\mathbf{m}\mathbf{o}\mathbf{v}\mathbf{e}$ 操作 - 移动一个窗口
  $\text{move [PID] [vertical] [horizontal]}$
  如$：$$\text{move 12 -5 10}$
  表示将 $PID$ 为 $12$ 的窗口在垂直方向上移动 $-5$ 个像素，在水平方向上移动 $10$ 个像素。若窗口左上角原位置为 $(20,30)$，此时则在 $(15,40)$；移动后的窗口，其层级为顶层。

  $3.$ $\mathbf{r}\mathbf{e}\mathbf{s}\mathbf{i}\mathbf{z}\mathbf{e}$ 操作 - 改变窗口大小
  $\text{resize [PID] [height] [width]}$
  如$：$$\text{resize 12 90 110}$
  表示保持左上角坐标不变的情况下，改变 $PID$ 为 $12$ 的窗口大小，调整为高度 $90$ 像素，宽度 $110$ 像素；改变大小后的窗口，其层级为顶层。

  $4.$ $\mathbf{c}\mathbf{l}\mathbf{o}\mathbf{s}\mathbf{e}$ 操作 - 关闭窗口
  $\text{close [PID]}$
  如$：$$\text{close 12}$
  表示关闭 $PID$ 为 $12$ 的窗口；

  $5.$ $\mathbf{a}\mathbf{c}\mathbf{t}\mathbf{i}\mathbf{v}\mathbf{e}$ 操作 - 激活窗口
  $\text{active [PID]}$
  如$：$$\text{active 12}$
  表示激活 $PID$ 为 $12$ 的窗口，此时该窗口的层级被置为顶层。

【输入格式】

  第 $1$ 行$：$$2$ 个正整数 $N,M$，表示桌面大小；

  第 $2$ 行$：$$1$ 个正整数 $K$，表示操作序列的长度；

  第 $3\cdots K+2$ 行$：$每行一个操作，格式见题目描述。

【输出格式】

  第 $1\cdots N$ 行$：$每行 $M$ 个字符，仅包含 $‘.’,‘+’,‘-’,‘|’,‘’$ 五种字符。

  $‘.’$ 表示桌面背景，即该部分未被任何窗口覆盖，$‘+’$ 表示窗口的四个角，$‘-’$ 表示窗口的横边, $‘|’$ 表示窗口的竖边，$‘’$ 表示窗口内部。

【样例输入】

7 10
8
new 1 0 3 2 5
new 2 4 4 2 5
new 3 3 3 4 6
resize 3 3 6
move 1 0 5
close 2
new 4 1 1 3 5
active 3
1
2
3
4
5
6
7
8
9
10

【样例输出】

........+-
.+---+..+-
.|   |.... 
.+-+----+. 
...|    |. 
...+----+.
..........
1
2
3
4
5
6
7

【评测用例规模与约定】

  对于 $100\%$ 的数据，$1\le N,M\le 256,1\le K\le 10000.$
  输入数据保证$：$
  $1.$ 同一时间不会有两个相同 $PID$ 的窗口存在，可能存在关闭某个 $PID$ 的窗口后，再新建一个同样 $PID$ 的窗口，$PID$ 的取值范围为 $1\le PID\le 100000$；
  $2.$ 同时存在的窗口数量不超过 $200$ 个；
  $3.$ 窗口尺寸不会小于 $2\times 2$，即窗口高度和宽度均不会小于 $2$，不会大于 $N\times M$；
  $4.$ 窗口在移动过程中，可能有部分界面超出桌面显示范围；
  $5.$ 所有输入的数值均不超过 $\pm 100000$。
  $6.$ $\mathbf{m}\mathbf{o}\mathbf{v}\mathbf{e}\mathbf{r}\mathbf{e}\mathbf{s}\mathbf{i}\mathbf{z}\mathbf{e}\mathbf{c}\mathbf{l}\mathbf{o}\mathbf{s}\mathbf{e}$ 只会对未关闭的窗口操作。

---

试题 E: 迷宫

时间限制：5.0s 内存限制：1.0GB 本题总分：15 分

【问题描述】

  这天，小明在玩迷宫游戏。

  迷宫为一个 $n\times n$ 的网格图，小明可以在格子中移动，左上角为 $(1,1)$，右下角 $(n,n)$ 为终点。迷宫中除了可以向上下左右四个方向移动一格以外，还有 $m$ 个双向传送门可以使用，传送门可以连接两个任意格子。

  假如小明处在格子 $(x_1,y_1)$，同时有一个传送门连接了格子 $(x_1,y_1)$ 和 $(x_2,y_2)$，那么小明既可以花费 $1$ 的步数向上下左右四个方向之一走一格 (不能越过边界)，也可以花费 $1$ 的步数通过传送门走到格子 $(x_2,y_2)$ 去。

  而对于同一个迷宫，小明每次进入的初始格子是在这 $n\times n$ 个格子中均匀随机的 (当然运气好可以直接随机到终点)，他想知道从初始格子走到终点的最短步数的期望值是多少。

【输入格式】

  输入共 $1+m$ 行，第一行为两个正整数 $n,m$。

  后面 $m$ 行，每行四个正整数 $x_{i1},y_{i1},x_{i2},y_{i2}$ 表示第 $i$ 个传送门连接的两个格 子坐标。

【输出格式】

  输出共一行，一个浮点数表示答案 (请保留两位小数)。

【样例输入】

2 1
1 1 2 2
1
2

【样例输出】

0.75
1

【样例说明】

  由于传送门的存在，从 $(1,1)$ 出发到终点 $(2,2)$ 只需要一步；而从 $(1,2)$ 和 $(2,1)$ 出发也只需要向下$/$右走一步；从 $(2,2)$ 出发需要 $0$ 步。所以步数期望为 $\frac{1+1+1+0}{2\times 2}=0.75$。

【评测用例规模与约定】

  对于 $20\%$ 的数据，保证 $n,m\le 20$；
  对于 $100\%$ 的数据，保证 $n,m\le 2000;x_{i1},y_{i1},x_{i2},y_{i2}\le n$。

---

试题 F: 小球称重

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

【问题描述】

  小蓝有 $N$ 个小球，编号 $1$ 至 $N$。其中 $N-1$ 是正品，重量相同；有 $1$ 个是次品，重量比正品轻。

  为了找出次品，小蓝已经用天平进行了 $M$ 次称重，并且记录下来每次两边放的小球编号，和称重结果。

  请你根据记录，判断还剩下几个小球有次品的嫌疑。

【输入格式】

  第一行包含 $2$ 个整数 N 和 M。

  以下包含 $M$ 次称重记录，每个记录占 $4$ 行。

  第一行是一个整数 $K$，表示天平两边各放了 $K$ 个小球。

  第二行包含 $K$ 个整数，代表放在天平左边的小球编号。

  第三行包含 $K$ 个整数，代表放在天平右边的小球编号。

  第四行是一个字符，为 $‘>’,‘<’,‘=’$ 之一。$‘>’$ 代表左边比右边重，$‘<’$ 代表左边比右边轻，$‘=’$ 代表两边重量相等。

  在一次称重中保证每个小球最多出现 $1$ 次。

【输出格式】

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

【样例输入】

10 2
3
1 2 3
4 5 6
<
2
3 7
8 9
=
1
2
3
4
5
6
7
8
9

【样例输出】

2
1

【样例说明】

   { 1 , 2 , 3 } < { 4 , 5 , 6 } \small \{1, 2, 3\} < \{4, 5, 6\} {1,2,3}<{4,5,6} 能判断出次品在 { 1 , 2 , 3 } \small \{1, 2, 3\} {1,2,3} 之中。
   { 3 , 7 } = { 8 , 9 } \small \{3, 7\} = \{8, 9\} {3,7}={8,9} 能判断出 $3$ 不可能是次品。
  所以只剩下 { 1 , 2 } \small \{1, 2\} {1,2} 可能是次品。

【评测用例规模与约定】

  对于 $40\%$ 的数据，$1\le N\le 10^6$;
  对于 $100\%$ 的数据，$1\le N\le 10^9,1\le M\le 10^5$, 参与 $M$ 次称重的小球总数 $\le 10^6.$

---

试题 G: 背包与魔法

时间限制：3.0s 内存限制：1.0GB 本题总分：20 分

【问题描述】

  小蓝面前有 $N$ 件物品，其中第 $i$ 件重量是 $W_i$，价值是 $V_i$。她还有一个背包，最大承重是 $M$。

  小蓝想知道在背包称重范围内，她最多能装总价值多少的物品？

  特别值得一提的是，小蓝可以使用一个魔法，将一件物品的重量增加 $K$， 同时价值翻倍。(当然小蓝也可以不使用魔法）

【输入格式】

  第一行包含 $3$ 个整数 $N、M$ 和 $K$。

  以下 $N$ 行，每行两个整数 $W_i$ 和 $V_i$。

【输出格式】

  一个整数代表答案。

【样例输入】

3 10 3
5 10
4 9
3 8
1
2
3
4

【样例输出】

26
1

【样例说明】

  选择第二件和第三件物品，同时对第二件物品使用魔法。

【评测用例规模与约定】

  对于 $30\%$ 的数据，$1\le N,M,K\le 100.$
  对于 $100\%$ 的数据，$1\le N\le 2000,1\le M,K\le 10000,0\le W_i,V_i\le 10000.$

---

试题 H: 修路

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

【问题描述】

  这天，小明在修路。

  他需要修理两条平行的道路 $A,B$，两条路上面分别有 $n$ 个和 $m$ 个点需要维修，它们相对于道路起点的距离分别为 $a_1,a_2,\cdots ,a_n$ 和 $b_1,b_2,\cdots ,b_m$。如图，两条路之间的距离为 $d$ 且它们起点 (最左端) 的连线和两条路都垂直。小明的起点为道路 $A$ 的起点，他需要尽可能快地遍历这些需要维修的 $n+m$ 个点，他既可以沿着道路 向右 行走，也可以在两条道路之间的空地上 随意 行走。

  小明想知道遍历这些点的最短路程是多少。

【输入格式】

  输入共三行，第一行为三个正整数 $n,m,d$。

  第二行为 $n$ 个由空格隔开的正整数 $a_1,a_2,\cdots ,a_n$。

  第三行为 $m$ 个由空格隔开的正整数 $b_1,b_2,\cdots ,b_m$。

【输出格式】

  一行，一个浮点数，表示答案，保留两位小数。

【样例输入】

2 2 2
2 1
1 2
1
2
3

【样例输出】

5.24
1

【样例说明】

  图中红线指出了样例的最短路线，$1+1+\sqrt{5}+1=5.24$。

【评测用例规模与约定】

  对于 $30\%$ 的数据，保证 $n+m\le 10$；
  对于 $100\%$ 的数据，保证 $n,m\le 2000,d\le 4\times 10^6,a_i,b_i\le 10^6$。

---

试题  I: 围栏

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

【问题描述】

  这天，小明在造围栏。

  他提前在地上 (二维平面) 打好了 $n$ 个洞，这 $n$ 个洞的位置形成了一个凸多边形。当他准备把固定围栏的木杆插进去的时候，突然发现自己少准备了两根木杆。

  如图，他现在只能在这 $n$ 个洞中选出 $n-2$ 个来放置木杆，他想知道用这 $n-2$ 个木杆能围成的凸多边形的最大的面积是多少。

【输入格式】

  输入共 $n+1$ 行，第一行为一个正整数 $n$。

  后面 $n$ 行，每行两个整数 $x_i,y_i$ 表示第 $i$ 个洞的坐标。

  保证按照逆时针的顺序输入这 $n$ 个点的坐标。

【输出格式】

  一行，一个正整数，表示答案。

  为了避免小数，请输出面积的两倍。

【样例输入】

5
0 0
1 0
2 1
0 3
-1 1
1
2
3
4
5
6

【样例输出】

6
1

【样例说明】

  选择 $(-1,1)(2,1)(0,3)$ 这三个点构成的多边形面积最大，为 $3$，所以输出 $6$。

【评测用例规模与约定】

  对于 $100\%$ 的数据，保证 $5\le n\le 100；|x_i|,|y_i|\le 10^6$。

---

试题 J: 好数之和

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

【问题描述】

  一个整数如果包含连续的 $2022$ 四个数字，我们就称之为 $“$好数$”$。

  例如 $2022、52022、20223、7020224$ 都是好数，而 $2202、20022、2222$ 都不是好数。

  给定 $L$ 和 $R$，请你计算在 $L$ 到 $R$ 之间（包含 $L$ 和 $R$）所有好数的和是多少？

【输入格式】

  两个整数 $L$ 和 $R$ 。

【输出格式】

  一个整数代表答案。

【样例输入】

1 20000
1

【样例输出】

14044
1

【样例说明】

  满足条件的好数有 $2022、12022$，它们的和是 $14044$。

【评测用例规模与约定】

  对于 $60\%$ 的评测用例，$R-L\le 10^8$
  对于 $100\%$ 的评测用例，$1\le L\le R\le 10^9$

---