2022年第十三届蓝桥杯省赛JAVAB组个人题解

2023-04-05

int for if

题目：试题A:星期计算试题B:山试题C:字符统计试题D:最少刷题数试题E:求阶乘试题F:最大子矩阵试题G:数组切分试题H:回忆迷宫试题I:红绿灯试题J:拉箱子总结试题A:星期计算importjava.math.BigInteger;publicclassMain{publicstaticvoidma

题目：

试题A: 星期计算
试题B: 山
试题C: 字符统计
试题D: 最少刷题数
试题E: 求阶乘
试题F: 最大子矩阵
试题G: 数组切分
试题H: 回忆迷宫
试题I: 红绿灯
试题J: 拉箱子
总结

试题A: 星期计算

import java.math.BigInteger;

public class Main {
public static void main(String[] args) {
BigInteger n = new BigInteger("20");
for (int i = 1; i < 22; i++) {
n = n.multiply(BigInteger.valueOf(20L));
}
// 6 7 1 2 3 4 5
System.out.println(n.remainder(BigInteger.valueOf(7L))); // 1
}
}
1
2
3
4
5
6
7
8
9
10
11
12

结果对7取余是1，n个7天后回到周六，周六的一天后是周日，题目要求用1-7表示。
答案：

7
1

试题B: 山

public class Main {
public static void main(String[] args) {
int num = 0;
for (int i = 2022; i <= 2022222022; i++) {
if (a(i)) {
num++;
}
}
System.out.println(num);//3138
}

public static Boolean a(int n) {
Boolean flag = true;
char[] chars = String.valueOf(n).toCharArray();
for (int i = 1; i < chars.length / 2 + (chars.length % 2); i++) {
if (chars[i] < chars[i - 1]) {
return false;
}
}

for (int i = 0; i < chars.length / 2; i++) {
if (chars[i] != chars[chars.length - i - 1]) {
return false;
}
}
return true;
}
}
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

纯暴力破解计算，不过这道题有个坑，题目只要求先单调不减，后单调不增，也就是2222这种连续的也在结果内，代码中 a(); 方法先判断是否先单调不减，后单调不增，再判断是否对称，写文时感觉顺序反下应该会快点，这个方法还是得跑一会的。
答案：

3138
1

试题C: 字符统计

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] chars = s.toCharArray();
int[] arr = new int[26];
for (int i = 0; i < chars.length; i++) {
arr[(int) chars[i] - 65]++;
}
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == max) {
System.out.print((char) (i + 65));
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这道题先统计输入的字符串每个字符的次数，然后遍历一遍找出最大次数，再遍历一遍输出次数与最大次数相同的字符。

试题D: 最少刷题数

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
LinkedList<Integer> list = new LinkedList<>();

for (int i = 0; i < n; i++) {
list.add(sc.nextInt());
}
Object[] arr = list.toArray();
list.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 > o2 ? 1 : -1;
}
});// 输入排序完成
int length = list.size(), num = list.get(length / 2);
if (length % 2 == 1) {
if ((int) arr[0] < num) {
System.out.print((num - (int) arr[0] + 1));
} else {
System.out.print(0);
}
for (int i = 1; i < arr.length; i++) {
if ((int) arr[i] < num) {
System.out.print(" " + (num - (int) arr[i] + 1));
} else {
System.out.print(" " + 0);
}
}
} else {
if ((int) arr[0] < num) {
System.out.print(num - (int) arr[0]);
} else {
System.out.print(0);
}
for (int i = 1; i < arr.length; i++) {
if ((int) arr[i] < num) {
System.out.print(" " + (num - (int) arr[i]));
} else {
System.out.print(" " + 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

这道题首先对输入的刷题数进行排序，然后进行分情况考虑，奇数情况下需要超过中间值才能满足全班刷题比他多的学生数不超过刷题比他少的学生数。偶数情况下需要等于中间偏大的值就可以满足条件。

试题E: 求阶乘

import java.math.BigInteger;
import java.util.Scanner;

public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int k = 1; k < 100; k++) {
// n表示当前0的位数，k表示需要0的位数
// int k = sc.nextInt(), n = 0;
int n = 0;

BigInteger sum = BigInteger.ONE, i = BigInteger.ZERO;
while (n < k) {
i = i.add(BigInteger.ONE);
sum = sum.multiply(i);//此时sum是i的去尾0阶乘

// 给sum去0
while (sum.remainder(BigInteger.TEN).toString().equals("0")) {
sum = sum.divide(BigInteger.TEN);
n++;
}
}
System.out.println(k);
if (n == k) {
System.out.println(i);
} else {
System.out.println(-1);
}
System.out.println();
}
}
}
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

这段代码的结果，通过结果不难发现规律，六个为一组(第一组可以认为从0开始)。首先(n+1)%6==0，则输出-1；其他数为 (n-组号)5，组号从0开始，每6个组号+1
如3是第一组（组号为0），所以3的值为（3-0）* 5=15，
再比如14为第三组（组号为2），所以14对应的值为（14-2）* 5=120。
计算组号可通过 n/6 计算，还是上面的例子， 3/6=0 ，14/6=2

所以可以将代码简化

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String k = sc.nextLine();
BigInteger bigK = new BigInteger(k);
BigInteger n = bigK.divide(BigInteger.valueOf(6L));
if (bigK.subtract(BigInteger.valueOf(5L)).remainder(BigInteger.valueOf(6L)).toString().equals("0")) {
System.out.println(-1);
} else {
System.out.println(bigK.subtract(n).multiply(BigInteger.valueOf(5L)));
}

}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

