第十三届蓝桥杯省赛 JAVA B组（真题解析+个人体会）（已更新完G题）

试题 A: 星期计算【填空题】

题目：

答案：7

解析：

此题直接对7求余即可。
public class Main { public static void main(String[] args) {
System.out.println(Math.pow(20, 22) % 7 + 6); } }
贴一个BigInteger的代码
import java.math.BigInteger; ​ public class Main { public static void
main(String[] args) { BigInteger bg = new BigInteger(20+""); BigInteger res =
bg.pow(22).remainder(BigInteger.valueOf(7)).add(BigInteger.valueOf(6));
System.out.println(res); } }
试题 B:【填空题】

题目：

答案：3138

这题我知道很多人把题目都给看错了，我认识好几个都是只看到了回文，没看到还有单调的条件。（大佬们都忙着做后面的题）

解析：

读题可以知道，回文数左右对称，所以只需判断是否回文，然后再判断左边的数单调不减，则右边的数一定单调不增。判断回文数可以使用双指针判断。
public class Main { public static void main(String[] args) { long start =
System.currentTimeMillis(); int count = 0; for (int i = 2022; i <= 2022222022;
i++) { if (isPalindrome(i) && check(i)) { count++; } } long end =
System.currentTimeMillis(); System.out.println(count); System.out.println("共用时"
+ (end - start) / 1000 % 60 + "秒");//测了一下时间用时40s } ​ private static boolean
check(int num) { String s = num + ""; for (int i = 0; i < s.length() / 2; i++)
{ if (s.charAt(i) > s.charAt(i + 1)) return false; } return true; } ​ private
static boolean isPalindrome(int num) { String s = num + ""; int n = s.length()
- 1; for (int l = 0, r = n; l < r; l++, r --) if (s.charAt(l) != s.charAt(r))
return false; return true; } } ​
试题 C:字符统计【编程题】

题目：

解析：

签到题,分别统计输出即可。
import java.util.Scanner; ​ public class Main { public static void
main(String[] args) { Scanner sc = new Scanner(System.in); String s =
sc.nextLine(); int[] arr = new int[26]; for (int i = 0; i < s.length(); i++) {
arr[s.charAt(i) - 'A']++; } int max = Integer.MIN_VALUE; for (int i = 0; i <
26; i++) { max = Math.max(max, arr[i]); } for (int i = 0; i < 26; i++) {
if(arr[i] == max) System.out.print((char) (i+'A')); } } }
试题 D:最少刷题数【编程题】

题目：

解析：

这个题我觉得虽然是个十分题，但是还是挺难的（也可能是我太菜了）。主要是要考虑的因素比较多，核心的想法应该是要计算出左边、右边与中间相等的数的个数，分情况判断每个数加上最小刷题数与中间数相等后需不需要+1。

这题当时给我做烦了，浪费了很多时间，我只考虑了和中间的相比，比它大就输出0，比它小就输出中间的数减去num[i]+1，并没有判断左右数与中间数相等的情况，没有全部AC。这里贴一下别人的代码
​ 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[] nums = new int[n]; int[] temp = new int[n]; for
(int i = 0; i < n; i++) { nums[i] = sc.nextInt(); temp[i] = nums[i]; } // 排序数组
Arrays.sort(temp); // 中间的下标 int midIndex = n / 2; // 中间的值 int midValue =
temp[midIndex]; ​ int midOption = 0; ​ int option = 0; // 左边和中值相同值的数量 int
sameLeft = 0; // 右边和中值相同值的数量 int sameRight = 0; ​ for (int i = midIndex - 1, j
= midIndex; i >= 0; i--, j++) { if (temp[i] == midValue) { sameLeft++; } if
(temp[j] == midValue) { sameRight++; } if (temp[i] != temp[j]) { break; } } ​
if (sameLeft >= sameRight) { option = 1; } if (sameLeft > sameRight) {
midOption = 1; } ​ for (int i = 0, len = nums.length; i < len; i++) { int count
= 0; if (nums[i] == midValue) { count = midOption; } else { count = midValue -
nums[i] + option; if (count < 0) { count = 0; } } if (i != n - 1) {
System.out.print(count + " "); } else { System.out.println(count); } ​ } } ​ } ​
我觉得这个代码的方法还是比较巧妙的hh

