第十二届蓝桥杯省赛 Java--B组
更新日志
5.22
试题E：路径，添加了Dijkstra算法，秒出答案
2.21
抱着开摆的心态先来试试题目难度
试题 A: ASC（5分）
已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？
答案： 76
1 | public class Main { |
试题 B: 卡片（5分）
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10， 但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？
答案： 3181
思路
思路是哈希
模拟一遍这个流程就好了
创建一个长度为10的数组 将数组中的每个元素初始化为2021 代表0~9 总共十种卡片 每种有2021张
然后将数字转化成字符串 字符串再转化成字符数组 遍历字符数组 将每个字符对应的卡片张数-1
当遍历完某个数字之后 卡片张数变为负数 则当前数字无法拼出来 输出当前数字的上一个数字即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] cards = new int[10];
Arrays.fill(cards, 2021);
int num = 1;
boolean flag = true;
while (flag) {
String str = num + "";
char[] c = str.toCharArray();
for (char ch : c) {
cards[ch - '0'] -= 1;
if (cards[ch - '0'] < 0) {
System.out.println(num - 1);
flag = false;
break;
}
}
num++;
}
}
}
试题 C: 直线（10分）
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点 {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标 是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。
给定平面上 20 × 21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横 坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之 间的整数的点。请问这些点一共确定了多少条不同的直线。
答案： 40257
思路
直线的斜截式 y=kx+b 只要每条直线的k和b不同 那就不是同一条直线
由于涉及到小数问题 直接比较大小会出错 这里我才用保留八位有效数字
浮点数比较大小 只要差值小于1e-8 即可认为相等
新建一个Fx类和Point类
Point类用来存放每一个点，遍历Point集合，将任意两点组成直线的k和b计算出来，并存入res集合
Fx类用来记录每两个点产生直线的k和b 并将它存入sdt集合中去重 平行于X轴和Y轴的单独处理 最后加上就行
HashSet去重：先判断hashCode（）是否相同，相同才会判断equals()
如果是需要对我们自定义的对象去重，就需要我们重写 hashCode 和 equals 方法
注意：HashSet要求放入的对象必须重写hashCode(),不然HashSet调用默认的hashCode方法判断对象的地址，不等就达不到想根据对象的值去重的目的。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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58import java.text.DecimalFormat;
import java.util.*;
class Solution {
public static void main(String[] args) {
ArrayList<Point> points = new ArrayList<>();
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 21; j++) {
points.add(new Point(i, j));
}
}
HashSet<Fx> set = new HashSet<>();
for (Point p1 : points) {
for (Point p2 : points) {
if (p1.x != p2.x && p1.y != p2.y){
double k = (p1.y - p2.y) / (p1.x - p2.x);
double b = p1.y - k * p1.x;
set.add(new Fx(k, b));
}
}
}
System.out.println(set.size() + 20 + 21);
}
}
class Point {
double x;
double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
class Fx {
double k;
double b;
public Fx(double k, double b) {
DecimalFormat df = new DecimalFormat("0.00000000");
this.k = Double.parseDouble(df.format(k));
this.b = Double.parseDouble(df.format(b));
}
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Fx)) return false;
Fx fx = (Fx) o;
return Double.compare(fx.k, k) == 0 && Double.compare(fx.b, b) == 0;
}
public int hashCode() {
return Objects.hash(k, b);
}
}
试题 D: 货物摆放（10分）
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝 规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、 宽、高。 小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上 分别堆 L、W、H 的货物，满足 n = L × W × H。
给定 n，请问有多少种堆放货物的方案满足要求。 例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1。
请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？
答案： 2430
思路
计算出因数然后无脑暴力三重循环1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import java.util.HashSet;
public class Main {
public static void main(String[] args) {
long num = 2021041820210418L;
HashSet<Long> set = new HashSet<>();
for (long i = 1; i < Math.sqrt(num); i++) {
if (num % i == 0) {
set.add(i);
set.add(num / i);
}
}
int res = 0;
for (long a : set)
for (long b : set)
for (long c : set)
if (a * b * c == num)
res++;
System.out.println(res);
}
}
试题 E: 路径（15分）
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
答案：10266387
思路
先按题目要求建图，将所有节点初始化为0x3f3f3f3f
(0x3f3f3f3f的十进制是1061109567,是10^9级别的,而一般场合下的数据都是小于10^9的,所以它可以作为无穷大使用)
两个节点的绝对值小于等于21 则求最小公倍数
最小公倍数公式 lcm = a * b / (gcd(a, b))
lcm是最小公倍数 gcd是最大公约数
欧几里得法求最大公约数 gcd(a, b) = gcd(b, a % b)
然后用弗洛伊德算法 求最短路径即可
(时间复杂度n^3 仅限填空题可以用用 编程题还是要用迪杰斯特拉算法)
心里默念了一下，大概算了10秒..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
27public class Main {
static int[][] arr = new int[2030][2030];
static void Floyd() {
for (int k = 1; k <= 2021; k++)
for (int i = 1; i <= 2021; i++)
for (int j = 1; j <= 2021; j++)
if (arr[i][j] > arr[i][k] + arr[k][j])
arr[i][j] = arr[i][k] + arr[k][j];
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
for (int i = 1; i <= 2021; i++) {
for (int j = 1; j <= 2021; j++) {
if (Math.abs(i - j) <= 21)
arr[i][j] = i * j / gcd(i, j);
else arr[i][j] = 0x3f3f3f3f;
}
}
Floyd();
System.out.println(arr[1][2021]);
}
}
1 | import java.util.Arrays; |
试题 F: 时间限制（15分）
小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取 了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时 刻经过的毫秒数。
现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要 显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
输入格式
输入一行包含一个整数，表示时间。
输出格式
输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值 为 0 到 23，MM 表示分，值为 0 到 59，SS 表示秒，值为 0 到 59。时、分、秒 不足两位时补前导 0。
样例输入 1
46800999
样例输出 1
13:00:00
样例输入 2
1618708103123
样例输出 2
01:08:23
评测用例规模与约定
对于所有评测用例，给定的时间为不超过10^18的正整数。
代码
1 | import java.util.Scanner; |
试题 G: 砝码称重（20分）
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量？
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN。
输出格式
输出一个整数代表答案。
输入样例：
3
1 4 6
输出样例：
10
样例解释
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 − 1；
10 = 4 + 6；
11 = 1 + 4 + 6。
数据范围
对于 50% 的评测用例，1≤N≤15。
对于所有评测用例，1≤N≤100，N 个砝码总重不超过 100000。
思路
网上看别的题解都用的是dp，我这里有个不用dp的方法
建立一个set集合 用来去重
我们先将第一个砝码a存入set集合
每个砝码只有三种情况 放左边 放右边 不放
那对于第二个砝码b 我们有 a+b a-b b 三种情况
我们把这三种情况的结果放入set
然后再用一个list集合遍历即可
每次放一个砝码之前 都将set集合中的结果 初始化到list集合中
用list集合中的每个元素，对砝码的三种情况进行计算，并放入set集合中1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
int a = scan.nextInt();
ArrayList<Integer> tmp = new ArrayList<>(set);
for (int b : tmp) {
set.add(b + a);
if (b != a) set.add(Math.abs(b - a));
}
set.add(a);
}
System.out.println(set.size());
}
}
试题 H: 杨辉三角形（20分）
HE
思路
杨辉三角的第i行第j个的数都是组合数C(i, j) （i，j从0开始）
C(n, 1) = n 对应斜着的第二行 也就是一定有解
由于杨辉三角左右对称C(a, b) == C(a, a-b)，又由于找第一次出现，因此一定在左边，右边不用看
1 ---> C(0, 0)
1
1 2 ---> C(2, 1)
1 3 ---> C(2n, n)
1 4 6 ---> C(4, 2)
1 5 10
1 6 15 20 —-> C(6, 3)
题目范围上限1E9，C(34, 17) > 1E9, C(32, 16) < 1E9，因此只要枚举前16个斜行即可
- 每个斜行是依次递增的C(n,m) m相同n越大 C(n,m)越大
- 每个横行从中间到两边是递减的
因此我们直接从中间对称轴倒序二分找起即可
C(r, k)对应的位置为：(r + 1) * r / 2 + k + 1
1 | import java.util.*; |
试题 I: 双向排序（25分）
思路
暴力解法会超时 所以这个题还是要找规律的(比赛肯定想不出来)
如果有两个连续的指令都是让我们降序排序，比如0 3和0 5，那么0 3这条指令就不需要进行操作，我们只需要执行操作区间更大的0 5
{ 1 2 3 4 5 6 7 }
0 3
{ 3 2 1 4 5 6 7 }
0 5
{ 5 4 3 2 1 6 7 }
再观察一下下面的两个操作
{ 1 2 3 4 5 6 7 }
0 5
{ 5 4 3 2 1 6 7 }
1 4
{ 5 4 3 1 2 6 7 }
0 5的意义就是将[1, 5]这个区间进行降序操作，而一开始整个区间[1, 7]都是升序的,我们要让[1,5]降序，那就只需要取[1,7]和[1,5]的交集，然后翻转这个交集，显然这个交集就是[1, 5]，翻转[1, 5]，于是我们得到了一个降序的[1, 5]区间，1 4的意义就是将[4, 7]这个区间进行升序操作，而最右边的区间[6, 7]已经是升序的了，并且里面所有的数字都比它们左边所有的数字都要大，所以[6, 7]区间的数字并不会变化，我们只需要接着取交集，取[1, 5]和[4, 7]的交集，得到一个[4, 5]的区间，翻转[4, 5]就是我们最终的答案。
要是上面两个操作之后，突然出现一个0 7的指令怎么办 显然执行0 7会覆盖之前两步的操作
所以不是连续的0操作最大就行了 而是要让后面比较大的0操作 覆盖掉之前操作区间所有比它小的操作 其间的1和0操作都会因为这个比较大的0操作而变得无效
经过上述这两步 我们就可以去掉很多无效操作 只保留有效操作 将这些有效操作入栈
栈维护出来之后，区间外部的东西就永远都不会动了，所以只需要一边缩区间一边填数字就行了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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
91
92
93
94
95
96import java.util.Scanner;
public class Main {
static int N = 100010;
static int n, m;
static PII[] stk = new PII[N];
static int[] ans = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int top = 0;//栈顶
while (m -- > 0) {
int p = sc.nextInt();
int q = sc.nextInt();
if (p == 0) {
//求出连续操作的最长前缀
while (top != 0 && stk[top].x == 0) q = Math.max(q, stk[top -- ].y);
while (top >= 2 && stk[top - 1].y <= q) top -= 2;
stk[ ++ top] = new PII(0, q);
} else if (top != 0) {
//求出连续操作的最长后缀
while (top != 0 && stk[top].x == 1) q = Math.min(q, stk[top --].y);
while (top >= 2 && stk[top - 1].y >= q) top -= 2;
stk[ ++ top] = new PII(1, q);
}
}
//k是递减变量，l为左边界，r为右边界
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++ ) {
if (stk[i].x == 0) {
//若为前缀操作，则(stk[i].y, r]不用操作，直接填数
while (r > stk[i].y && l <= r) ans[r -- ] = k --;
} else {
//若为后缀操作，则[l, stk[i].y)不用操作，直接填数
while (l < stk[i].y && l <= r) ans[l ++ ] = k --;
}
if (l > r) break;
}
//若l < r, 表示中间还有些数没有填上，操作次数为奇数，则下一次操作为前缀操作
if (top % 2 == 1) {
while (l <= r) ans[l ++ ] = k --;
} else {
while (l <= r) ans[r -- ] = k --;
}
for (int i = 1; i <= n; i ++ ) System.out.print(ans[i] + " ");
}
static class PII {
int x, y;
public PII(int x, int y) {
this.x = x;
this.y = y;
}
}
}
//暴力骗分能通过60%的案例
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
int m = scan.nextInt();
for (int i = 0; i < m; i++) {
int p = scan.nextInt();
int split = scan.nextInt();
if (p == 0) {
Arrays.sort(arr, 0, split, (o1, o2) -> o2 - o1);
} else {
Arrays.sort(arr, split - 1, n);
}
}
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+" ");
}
}
}
试题 J: 括号序列（25分）
摆烂了 有空再说
