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：字符统计 【2022年第十三届蓝桥杯JAVA B组部分题解】【问题描述】
??给定一个只包含大写字母的字符串 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 arr1 = new ArrayList<>(); //用来排序 ArrayList 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 + log5i 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迈。
**

文章图片

**
随便输入一个比较大的数，但是用方法一出来的结果不一样
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.