-------------------------------------------------------------分界线-----------------------------------------------------------

2023年2月7日更新

核心思想：排序找中位数，然后统计左右两边比mid大和比mid小的数，分类讨论。

(感觉像个模拟题)挺烦的十分题
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[] a = new int[n], tmp = new int[n]; for (int i = 0; i < n;
i++) { a[i] = sc.nextInt(); tmp[i] = a[i]; } Arrays.sort(tmp); int mid = tmp[n
/ 2]; int bg_cnt = 0, sml_cnt = 0; // 记录比mid大的和比mid小的数 for (int i = 0; i < n;
i++) if (a[i] < mid) sml_cnt ++; else if (a[i] > mid) bg_cnt ++; if (bg_cnt <
sml_cnt) { for (int i = 0; i < n; i++) if (a[i] < mid) System.out.print(mid -
a[i] + " "); else System.out.print(0 + " "); } else if (bg_cnt == sml_cnt){ for
(int i = 0; i < n; i++) if (a[i] < mid) System.out.print(mid - a[i] + 1 + " ");
else System.out.print(0 + " "); }else { for (int i = 0; i < n; i++) if (a[i] <=
mid) System.out.print(mid - a[i] + 1 + " "); else System.out.print(0 + " "); }
} }
试题 E: 求阶乘

题目：

解析

这题我又给想简单了，此题的数据范围非常大，所以可能只能过极个别样例。也不能直接从1到N枚举判断，突破口是数字中谁和谁相乘得到10，很容易想到2*5，2的个数肯定比5多，所以N的阶乘最后有多少0
就看N能分成多少5 。可以从1~N每个数都除以5，然后统计个5的个数，因为25/5也会得到5，所以需要用循环计算。

暴力法
import java.util.Scanner; ​ public class Main { //后面以0 结尾的一定是5！....(5的倍数的阶乘)
所以只需要判断5的倍数的阶乘 //(判断的数)/5 就是含有5的个数 也是阶乘后0的个数 public static void main(String[]
args) { Scanner sc = new Scanner(System.in); long k = sc.nextLong(); long
count; long a = 5;//直接从5的阶乘(120)开始判断 while (true) { long tempA = a; count = 0;
while (tempA > 0) { tempA /= 5; count += tempA; } if (count < k) { a += 5; }
else if (count == k) { System.out.println(a); break; } else {
System.out.println(-1); break; } } } } ​

-------------------------------------------------------------分界线-----------------------------------------------------------

2023年2月8日更新

二分

N 越大，末尾的 0 越多，具有单调性，可以使用二分找到答案。
import java.util.Scanner; public class Main { // 找N里面有多少个5(25里有两个5)
二分出一个>=k(找大于等于k的第一个位置)的最小的N，不存在则输出-1 public static void main(String[] args) {
Scanner sc = new Scanner(System.in); long l = 1, r = Long.MAX_VALUE-5; long k =
sc.nextLong(); while (l < r) { long mid = l + r >> 1; if (cal(mid) >= k) r =
mid; else l = mid + 1; } if (cal(r) == k) System.out.println(r); else
System.out.println(-1); } private static long cal(long num) { long cnt = 0;
while (num > 0) { cnt += num / 5; num /= 5; } return cnt; } }
试题 F: 最大子矩阵

题目：

解析：单调队列+二分

