> 文档中心 > 2022年第十三届蓝桥杯JAVA B组部分题解

2022年第十三届蓝桥杯JAVA B组部分题解


说明

  第一次参加蓝桥杯,考试白花了四个小时,做题太慢太拉了。
等了一天也没看到有人出题解,那就自己来写。
打算重新再回顾一遍,有自己当时的思路,也有事后诸葛,
还有小编在排版时写的思考过程。
300块是打水漂了

目录

  • 说明
  • 试题 A:星期计算
    • 思路
  • 试题B:山
    • 【问题描述】
    • 思路
    • 结构
    • 代码
  • 试题C:字符统计
    • 思路
    • 代码
  • 试题D:最少刷题数
  • 试题 E: 求阶乘
    • 思路2.0
    • 代码
    • 最最最终版(觉得啰嗦的直接看这里)
    • 代码实现
  • 试题 F: 最大子矩阵
  • 试题 G: 数组切分
    • 思路
  • 试题 H: 回忆迷宫
  • 试题 I: 红绿灯
  • 试题 J: 拉箱子

试题 A:星期计算

【问题描述】
  已知今天是星期六,请问2022天后是星期几?

  注意用数字 1 到 7 表示星期一到星期日。
【答案提交】
  这是一道结果填空的题,你只需要算出结果后提交即可。
  本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

思路

  直接使用电脑自带计算器
在这里插入图片描述
计算出2022除以7余1。
得出结果:星期天
答案:7。

试题B:山

【问题描述】

  这天小明正在学数数。
  他突然发现有些正整数的形状像一座“山”,比如 123565321、145541,它们左右对称(回文)且数位上的数字先单调不减后单调不增。
  小明数了很久也没有数完,他想让你告诉他在区间 [2022, 2022222022] 中有多少个数的形状像一座“山”。

思路

  (1)这道题就不能取巧了,直接暴力就好了。
  (2)关键是回文和先单调不减,后单调不增。

结构

//回文public static boolean huiwen(int x){}//先单调不减,后单调不增,回文之后,只需要判断一半就好了public static boolean dandiao(int x){}

代码

