devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：IT小白 | 2024-04-20 06:22:29

赞

踩

蓝桥杯javab组真题解析

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

题目：

答案：7

解析：

此题直接对7求余即可。

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         System.out.println(Math.pow(20, 22) % 7 + 6);
  4.     }
  5. }

贴一个BigInteger的代码

  1. import java.math.BigInteger;
  2. ​
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         BigInteger bg = new BigInteger(20+"");
  6.         BigInteger res = bg.pow(22).remainder(BigInteger.valueOf(7)).add(BigInteger.valueOf(6));
  7.         System.out.println(res);
  8.     }
  9. }

试题 B:【填空题】

题目：

答案：3138

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

解析：

读题可以知道，回文数左右对称，所以只需判断是否回文，然后再判断左边的数单调不减，则右边的数一定单调不增。判断回文数可以使用双指针判断。

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         long start = System.currentTimeMillis();
  4.         int count = 0;
  5.         for (int i = 2022; i <= 2022222022; i++) {
  6.             if (isPalindrome(i) && check(i)) {
  7.                 count++;
  8.             }
  9.         }
  10.         long end = System.currentTimeMillis();
  11.         System.out.println(count);
  12.         System.out.println("共用时" + (end - start) / 1000 % 60 + "秒");//测了一下时间用时40s
  13.     }
  14. ​
  15.     private static boolean check(int num) {
  16.         String s = num + "";
  17.         for (int i = 0; i < s.length() / 2; i++) {
  18.             if (s.charAt(i) > s.charAt(i + 1)) return false;
  19.         }
  20.         return true;
  21.     }
  22. ​
  23.     private static boolean isPalindrome(int num) {
  24.         String s = num + "";
  25.         int n = s.length() - 1;
  26.         for (int l = 0, r = n; l < r; l++, r --)
  27.             if (s.charAt(l) != s.charAt(r)) return false;
  28.         return true;
  29.     }
  30. }
  31. ​

试题 C:字符统计【编程题】

题目：

解析：

签到题,分别统计输出即可。

  1. import java.util.Scanner;
  2. ​
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         String s = sc.nextLine();
  7.         int[] arr = new int[26];
  8.         for (int i = 0; i < s.length(); i++) {
  9.             arr[s.charAt(i) - 'A']++;
  10.         }
  11.         int max = Integer.MIN_VALUE;
  12.         for (int i = 0; i < 26; i++) {
  13.             max = Math.max(max, arr[i]);
  14.         }
  15.         for (int i = 0; i < 26; i++) {
  16.             if(arr[i] == max) System.out.print((char) (i+'A'));
  17.         }
  18.     }
  19. }

试题 D:最少刷题数【编程题】

题目：

解析：

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

这题当时给我做烦了，浪费了很多时间，我只考虑了和中间的相比，比它大就输出0，比它小就输出中间的数减去num[i]+1，并没有判断左右数与中间数相等的情况，没有全部AC。这里贴一下别人的代码

  1. ​
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4. ​
  5. public class Main {
  6. ​
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  10.         int[] nums = new int[n];
  11.         int[] temp = new int[n];
  12.         for (int i = 0; i < n; i++) {
  13.             nums[i] = sc.nextInt();
  14.             temp[i] = nums[i];
  15.         }
  16.         // 排序数组
  17.         Arrays.sort(temp);
  18.         // 中间的下标
  19.         int midIndex = n / 2;
  20.         // 中间的值
  21.         int midValue = temp[midIndex];
  22. ​
  23.         int midOption = 0;
  24. ​
  25.         int option = 0;
  26.         // 左边和中值相同值的数量
  27.         int sameLeft = 0;
  28.         // 右边和中值相同值的数量
  29.         int sameRight = 0;
  30. ​
  31.         for (int i = midIndex - 1, j = midIndex; i >= 0; i--, j++) {
  32.             if (temp[i] == midValue) {
  33.                 sameLeft++;
  34.             }
  35.             if (temp[j] == midValue) {
  36.                 sameRight++;
  37.             }
  38.             if (temp[i] != temp[j]) {
  39.                 break;
  40.             }
  41.         }
  42. ​
  43.         if (sameLeft >= sameRight) {
  44.             option = 1;
  45.         }
  46.         if (sameLeft > sameRight) {
  47.             midOption = 1;
  48.         }
  49. ​
  50.         for (int i = 0, len = nums.length; i < len; i++) {
  51.             int count = 0;
  52.             if (nums[i] == midValue) {
  53.                 count = midOption;
  54.             } else {
  55.                 count = midValue - nums[i] + option;
  56.                 if (count < 0) {
  57.                     count = 0;
  58.                 }
  59.             }
  60.             if (i != n - 1) {
  61.                 System.out.print(count + " ");
  62.             } else {
  63.                 System.out.println(count);
  64.             }
  65. ​
  66.         }
  67.     }
  68. ​
  69. }
  70. ​