这题感觉比G题还难做，考试只能打打暴力了....
import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner;
// 枚举行x1,x2,二分最大的列数len,维护滑动窗口为大小为len的最大值和最小值 // 单调队列+二分 public class Main { //
矩阵中最大值-最小值<=limit && 元素个数最多 static int n, m, limit, ans; static int[][][] max,
min; //max[k][i][j]代表的含义是在第k列中，第i个元素到第j个的元素最大值是多少，min数组同理。 public static void
main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m
= sc.nextInt(); max = new int[m + 1][n + 1][n + 1]; min = new int[m + 1][n +
1][n + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
max[j][i][i] = min[j][i][i] = sc.nextInt(); limit = sc.nextInt(); for (int k =
1; k <= m; k++) for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) {
max[k][i][j] = Math.max(max[k][j][j], max[k][i][j - 1]); min[k][i][j] =
Math.min(min[k][j][j], min[k][i][j - 1]); } for (int x1 = 1; x1 <= n; x1++) for
(int x2 = x1; x2 <= n; x2++) { int l = 1, r = m; while (l < r) { int mid = l +
r + 1 >> 1; if (check(x1, x2, mid)) l = mid; else r = mid - 1; } if (check(x1,
x2, r)) ans = Math.max(ans, (x2 - x1 + 1) * r); } System.out.println(ans); }
private static boolean check(int x1, int x2, int k) { Deque<Integer> q_min =
new ArrayDeque<>(); Deque<Integer> q_max = new ArrayDeque<>(); // 枚举所有列 for
(int i = 1; i <= m; i++) { if (!q_min.isEmpty() && i - k >= q_min.peekFirst())
q_min.pollFirst(); while (!q_min.isEmpty() && min[i][x1][x2] <=
min[q_min.peekLast()][x1][x2]) q_min.pollLast(); q_min.addLast(i); if
(!q_max.isEmpty() && i - k >= q_max.peekFirst()) q_max.pollFirst(); while
(!q_max.isEmpty() && max[i][x1][x2] >= max[q_max.peekLast()][x1][x2])
q_max.pollLast(); q_max.addLast(i); //窗口大小为k if (i >= k &&
max[q_max.peekFirst()][x1][x2] - min[q_min.peekFirst()][x1][x2] <= limit)
return true; } return false; } }
试题 G:数组切分

题目：

 

解析：

算法1 回溯算法

枚举所有分割点
回溯算法可以枚举所有情况，当每个切分的子数组都满足题目要求时，答案++，但时间复杂度较高，会tle

小技巧
问 : 如何判断区间[i,j]是否可以组成一段连续的自然数？
答 ：只需 区间最大值 - 区间最小值 == j - i (区间长度)即可
import java.util.LinkedList; import java.util.Scanner; public class Main {
static LinkedList<Integer> path = new LinkedList<>(); static int res = 0, mod =
1000000007; public static void main(String[] args) { Scanner sc = new
Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for (int i = 0;
i < n; i++) a[i] = sc.nextInt(); dfs(a, 0); System.out.println(res % mod); }
private static void dfs(int[] a, int startindex) { int n = a.length; if
(startindex == n) { res ++; return; } for (int i = startindex; i < n; i++) { if
(check(a, startindex, i)) { path.add(i); dfs(a, i + 1); path.removeLast(); } }
} private static boolean check(int[] a, int l, int r) { int max =
Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int i = l; i <= r; i++) { if
(a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } return max - min == r -
l; } }
算法2 DP(正解)
import java.util.Scanner; public class Main { static int mod = 1000000007;
public static void main(String[] args) { // f[i]: 以a[i]结尾的切分合法数组的方法数量 Scanner
sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = sc.nextInt(); int[] f = new int[n + 1];
f[0] = 1; for (int i = 1; i <= n; i++) { int max = Integer.MIN_VALUE, min =
Integer.MAX_VALUE; for (int j = i; j > 0; j--) { max = Math.max(max, a[j]); min
= Math.min(min, a[j]); //如果a[j, i]是一段连续的自然数，那么就有以a[i]结尾的合法切分合法数量+=以a[j -
1]结尾的合法切分数量 //即f[i] += f[j - 1] if (max - min == i - j) f[i] = (f[i] + f[j -
1]) % mod; } } System.out.println(f[n]); } }

试题 H: 回忆迷宫

题目：

解析：

试题 I: 红绿灯

题目：

解析：

试题 J: 拉箱子

题目：

解析：

• « 上一篇：Homekit智能家居DIY设备-智能通断开关
• » 下一篇：滑动窗口算法