试题F: 最大子矩阵

import java.util.Scanner;

public class Main {
public static int[][] map;
public static int[][] v;

public static int max;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
int limit = sc.nextInt();

Integer maxx = 0;
// 从地图中每个点开始搜素
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 每次搜索把这个max初始化为0
max = 0;
v = new int[n][m];
dfs(i, j, limit, i, i, j, j, n, m, map[i][j], map[i][j]);
// 搜索结束与之前点搜出来的最大值比较
if (maxx < max) {
maxx = max;
}
}
}
System.out.println(maxx);
}

public static int[] px = {0, 0, 1, -1};
public static int[] py = {1, -1, 0, 0};

// x，y为当前访问坐标，limit为题目要求极限，udlr为上下左右边界
// nn，mm为地图大小，dmax，dmin为当前访问过所有的点中最大值最小值
public static void dfs(int x, int y, int limit, int u, int d, int l, int r, int nn, int mm, int dmax, int dmin) {
// 判断是不是矩形
Boolean flag = true;
for (int i = u; i <= d; i++) {
for (int j = l; j <= r; j++) {
if (v[i][j] == 0) {
flag = false;
i = d + 1;
break;
}
}
}
if (flag) {
int m = (d - u + 1) * (r - l + 1);

if (m > max) {
max = m;
}
}
int xx, yy;
for (int i = 0; i < 4; i++) {
xx = x + px[i];
yy = y + py[i];
if (xx >= 0 && xx < nn && yy >= 0 && yy < mm && v[xx][yy] == 0) {
//考虑极限
if (map[xx][yy] > dmax) {
dmax = map[xx][yy];
}
if (map[xx][yy] < dmin) {
dmin = map[xx][yy];
}
// 满足极限要求
if (dmax - dmin <= limit) {
v[xx][yy] = 1;
// 判断下个访问的点是否超出边界，如果超出则扩大边界
if (u > xx)
u = xx;
if (l > yy)
l = yy;
if (d < xx)
d = xx;
if (r < yy)
r = yy;
dfs(xx, yy, limit, u, d, l, r, nn, mm, dmax, dmin);
// 这里搜索结束应该忘记把当前最大值最小值回溯了
v[xx][yy] = 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

因为只学过搜索，但是不知道怎么判断是不是矩形，所以判断矩形部分非常暴力，思路是搜索一次就通过上下左右四个边界判断边界内的点是否都访问过，如果都访问过则代表当前为矩形。
上下左右边界则是每次搜索都要判断这个点是否超过边界，如果超过边界则将边界扩大。
从每个点都开始深搜，最后输出所有点搜出的结果的最大值。

试题G: 数组切分

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
public static int[] arr;
public static int[] v;
public static BigInteger summ = BigInteger.ZERO;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 1; i < n; i++) {
// 初始化标记数组
v = new int[n - 1];
// 从第0刀，切的总数1-(n-1)进行遍历
dfs(0, i);
}
// 因为是1-n的排列，所以一定存在一刀不切且成立的情况
System.out.println(summ.add(BigInteger.ONE));
}

public static void dfs(int n, int sum) {
// 切的次数n与总次数sum相等
if (n == sum) {
// 当前切段开始位置和结束位置
int start = 0, stop = 0;
Boolean flag = true;
// 遍历标记数组
for (int i = 0; i < v.length; i++) {
// 如果标记数组为1，代表从数组指定位置后方切割
if (v[i] == 1) {
stop = i + 1;
LinkedList<Integer> list = new LinkedList<>();
for (int j = start; j < stop; j++) {
list.add(arr[j]);
}
list.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 > o2 ? 1 : -1;
}
});
// 排序后将linkedlist变为arraylist加快遍历速度
ArrayList<Integer> aList = new ArrayList<>(list);
for (int i1 = 1; i1 < aList.size(); i1++) {
// 排序后的list如果相邻两个数相差不为1，代表集合不连续，这种切割情况不满足题意
if (aList.get(i1) - aList.get(i1 - 1) != 1) {
flag = false;
i = v.length;
break;
}
}
start = i + 1;
}
}
// 判断切的最后一刀之后是否连续
LinkedList<Integer> list = new LinkedList<>();
for (int j = start; j < arr.length; j++) {
list.add(arr[j]);
}
list.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 > o2 ? 1 : -1;
}
});
// 排序后将linkedlist变为arraylist加快遍历速度
ArrayList<Integer> aList = new ArrayList<>(list);
for (int i1 = 1; i1 < aList.size(); i1++) {
// 排序后的list如果相邻两个数相差不为1，代表集合不连续，这种切割情况不满足题意
if (aList.get(i1) - aList.get(i1 - 1) != 1) {
flag = false;
break;
}
}
if (flag) {
summ = summ.add(BigInteger.ONE);
// 输出切割情况
for (int i = 0; i < v.length; i++) {
System.out.print(v[i] + ",");
}
System.out.println();
if (summ.compareTo(BigInteger.valueOf(1000000007L)) == 0) {
summ = BigInteger.ZERO;
System.out.println(1);
}
}
// 达到切的次数，结束搜索
return;
}
// 保证每次切的都在切过的地方的后方，防止重复
int i = 0;
for (int i1 = 0; i1 < v.length; i1++) {
if (v[i1] == 1) {
i = i1 + 1;
}
}
for (; i < v.length; i++) {
if (v[i] == 0) {
v[i] = 1;
dfs(n + 1, sum);
v[i] = 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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

这道题思路是首先考虑能切几刀，然后找出1刀到n-1刀切的所有情况。
切的位置从前往后依次选择，注意的是，如果第一刀在第二个位置，那么要小心第二刀切在第一个位置，要避免这种情况，否则会与第一刀在第一个位置第二刀在第二个位置重复。
写法依旧暴力，所以就算交上估计也对不了，测试100000 输入1-100000，跑3个小时没跑出来放弃了，但是20 1-20还是很快能出来的。

试题H: 回忆迷宫

import java.util.Arrays;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
char[] step = sc.next().toCharArray();
char[][] map = new char[204][204];
for (int i = 0; i < map.length; i++) {
Arrays.fill(map[i], '*');
}

// 当前坐标
int x = 100, y = 100;
map[x][y] = ' ';
// 上下左右边界
int u = 99, d = 101, l = 99, r = 101;
for (int i = 0; i < step.length; i++) {
switch (step[i]) {
case 'U':
x--;
if (u >= x)
u = x - 1;
map[x][y] = ' ';
break;
case 'L':
y--;
if (l >= y)
l = y - 1;
map[x][y] = ' ';
break;
case 'D':
x++;
if (d <= x)
d = x + 1;
map[x][y] = ' ';
break;
case 'R':
y++;
if (r <= y)
r = y + 1;
map[x][y] = ' ';
break;
}
}
map[u][l] = ' ';
map[u][r] = ' ';
map[d][l] = ' ';
map[d][r] = ' ';
for (int i = u; i <= d; i++) {
for (int j = l; j <= r; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}

}
}
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