我觉得这个代码的方法还是比较巧妙的hh

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

2023年2月7日更新

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

(感觉像个模拟题)挺烦的十分题

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int[] a = new int[n], tmp = new int[n];
  9.         for (int i = 0; i < n; i++) {
  10.             a[i] = sc.nextInt();
  11.             tmp[i] = a[i];
  12.         }
  13.         Arrays.sort(tmp);
  14.         int mid = tmp[n / 2];
  15.         int bg_cnt = 0, sml_cnt = 0; // 记录比mid大的和比mid小的数
  16.         for (int i = 0; i < n; i++)
  17.             if (a[i] < mid) sml_cnt ++;
  18.             else if (a[i] > mid) bg_cnt ++;
  19.  
  20.         if (bg_cnt < sml_cnt) {
  21.             for (int i = 0; i < n; i++)
  22.                 if (a[i] < mid) System.out.print(mid - a[i] + " ");
  23.                 else System.out.print(0 + " ");
  24.         } else if (bg_cnt == sml_cnt){
  25.             for (int i = 0; i < n; i++)
  26.                 if (a[i] < mid) System.out.print(mid - a[i] + 1 + " ");
  27.                 else System.out.print(0 + " ");
  28.         }else {
  29.             for (int i = 0; i < n; i++)
  30.                 if (a[i] <= mid) System.out.print(mid - a[i] + 1 + " ");
  31.                 else System.out.print(0 + " ");
  32.         }
  33.     }
  34. }

试题 E: 求阶乘

题目：

解析

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

暴力法

  1. import java.util.Scanner;
  2. ​
  3. public class Main {
  4.     //后面以0 结尾的一定是5！....(5的倍数的阶乘) 所以只需要判断5的倍数的阶乘
  5.     //(判断的数)/5 就是含有5的个数 也是阶乘后0的个数
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         long k = sc.nextLong();
  9.         long count;
  10.         long a = 5;//直接从5的阶乘(120)开始判断
  11.         while (true) {
  12.             long tempA = a;
  13.             count = 0;
  14.             while (tempA > 0) {
  15.                 tempA /= 5;
  16.                 count += tempA;
  17.             }
  18.             if (count < k) {
  19.                 a += 5;
  20.             } else if (count == k) {
  21.                 System.out.println(a);
  22.                 break;
  23.             } else {
  24.                 System.out.println(-1);
  25.                 break;
  26.             }
  27.         }
  28.     }
  29. }
  30. ​

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

2023年2月8日更新

二分

N 越大，末尾的 0 越多，具有单调性，可以使用二分找到答案。

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     // 找N里面有多少个5(25里有两个5) 二分出一个>=k(找大于等于k的第一个位置)的最小的N，不存在则输出-1
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         long l = 1, r = Long.MAX_VALUE-5;
  8.         long k = sc.nextLong();
  9.         while (l < r) {
  10.             long mid = l + r >> 1;
  11.             if (cal(mid) >= k) r = mid;
  12.             else l = mid + 1;
  13.         }
  14.         if (cal(r) == k) System.out.println(r);
  15.         else System.out.println(-1);
  16.     }
  17.  
  18.     private static long cal(long num) {
  19.         long cnt = 0;
  20.         while (num > 0) {
  21.             cnt += num / 5;
  22.             num /= 5;
  23.         }
  24.         return cnt;
  25.     }
  26. }

试题 F: 最大子矩阵

题目：

解析：单调队列+二分

这题感觉比G题还难做，考试只能打打暴力了....

  1. import java.util.ArrayDeque;
  2. import java.util.Deque;
  3. import java.util.Scanner;
  4. // 枚举行x1,x2,二分最大的列数len,维护滑动窗口为大小为len的最大值和最小值
  5. // 单调队列+二分
  6. public class Main {
  7.     // 矩阵中最大值-最小值<=limit && 元素个数最多
  8.     static int n, m, limit, ans;
  9.     static int[][][] max, min;
  10.     //max[k][i][j]代表的含义是在第k列中，第i个元素到第j个的元素最大值是多少，min数组同理。
  11.     public static void main(String[] args) {
  12.         Scanner sc = new Scanner(System.in);
  13.         n = sc.nextInt(); m = sc.nextInt();
  14.         max = new int[m + 1][n + 1][n + 1]; min = new int[m + 1][n + 1][n + 1];
  15.         for (int i = 1; i <= n; i++)
  16.             for (int j = 1; j <= m; j++)
  17.                 max[j][i][i] = min[j][i][i] = sc.nextInt();
  18.         limit = sc.nextInt();
  19.  
  20.         for (int k = 1; k <= m; k++)
  21.             for (int i = 1; i <= n; i++)
  22.                 for (int j = i + 1; j <= n; j++) {
  23.                     max[k][i][j] = Math.max(max[k][j][j], max[k][i][j - 1]);
  24.                     min[k][i][j] = Math.min(min[k][j][j], min[k][i][j - 1]);
  25.                 }
  26.  
  27.         for (int x1 = 1; x1 <= n; x1++)
  28.             for (int x2 = x1; x2 <= n; x2++) {
  29.                 int l = 1, r = m;
  30.                 while (l < r) {
  31.                     int mid = l + r + 1 >> 1;
  32.                     if (check(x1, x2, mid)) l = mid;
  33.                     else r = mid - 1;
  34.                 }
  35.                 if (check(x1, x2, r)) ans = Math.max(ans, (x2 - x1 + 1) * r);
  36.             }
  37.         System.out.println(ans);
  38.     }
  39.     
  40.     private static boolean check(int x1, int x2, int k) {
  41.         Deque<Integer> q_min = new ArrayDeque<>();
  42.         Deque<Integer> q_max = new ArrayDeque<>();
  43.         // 枚举所有列
  44.         for (int i = 1; i <= m; i++) {
  45.             if (!q_min.isEmpty() && i - k >= q_min.peekFirst()) q_min.pollFirst();
  46.             while (!q_min.isEmpty() && min[i][x1][x2] <= min[q_min.peekLast()][x1][x2]) q_min.pollLast();
  47.             q_min.addLast(i);
  48.  
  49.             if (!q_max.isEmpty() && i - k >= q_max.peekFirst()) q_max.pollFirst();
  50.             while (!q_max.isEmpty() && max[i][x1][x2] >= max[q_max.peekLast()][x1][x2]) q_max.pollLast();
  51.             q_max.addLast(i);
  52.             //窗口大小为k
  53.             if (i >= k && max[q_max.peekFirst()][x1][x2] - min[q_min.peekFirst()][x1][x2] <= limit) return true;
  54.         }
  55.         return false;
  56.     }
  57. }

试题 G:数组切分

题目：

 

解析：

算法1 回溯算法

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

小技巧
问 : 如何判断区间[i,j]是否可以组成一段连续的自然数？
答 ：只需 区间最大值 - 区间最小值 == j - i (区间长度)即可

  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     static LinkedList<Integer> path =  new LinkedList<>();
  6.     static int res = 0, mod = 1000000007;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  10.         int[] a = new int[n];
  11.         for (int i = 0; i < n; i++) a[i] = sc.nextInt();
  12.         dfs(a, 0);
  13.         System.out.println(res % mod);
  14.     }
  15.  
  16.     private static void dfs(int[] a, int startindex) {
  17.         int n = a.length;
  18.         if (startindex == n) {
  19.             res ++;
  20.             return;
  21.         }
  22.         for (int i = startindex; i < n; i++) {
  23.             if (check(a, startindex, i)) {
  24.                 path.add(i);
  25.                 dfs(a, i + 1);
  26.                 path.removeLast();
  27.             }
  28.         }
  29.     }
  30.  
  31.     private static boolean check(int[] a, int l, int r) {
  32.         int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
  33.         for (int i = l; i <= r; i++) {
  34.             if (a[i] > max) max = a[i];
  35.             if (a[i] < min) min = a[i];
  36.         }
  37.         return max - min == r - l;
  38.     }
  39. }

算法2 DP(正解)

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     static int mod = 1000000007;
  5.     public static void main(String[] args) {
  6.         // f[i]: 以a[i]结尾的切分合法数组的方法数量
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[] a = new int[n + 1];
  10.         for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
  11.         int[] f = new int[n + 1];
  12.         f[0] = 1;
  13.         for (int i = 1; i <= n; i++) {
  14.             int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
  15.             for (int j = i; j > 0; j--) {
  16.                 max = Math.max(max, a[j]);
  17.                 min = Math.min(min, a[j]);
  18.                 //如果a[j, i]是一段连续的自然数，那么就有以a[i]结尾的合法切分合法数量+=以a[j - 1]结尾的合法切分数量
  19.                 //即f[i] += f[j - 1]
  20.                 if (max - min == i - j)
  21.                     f[i] = (f[i] + f[j - 1]) % mod;
  22.             }
  23.         }
  24.         System.out.println(f[n]);
  25.     }
  26. }

试题 H: 回忆迷宫

题目：

解析：

试题 I: 红绿灯

题目：

解析：

试题 J: 拉箱子

题目：

解析：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/455822
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号