public static void main(String[] args){ int count = 0; for(int i = 2022; i <= 2022222022; i++) {  if(dandiao(i) && huiwen(i) ) {   count++;  } } System.out.println(count);} public static boolean dandiao(int x){  int count = 0;  int m = x;  while(m > 0) {   m /= 10;   count++;  }  m =x;  int t = count>>1;  if(t * 2 == count){   t = t;    //偶数比较前面一半  }else{   t = t+1;  //奇数要到一半,多一个  }  int target = -1;  while(t > 0) {   if(m%10 >= target) {    target = m %10;    m = m/10;    }else {     return false;    }    t--;   }  return true; } public static boolean huiwen(int x){  int count = 0;  int m = x;  int b = 0;  while(m > 0) {   m /= 10;   count++;  }//count记录数位  m = x;  while(count > 0) {   b = b*10+ m%10; //反向输出   count--;   m /= 10;  }  return b==x; }

  数字需要一个个遍历,用时比较长,等一下结果就出来了。
  ans = 3138

试题C:字符统计

【问题描述】
  给定一个只包含大写字母的字符串 S,请你输出其中出现次数最多的字母。
  如果有多个字母均出现了最多次,按字母表顺序依次输出所有这些字母。
【输入格式】
  一个只包含大写字母的字符串 S .
【输出格式】
  若干个大写字母,代表答案。
【样例输入】
  BABBACAC
【样例输出】
   AB
【评测用例规模与约定】
  对于 100% 的评测用例,1 ≤ |S | ≤ 106.

思路

   (1)把字符串转成字符数组,利用哈希表统计每个字母出现的个数
   (2)找出最多的那个(些)并依次输出

代码

import java.util.*;class Main {    public static void main(String []args) { Scanner sc = new Scanner(System.in); String s= sc.next();  char[] s1 = s.toCharArray(); //把字符串转成字符数组 int [] count = new int[26];  //创建一个计数数组 for(int i = 0; i < s1.length; i++) {     count[s1[i] - 'A']++; } int max = 0; for(int i = 0; i< 26; i++) {     if(max < count[i]) {  max = count[i];     //计算最大值     } } int[] f = new int[26]; //找到等于最大值得几个字符,存到F数组里面 int j = 0; for(int i = 0; i< 26; i++) {     f[i] = -1;     if(max == count[i]) {  f[j++] = i;     } } for(int i = 0; i< 26; i++) {     if(f[i] != -1) {  int t = f[i] + 'A';   // 转回ASCII码  System.out.print((char)t);     } }    }}

试题D:最少刷题数

【问题描述】
  小蓝老师教的编程课有 N 名学生,编号依次是 1 . . . N。第 i 号学生这学期
刷题的数量是 Ai。
  对于每一名学生,请你计算他至少还要再刷多少道题,才能使得全班刷题
比他多的学生数不超过刷题比他少的学生数。
【输入格式】
  第一行包含一个正整数 N。
  第二行包含 N 个整数:A1, A2, A3, . . . , AN.
【输出格式】
  输出 N 个整数,依次表示第 1 . . . N 号学生分别至少还要再刷多少道题。
【样例输入】
  5
  12 10 15 20 6
【样例输出】
  0 3 0 0 7
【评测用例规模与约定】
  对于 30% 的数据,1 ≤ N ≤ 1000, 0 ≤ Ai ≤ 1000.
  对于 100% 的数据,1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000.

import java.util.ArrayList;import java.util.Scanner;public class Main {    public static void main(String args[]) { Scanner sc= new Scanner(System.in); int num = sc.nextInt(); ArrayList<Integer> arr1 = new ArrayList<>(); //用来排序 ArrayList<Integer> arr2 = new ArrayList<>(); //用来保持 for(int i = 0; i < num; i++){     int m = sc.nextInt();     arr1.add(m);     arr2.add(m); }//排序以前 System.out.println(arr1.toString()+arr2.toString()); //冒泡排序 for (int i = 0; i < num; i++) {     for (int j = i+1; j < num ; j++) {  int a= arr1.get(i);  int b = arr1.get(j);  if(a > b){      int t = a;      arr1.set(i,b);      arr1.set(j,a);  }     } }     // 排序之后  System.out.println(arr1.toString()+arr2.toString()); int mid = arr1.get(num/2); for (int i = 0; i < num; i++) {     if(arr2.get(i) < mid){  arr2.set(i ,mid - arr2.get(i) + 1);     }else{  arr2.set(i ,0);     } } System.out.println(arr2.toString());    }}

 这题考试没做出来,对ArrayList不熟悉,想着在数组里面改,但是数组传递的是地址。后面看别人的想法。自己也就做出来了。

试题 E: 求阶乘

【问题描述】
  满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?
  如果这样的 N 不存在输出 −1。
【输入格式】
  一个整数 K。
【输出格式】
  一个整数代表答案。
【样例输入】
2
【样例输出】
10
【评测用例规模与约定】
  对于 30% 的数据,1 ≤ K ≤ 106.
思路
  (1)这题有点像18年省赛填空题 尾积为零.
  (2)是计算一群数据的成绩末尾有几个零,想要得到0,要么是2*5 = 10; 要么是尾部本来就有0;
  (3)如果一个数可以分离出来 2 5 10 那么这个数就对尾部的0 有贡献。为了方便计算。先算0,再算5,再算2。
      因为 0, 5 , 2 出现的次数是依次减少的.木桶能装多少水取决于最短的那块板。
代码

import java.util.Scanner;public class jiecheng {    public static void main(String[] args) { Scanner sc = new Scanner(System.in); long k = sc.nextLong(); long count0 = 0; long count2  = 0; long count5 = 0; for(long i = 1; i < 10e18; i++){     long m = i; //     while(m % 10  == 0 && i != 0) {  count0 += 1;  m /= 10;     }     while(m % 5 == 0 && i != 0){  count5 += 1;  m /= 5;     }     while(m % 2 == 0 && i != 0){  //其实可以不算2,因为2 的数量永远远远大于5  count2 += 1;  m /= 2;     }     if(count0 + Math.min(count2,count5) == k){  System.out.println(i);  break;     } }    }}

思路2.0

  1.0非常暴力。1018 很明显会超时。好吧,之前写的只能过30%的测试用例。

  那么有什么办法可以优化一下代码呢。

  因为上面说了,2的数量是永远远远大于5的。那么没到一个结尾为5的数字的时候就是尾部零加一的时候。

  看下面规律
请添加图片描述
看到的是:每加到5的倍数就会加一个零甚至更多。
最开始想到的是动态规划:

设计状态:dp[i] 表示数据为 i i i 的时候,尾部 0 0 0 的数量
转移方程:dp[i] = dp[i-5] + 1 + log5 i i i - log5 (i i i-5);

初始状态:dp[5] = 1;

可行是可行但是,创建的数组太大。很明显不符合要求。
那么我们可以用一种简单的方法表示出来:

最终版:

一个公式:f[n] = n /5 + log5n - 1;

代码

public class jiecheng {    public static void main(String[] args) { Scanner sc = new Scanner(System.in); long K = sc.nextLong(); for(long i = 5* K + 5; i> 0; i = i - 5){     if(i / 5 + log(5,i) - 1 == K){  System.out.println(i);     } }    }    public static int log(int a, long b){ return (int) (Math.log(b)/Math.log(a));    }}

!!!
调了几个测试用例计算结果非常快!!速度60迈。
**2022年第十三届蓝桥杯JAVA B组部分题解
**
随便输入一个比较大的数,但是用方法一出来的结果不一样
OHHHH!!!错辣!!!
后来发现当我输入几个比较小的数的时候,答案都没问题,一旦超过50,就变坏了。

emmm
对了,50,75 里面也有一个25.讲道理也要加一个零。
这这这,,重来吧

最最最终版(觉得啰嗦的直接看这里)

  (1)这题有点像18年省赛填空题 尾积为零.
  (2)是计算一群数据的成绩末尾有几个零,想要得到0,要么是2*5 = 10; 要么是尾部本来就有0;
  (3)如果一个数可以分离出来 2 5 10 那么这个数就对尾部的0 有贡献。为了方便计算。先算0,再算5,再算2。
      因为 0, 5 , 2 出现的次数是依次减少的.木桶能装多少水取决于最短的那块板。
   (4)0也相当于是5 * 2,因此只需要计算5出现的次数就好了
请添加图片描述

我们知道了,有一个五就加一,有一个25就加2,有一个125就加3.。。。。。。
请添加图片描述
  等比数列求和公式

K = 1/4M(1 - (1/5)^n);

代码实现

   import java.util.Scanner;      public class jiecheng {    static boolean judge(long k, long M, int n) { long m = 5; while (n >= 1) {    k -= (M / m);    --n;    m *= 5;  }  return k == 0;     }     static double[] nums = new double[30];     public static void main(String[] args) {  Scanner cin = new Scanner(System.in);  long k = cin.nextLong();  for (int i = 1; i < 30; ++i) {      nums[i] = (4 * k) / (1 - Math.pow(0.2, i * 1.0));  }  for (int i = 1; i < 30; ++i) {      double cur = Math.pow(5, i);      double tCur = Math.pow(5, i + 1);      if (nums[i] >= cur && nums[i]*1.0 < tCur) {   long lI = (long) (nums[i]);   int mod = (int) (lI % 5);   if (lI != nums[i]) {lI += 5;   }   lI -= mod;   if (judge(k, lI, i)) {System.out.println(lI);return;   }      }  }  System.out.println(-1);     } }

  这里有两个未知数n,m;难受~
  能力有限,思路和大佬差不多,这里引用下大佬的代码(狗头保命)
这个题目考完试了又摸了4个小时,最后代码写不来也是坠了

@秋刀鱼与猫_
.

试题 F: 最大子矩阵

【问题描述】
  小明有一个大小为 N × M 的矩阵,可以理解为一个 N 行 M 列的二维数组。
我们定义一个矩阵 m 的稳定度 f(m) 为 f(m) = max(m) − min(m),其中 max(m)
表示矩阵 m 中的最大值,min(m) 表示矩阵 m 中的最小值。现在小明想要从这
个矩阵中找到一个稳定度不大于 limit 的子矩阵,同时他还希望这个子矩阵的面
积越大越好(面积可以理解为矩阵中元素个数)。
  子矩阵定义如下:从原矩阵中选择一组连续的行和一组连续的列,这些行
列交点上的元素组成的矩阵即为一个子矩阵。
【输入格式】
  第一行输入两个整数 N,M,表示矩阵的大小。
  接下来 N 行,每行输入 M 个整数,表示这个矩阵。
  最后一行输入一个整数 limit,表示限制。
【输出格式】
  输出一个整数,分别表示小明选择的子矩阵的最大面积。
【样例输入】
  3 4
  2 0 7 9
  0 6 9 7
  8 4 6 4
  8
【样例输出】
  6
【样例说明】
  满足稳定度不大于 8 的且面积最大的子矩阵总共有三个,他们的面积都是
  6(粗体表示子矩阵元素):
  2 0 7 9
  0 6 9 7
  8 4 6 4

  2 0 7 9
  0 6 9 7
  8 4 6 4

  2 0 7 9
  0 6 9 7
  8 4 6 4
【评测用例规模与约定】

评测用例编号 N M
1 、2 1 ≤ N ≤ 10 1 ≤ M ≤ 10
3、4 N = 1 M ≤ 100000
5~12 1 ≤ N ≤ 10 M ≤ 10000
13 ∼ 20 1 ≤ N ≤ 80 1 ≤ M ≤ 80

对于所有评测用例,0 ≤ 矩阵元素值, limit ≤ 105。

这个题目看的就头痛。下一个

试题 G: 数组切分

【问题描述】
  已知一个长度为 N N N的数组: A 1 A1 A1, A 2 A2 A2, A 3 A3 A3, … A N AN AN 恰好是 1 ∼ N N N 的一个排列。
  现在要求你将 A A A 数组切分成若干个 (最少一个,最多 N N N 个) 连续的子数组
  并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
  例如:
    对于 A A A= {1, 3, 2, 4}, 一共有 5 种切分方法:
  {1}{3}{2}{4}:每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
  {1}{3, 2}{4}:{3, 2} 包含 2 到 3,是 一段连续的自然数,另外 {1} 和 {4} 显然也是。
  {1}{3, 2, 4}:{3, 2, 4} 包含 2 到 4,是 一段连续的自然数,另外 {1} 显然也是。
  {1, 3, 2}{4}:{1, 3, 2} 包含 1 到 3,是 一段连续的自然数,另外 {4} 显然也是。
  {1, 3, 2, 4}:只有一个子数组,包含 1 到 4,是 一段连续的自然数。
【输入格式】
  第一行包含一个整数 N N N。第二行包含 N N N 个整数,代表 A A A 数组。
【输出格式】
  输出一个整数表示答案。由于答案可能很大,所以输出其对 1000000007 取
模后的值
【样例输入】
  4
  1 3 2 4
【样例输出】
  5

【评测用例规模与约定】
  对于 30% 评测用例,1 ≤ N ≤ 20.
  对于 100% 评测用例,1 ≤ N ≤ 10000.

思路

  以我 “多年” 的刷题经验来看,应该是动态规划,但是考试就没时间看了。
  当时犯了一个致命的错误,就是前面一道题目卡住了就直接从后往前看题目
  蓝桥杯的题目难度一般来说是逐渐上升的,所以一定要从头到尾做下来,
  前面的做不来,后面的大概率做不完整。

经过一段时间的思考,我觉得还是得等我去LeetCode历练一下,再回来做这些题目。

试题 H: 回忆迷宫

【问题描述】
爱丽丝刚从一处地下迷宫中探险归来,你能根据她对于自己行动路径的回
忆,帮她画出迷宫地图吗?
迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步
骤,每个移动步骤可能是上下左右四个方向中的一种,表示爱丽丝往这个方向
走了一格。你需要根据这些移动步骤给出一个迷宫地图,并满足以下条件:
1、爱丽丝能在迷宫内的某个空地开始,顺利的走完她回忆的所有移动步
骤。
2、迷宫内不存在爱丽丝没有走过的空地。
3、迷宫是封闭的,即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处
视为迷宫外,所有不与迷宫外联通的空地都视为是迷宫内。(迷宫地图为四联
通,即只有上下左右视为联通)
4、在满足前面三点的前提下,迷宫的墙的数量要尽可能少。
【输入格式】
第一行一个正整数 N,表示爱丽丝回忆的步骤数量。
接下来一行 N 个英文字符,仅包含 UDLR 四种字符,分别表示上(Up)、
下(Down)、左(Left)、右(Right)。
【输出格式】
请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行,用字符 ‘
表示墙,用 ‘ ’(空格)表示非墙。
你的输出需要保证以下条件:
1、至少有一行第一个字符为 ‘
’。 2、第一行至少有一个字符为 ‘’。
3、每一行的最后一个字符为 ‘
’。 4、最后一行至少有一个字符为 ‘*’。
【样例输入】
17
UUUULLLLDDDDRRRRU
【样例输出】






【样例说明】
爱丽丝可以把第六行第六个字符作为起点。
外墙墙墙墙墙外
墙内内内内内墙
墙内墙墙墙内墙
墙内墙墙墙内墙
墙内墙墙墙内墙
墙内内内内内墙
外墙墙墙墙墙外
【评测用例规模与约定】
对于所有数据,0 < N ≤ 100.

试题 I: 红绿灯

【问题描述】
爱丽丝要开车去上班,上班的路上有许多红绿灯,这让爱丽丝很难过。为
了上班不迟到,她给自己的车安装了氮气喷射装置。现在她想知道自己上班最
短需要多少时间。
爱丽丝的车最高速度是 1V 米每秒,并且经过改装后,可以瞬间加速到小于
等于最高速的任意速度,也可以瞬间停止。
爱丽丝家离公司有 N 米远,路上有 M 个红绿灯,第 i 个红绿灯位于离爱
丽丝家 Ai 米远的位置,绿灯持续 Bi 秒,红灯持续 Ci 秒。在初始时(爱丽丝开
始计时的瞬间),所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红的
瞬间到达红绿灯,她会停下车等红灯,因为她是遵纪守法的好市民。
氮气喷射装置可以让爱丽丝的车瞬间加速到超光速(且不受相对论效应的
影响!),达到瞬移的效果,但是爱丽丝是遵纪守法的好市民,在每个红绿灯前
她都会停下氮气喷射,即使是绿灯,因为红绿灯处有斑马线,而使用氮气喷射
装置通过斑马线是违法的。此外,氮气喷射装置不能连续启动,需要一定时间
的冷却,表现为通过 K 个红绿灯后才能再次使用。(也就是说,如果 K = 1,就
能一直使用啦!)初始时,氮气喷射装置处于可用状态。
【输入格式】
第一行四个正整数 N、M、K、V,含义如题面所述。
接下来 M 行,每行三个正整数 Ai、Bi、Ci,含义如题面所述。
【输出格式】
输出一个正整数 T,表示爱丽丝到达公司最短需要多少秒。
【样例输入】
90 2 2 2
30 20 20
60 20 20
【样例输出】
80
【样例说明】
爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯,然后绿灯
通过,以最高速行进 60 秒后到达第二个红绿灯,此时绿灯刚好变红,于是她等
待 20 秒再次变为绿灯后通过该红绿灯,此时氮气喷射装置冷却完毕,爱丽丝再
次使用瞬间到达公司,总共用时 80 秒。
【评测用例规模与约定】
对于 30% 的数据,N ≤ 100; M ≤ 10; M < K; V = 1.
对于 60% 的数据,N ≤ 1000; M ≤ 100; K ≤ 50; Bi,Ci ≤ 100; V ≤ 10.
对于 100% 的数据,0 < N ≤ 108; M ≤ 1000; K ≤ 1000; 0 < Bi,Ci ≤ 106
; 0 < V ≤ 106
; 0 < Ai < N; 对任意 i < j, 有 Ai < Aj.

试题 J: 拉箱子

【问题描述】
推箱子是一款经典电子游戏,爱丽丝很喜欢玩,但是她有点玩腻了,现在
她想设计一款拉箱子游戏。
拉箱子游戏需要玩家在一个 N × M 的网格地图中,控制小人上下左右移动,
将箱子拉到终点以获得胜利。
现在爱丽丝想知道,在给定地形(即所有墙的位置)的情况下,有多少种
不同的可解的初始局面。
【初始局面】 的定义如下:
1、初始局面由排列成 N × M 矩形网格状的各种元素组成,每个网格中有
且只有一种元素。可能的元素有:空地、墙、小人、箱子、终点。
2、初始局面中有且只有一个小人。
3、初始局面中有且只有一个箱子。
4、初始局面中有且只有一个终点。
【可解】 的定义如下:
通过有限次数的移动小人(可以在移动的同时拉箱子),箱子能够到达终点
所在的网格。
【移动】 的定义如下:
在一次移动中,小人可以移动到相邻(上、下、左、右四种选项)的一个
网格中,前提是满足以下条件:
1、小人永远不能移动到 N × M 的网格外部。
2、小人永远不能移动到墙上或是箱子上。
3、小人可以移动到空地或是终点上。
【拉箱子】 的定义如下:
在一次合法移动的同时,如果小人初始所在网格沿小人移动方向的反方向
上的相邻网格上恰好是箱子,小人可以拉动箱子一起移动,让箱子移动到小人
初始所在网格。
即使满足条件,小人也可以只移动而不拉箱子。
【输入格式】
第一行两个正整数 N 和 M,表示网格的大小。
接下来 N 行,每行 M 个由空格隔开的整数 0 或 1 描述给定的地形。其中
1 表示墙,0 表示未知的元素,未知元素可能是小人或箱子或空地或终点,但不
能是墙。
【输出格式】
输出一个正整数,表示可解的初始局面数量。
【样例输入】
2 4
0 0 0 0
1 1 1 0
【样例输出】
13
【样例说明】
13 种可解的初始局面示意图如下:
人终箱空
墙墙墙空


人终空箱
墙墙墙空


人空终箱
墙墙墙空


箱人终空
墙墙墙空


空人终箱
墙墙墙空


箱终人空
墙墙墙空


空终人箱
墙墙墙空


箱终空人
墙墙墙空


箱空终人
墙墙墙空


空箱终人
墙墙墙空


箱终空空
墙墙墙人


箱空终空
墙墙墙人


空箱终空
墙墙墙人
【评测用例规模与约定】
对于 30% 的数据,N, M ≤ 3.
对于 100% 的数据,0 < N, M ≤ 10.