2022年第十三届蓝桥杯省赛JAVAB组个人题解
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目
试题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
}
}
结果对7取余是1n个7天后回到周六周六的一天后是周日题目要求用1-7表示。
答案
7
试题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;
}
}
纯暴力破解计算不过这道题有个坑题目只要求先单调不减后单调不增也就是2222这种连续的也在结果内代码中 a(); 方法先判断是否先单调不减后单调不增再判断是否对称写文时感觉顺序反下应该会快点这个方法还是得跑一会的。
答案
3138
试题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));
}
}
}
}
这道题先统计输入的字符串每个字符的次数然后遍历一遍找出最大次数再遍历一遍输出次数与最大次数相同的字符。
试题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);
}
}
}
}
}
这道题首先对输入的刷题数进行排序然后进行分情况考虑奇数情况下需要超过中间值才能满足全班刷题比他多的学生数不超过刷题比他少的学生数。偶数情况下需要等于中间偏大的值就可以满足条件。
试题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();
}
}
}
这段代码的结果通过结果不难发现规律六个为一组(第一组可以认为从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
1
5
2
10
3
15
4
20
5
-1
6
25
7
30
8
35
9
40
10
45
11
-1
12
50
13
55
14
60
15
65
16
70
17
-1
18
75
19
80
20
85
21
90
22
95
23
-1
所以可以将代码简化
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)));
}
}
}
试题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};
// xy为当前访问坐标limit为题目要求极限udlr为上下左右边界
// nnmm为地图大小dmaxdmin为当前访问过所有的点中最大值最小值
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;
}
}
}
}
}
因为只学过搜索但是不知道怎么判断是不是矩形所以判断矩形部分非常暴力思路是搜索一次就通过上下左右四个边界判断边界内的点是否都访问过如果都访问过则代表当前为矩形。
上下左右边界则是每次搜索都要判断这个点是否超过边界如果超过边界则将边界扩大。
从每个点都开始深搜最后输出所有点搜出的结果的最大值。
试题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刀到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();
}
}
}
这道题也只会暴力还不确定对思路是通过边界围出一个爱丽丝走过的最小的矩形同时矩形四个角也置空地每走一步判断是否超过边界超过将边界扩大。最后将地图输出爱丽丝走过的与四角为空格其余为 * 。
试题I: 红绿灯
这道题考试的时候写了一种能开氮气就直接开计算最后时间显然当时考虑简单了所以代码不放了。
试题J: 拉箱子
后两题都太难了我都没有写出来欢迎大佬评论区说下思路放下代码
总结
总的看今年还是比去年的难很多了后面还是得每天花点时间学习下算法最后祈祷今年能拿个省二吧
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |