当前位置：首页 > news >正文

2022年第十三届蓝桥杯省赛B组Java题解

news 2025/5/5 7:14:19

2022年第十三届蓝桥杯省赛B组Java题解

个人心得：

2022年蓝桥杯省赛Java B组共包含10道题目，其中填空题2道（A、B），编程题8道（C-J）。题目覆盖数论、字符串处理、动态规划、数据结构等核心知识点，对算法思维和编程能力要求较高。本文提供所有题目的详细解析与优化代码，代码逻辑简洁，注释清晰，部分题目提供多种解法，适合备赛复习与自测。

试题A：星期计算（填空题）

题目描述
已知今天是星期六，请问 $20^{22}$ 天后是星期几？用1-7表示周一到周日。

解题思路
核心是计算 $20^{22} \mod 7$ 。利用快速幂取模避免数值溢出：

根据模运算性质： $\times b) \mod p = [(a \mod p) \times (b \mod p)] \mod p$
循环计算每一步的取模结果，最后加上6（星期六）再取模7。

优化代码

public class Main {public static void main(String[] args) {int ans = 1;for (int i = 0; i < 22; i++) {ans = (ans * 20) % 7; // 逐步取模防止溢出}int result = (6 + ans) % 7;System.out.println(result == 0 ? 7 : result); // 处理余数为0的情况}
}

答案
7

试题B：山（填空题）

题目描述
在区间[2022, 2022222022]中，统计满足以下条件的数：

回文数；
前半部分数字非递减（如12321的前半部分123是递增的）。

解题思路
暴力枚举每个数会超时，优化策略：

生成回文数：构造前半部分，生成对应的回文数，减少无效遍历。
单调性检查：仅需验证前半部分是否为非递减序列。

优化代码

public class Main {public static void main(String[] args) {int cnt = 0;// 生成前五位的前缀（2022至99999）for (int i = 2022; i <= 99999; i++) {String prefix = String.valueOf(i);if (!isNonDecreasing(prefix)) continue;// 生成两种回文形式：全对称（如12321）和半对称（如123321）String full = prefix + new StringBuilder(prefix).reverse().toString();String half = prefix + new StringBuilder(prefix.substring(0, prefix.length() - 1)).reverse().toString();checkAndCount(full, cnt);checkAndCount(half, cnt);}System.out.println(cnt);}// 检查是否非递减private static boolean isNonDecreasing(String s) {for (int i = 0; i < s.length() - 1; i++) {if (s.charAt(i) > s.charAt(i + 1)) return false;}return true;}// 验证回文数是否在范围内private static void checkAndCount(String s, int cnt) {long num = Long.parseLong(s);if (num >= 2022 && num <= 2022222022) cnt++;}
}

答案
3138

试题C：字符统计（编程题）

题目描述
给定大写字符串S，输出出现次数最多的字母（多个时按字母序排列）。

解题思路

使用数组统计频率；
遍历数组找到最大值；
按字母序收集所有频率为最大值的字符。

优化代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.next();int[] count = new int[26];int max = 0;// 统计频率for (char c : s.toCharArray()) {count[c - 'A']++;max = Math.max(max, count[c - 'A']);}// 收集结果StringBuilder res = new StringBuilder();for (int i = 0; i < 26; i++) {if (count[i] == max) res.append((char) ('A' + i));}System.out.println(res);}
}

试题D：最少刷题数（编程题）

题目描述
N名学生，每人刷题数为 $A_i$ 。求每个学生至少再刷多少题，使得比他刷题多的人数不超过比他少的人数。

解题思路

排序后找到中位数位置；
若当前学生题数小于中位数，则需补到中位数+1。

优化代码

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();int[] arr = new int[n], sorted = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();sorted[i] = arr[i];}Arrays.sort(sorted);int mid = sorted[n / 2]; // 中位数位置for (int num : arr) {System.out.print(num >= mid ? 0 : mid - num + 1 + " ");}}
}

试题E：求阶乘（编程题）

题目描述
找到最小的N使得N!末尾恰好有K个0，不存在则输出-1。

解题思路
阶乘末尾的0由因子5的数量决定（因为2的数量总是足够）。通过二分查找确定满足条件的N。

优化代码

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long k = sc.nextLong();long left = 5, right = 5 * k, ans = -1;while (left <= right) {long mid = (left + right) / 2;long cnt = countZeros(mid);if (cnt >= k) {if (cnt == k) ans = mid;right = mid - 1;} else left = mid + 1;}System.out.println(ans);}// 计算n!中因子5的数量private static long countZeros(long n) {long cnt = 0;while (n > 0) {cnt += n / 5;n /= 5;}return cnt;}
}

试题F：最大子矩阵（编程题）

题目描述
给定一个矩阵，找到满足稳定度（最大值与最小值之差）不超过限制的最大子矩阵面积。

解题思路

滑动窗口+单调队列：逐行处理，用单调队列维护当前窗口的最大值和最小值。
枚举列范围：对于每一列，计算行方向的滑动窗口，统计满足条件的最大面积。

优化代码

import java.util.Deque;
import java.util.LinkedList;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(), limit = sc.nextInt();int[][] matrix = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = sc.nextInt();}}int maxArea = 0;for (int top = 0; top < n; top++) {int[] rowMin = new int[m], rowMax = new int[m];Arrays.fill(rowMin, Integer.MAX_VALUE);Arrays.fill(rowMax, Integer.MIN_VALUE);for (int bottom = top; bottom < n; bottom++) {// 更新当前行的min和maxfor (int j = 0; j < m; j++) {rowMin[j] = Math.min(rowMin[j], matrix[bottom][j]);rowMax[j] = Math.max(rowMax[j], matrix[bottom][j]);}// 滑动窗口计算列范围Deque<Integer> minDeque = new LinkedList<>(), maxDeque = new LinkedList<>();int left = 0;for (int right = 0; right < m; right++) {while (!minDeque.isEmpty() && rowMin[right] <= rowMin[minDeque.peekLast()]) minDeque.pollLast();minDeque.addLast(right);while (!maxDeque.isEmpty() && rowMax[right] >= rowMax[maxDeque.peekLast()]) maxDeque.pollLast();maxDeque.addLast(right);// 收缩左边界直到稳定度<=limitwhile (rowMax[maxDeque.peekFirst()] - rowMin[minDeque.peekFirst()] > limit) {if (maxDeque.peekFirst() == left) maxDeque.pollFirst();if (minDeque.peekFirst() == left) minDeque.pollFirst();left++;}int area = (bottom - top + 1) * (right - left + 1);maxArea = Math.max(maxArea, area);}}}System.out.println(maxArea);}
}

试题G：数组切分（编程题）

题目描述
将数组分成若干段，每段是连续自然数的排列，求分割方式数目。

解题思路

动态规划：定义dp[i]表示前i个元素的切分方案数。
检查连续段：对于每个j，若j+1到i是连续自然数，则累加dp[j]到dp[i]。

优化代码

public class Main {static final int MOD = (int)1e9 + 7;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n + 1];for (int i = 1; i <= n; i++) arr[i] = sc.nextInt();int[] dp = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; i++) {int max = arr[i], min = arr[i];for (int j = i; j >= 1; j--) {max = Math.max(max, arr[j]);min = Math.min(min, arr[j]);if (max - min == i - j) { // 连续自然数的条件dp[i] = (dp[i] + dp[j - 1]) % MOD;}}}System.out.println(dp[n]);}
}

试题H：回忆迷宫（编程题）

题目描述
根据移动路径生成迷宫，确保围墙最少且路径唯一。

解题思路

模拟路径：记录所有经过的坐标，确定迷宫边界。
填充墙壁：遍历边界，判断每个位置是否需要围墙。

优化代码

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class Main {static int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);String path = sc.next();Set<String> visited = new HashSet<>();int x = 0, y = 0;visited.add(x + "," + y);for (char c : path.toCharArray()) {if (c == 'U') x--;else if (c == 'D') x++;else if (c == 'L') y--;else if (c == 'R') y++;visited.add(x + "," + y);}// 确定迷宫边界int minX = -1, maxX = 1, minY = -1, maxY = 1;for (String pos : visited) {String[] s = pos.split(",");int px = Integer.parseInt(s[0]), py = Integer.parseInt(s[1]);minX = Math.min(minX, px - 1);maxX = Math.max(maxX, px + 1);minY = Math.min(minY, py - 1);maxY = Math.max(maxY, py + 1);}// 生成迷宫for (int i = minX; i <= maxX; i++) {StringBuilder sb = new StringBuilder();for (int j = minY; j <= maxY; j++) {if (visited.contains(i + "," + j)) sb.append(' ');else {boolean isWall = false;for (int[] d : dirs) {int nx = i + d[0], ny = j + d[1];if (visited.contains(nx + "," + ny)) {isWall = true;break;}}sb.append(isWall ? '*' : ' ');}}System.out.println(sb);}}
}

试题I：红绿灯（编程题）

题目描述
计算在红绿灯路口等待的最短时间，考虑氮气加速的冷却时间。

解题思路

动态规划：状态dp[i][k]表示到达第i个红绿灯时剩余k次氮气的最短时间。
处理红绿灯周期：计算等待时间，并选择是否使用氮气加速。

优化代码

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(); // m为氮气次数int[][] lights = new int[n][3];for (int i = 0; i < n; i++) {lights[i][0] = sc.nextInt(); // 距离lights[i][1] = sc.nextInt(); // 红灯时间lights[i][2] = sc.nextInt(); // 绿灯时间}long[][] dp = new long[n + 1][m + 1];Arrays.fill(dp[0], 0);for (int i = 1; i <= n; i++) {int dist = lights[i-1][0];int red = lights[i-1][1], green = lights[i-1][2];int cycle = red + green;for (int k = 0; k <= m; k++) {dp[i][k] = Long.MAX_VALUE;// 不使用氮气long arriveTime = dp[i-1][k] + dist;long wait = (arriveTime % cycle < red) ? (red - arriveTime % cycle) : 0;dp[i][k] = Math.min(dp[i][k], arriveTime + wait);// 使用氮气（k>0）if (k > 0) {arriveTime = dp[i-1][k-1] + dist / 2;wait = (arriveTime % cycle < red) ? (red - arriveTime % cycle) : 0;dp[i][k] = Math.min(dp[i][k], arriveTime + wait + (i < n ? 0 : 0)); // 冷却时间已在状态中处理}}}long ans = Long.MAX_VALUE;for (long num : dp[n]) ans = Math.min(ans, num);System.out.println(ans);}
}

试题J：拉箱子（编程题）

题目描述
经典的推箱子游戏变种，使用BFS处理人物和箱子的移动状态。

解题思路

BFS+状态压缩：记录箱子和人物的位置，以及移动步数。
状态转移：分箱子的移动和人物的移动，确保路径可达。

优化代码

import java.util.*;public class Main {static int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};static char[][] grid;static int n, m;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt(); m = sc.nextInt();grid = new char[n][m];int[] start = new int[4]; // 人物x,y; 箱子x,yint[] target = new int[2];for (int i = 0; i < n; i++) {String line = sc.next();for (int j = 0; j < m; j++) {grid[i][j] = line.charAt(j);if (grid[i][j] == 'S') {start[0] = i; start[1] = j;} else if (grid[i][j] == 'B') {start[2] = i; start[3] = j;} else if (grid[i][j] == 'T') {target[0] = i; target[1] = j;}}}Queue<int[]> queue = new LinkedList<>();boolean[][][][] visited = new boolean[n][m][n][m];queue.add(new int[]{start[0], start[1], start[2], start[3], 0});visited[start[0]][start[1]][start[2]][start[3]] = true;int ans = -1;while (!queue.isEmpty()) {int[] state = queue.poll();int px = state[0], py = state[1], bx = state[2], by = state[3], step = state[4];if (bx == target[0] && by == target[1]) {ans = step;break;}// 人物移动for (int[] d : dirs) {int nx = px + d[0], ny = py + d[1];if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '#') continue;// 如果移动到箱子位置，则推动箱子if (nx == bx && ny == by) {int nbx = bx + d[0], nby = by + d[1];if (nbx < 0 || nbx >= n || nby < 0 || nby >= m || grid[nbx][nby] == '#') continue;if (!visited[nx][ny][nbx][nby]) {visited[nx][ny][nbx][nby] = true;queue.add(new int[]{nx, ny, nbx, nby, step + 1});}} else {if (!visited[nx][ny][bx][by]) {visited[nx][ny][bx][by] = true;queue.add(new int[]{nx, ny, bx, by, step + 1});}}}}System.out.println(ans);}
}