2022年第十三届蓝桥杯大赛软件类省赛JavaB组试题即答案解析（备战蓝桥杯）

爱踢球的程序员

已于 2024-03-27 16:59:17 修改

阅读量3.9k

点赞数 13

分类专栏：蓝桥杯大赛文章标签：蓝桥杯 java 算法

于 2023-03-04 13:21:51 首次发布

本文链接：https://blog.csdn.net/TerryProgrammer/article/details/129320376

版权

蓝桥杯大赛专栏收录该内容

1 篇文章

订阅专栏

蓝桥杯2022年javab组省赛真题，备战2023年蓝桥杯大赛

试题A：星期计数

本题总分：5 分

【问题描述】

已知今天是星期六，请问 2022 天后是星期几？

注意用数字 1 到 7 表示星期一到星期日。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

7

第一题往往都是送分题，直接乘以20循环22次，为了不超过数据范围，可以用大数BigInteger，也可以每次对7取模，这题刚好为7，如果结果大于7则需要再取一次模


public class A {
    public static void main(String[] args) {
        int ans=6,a=1;
        for (int i = 0; i < 22; i++) {
            a=(a*20)%7;
        }
        System.out.println(ans+a);
    }
}

试题 B: 山

本题总分：5 分

【问题描述】

这天小明正在学数数。

他突然发现有些正整数的形状像一座“山”，比如 123565321、145541，它们左右对称（回文）且数位上的数字先单调不减，后单调不增。

小明数了很久也没有数完，他想让你告诉他在区间 [2022, 2022222022] 中有多少个数的形状像一座“山”。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

3138

由于是填空题，时间限制并没有那么严格，我们可以直接枚举，然后先做下一题等待结果

先判断是否是回文数字，如果是回文数字再判断前半段（偶数位数刚好是前半段，奇数位数需要多判断一位）数字是否是单调不减的数，如果满足条件的话后半段一定是单调不增的（回文）


public class B {
    public static void main(String[] args) {
        int res=0;
        for (int i = 2022; i <=2022222022 ; i++) {
            if (check(i)) res++;
        }
        System.out.println(res);
    }
    public static boolean check(int x){
        String s=String.valueOf(x);
        String re= String.valueOf(new StringBuilder(s).reverse());
        if (!s.equals(re)) return false;
        int len = (s.length() + 1) / 2;
        char[] c = s.toCharArray();
        for (int i = 1; i <len ; i++) {
            if (c[i]<c[i-1])return false;
        }
        return true;
    }
}

试题 C: 字符统计

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

给定一个只包含大写字母的字符串 S，请你输出其中出现次数最多的字母。

如果有多个字母均出现了最多次，按字母表顺序依次输出所有这些字母。

【输入格式】

一个只包含大写字母的字符串 S .

【输出格式】

若干个大写字母，代表答案。

【样例输入】

BABBACAC

【样例输出】

AB

【评测用例规模与约定】

对于 100% 的评测用例，1 ≤ |S | ≤ 106.

可以把[A-Z]的字母存在一个长度为26的数组中，扫描一遍字符串，出现哪个字符就在对应位置累加，并记录下出现最多次的次数，遍历数组将出现最多次的字母输出


import java.util.Scanner;

public class C {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        char[] c = sc.nextLine().toCharArray();
        int[] arr=new int[26];
        int max=0;
        for (int i = 0; i < c.length; i++) {
            arr[c[i]-'A']++;
            max=Math.max(arr[c[i]-'A'],max);
        }
        for (int i = 0; i < 26; i++) {
            if (arr[i]==max) System.out.print((char)('A'+i));
        }
    }
}

试题 D: 最少刷题数

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

小蓝老师教的编程课有 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.

这题有两种做法。

第一种是取中位数，然后分类讨论，需要考虑人数的奇偶性、与中位数相等的数前半段和后半段的大小对比，情况很多容易写错

第二种做法就是二分答案，先开一个两倍大（20w，Ai可能为10w，二分最大值也可能为10w）的数组cnt，cnti用于存放小于等于i的数的个数，然后遍历每个人的刷题数，如果小于当前同学刷题数的人数超过大于当前同学刷题数的人数则输出0，否则进行二分查找。

同时这题输入的数据量较多，需要写个快读，否则容易超时


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class D {
    private static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static int nextInt(){
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }
    public static void main(String[] args) {
        int n=nextInt(),N= 100010;
        int[] arr=new int[n+1];
        int[] cnt=new int[2*N];
        for (int i = 1; i <= n; i++) {
            arr[i]=nextInt();
            cnt[arr[i]]++;
        }
        for (int i = 1; i <2* N ; i++) cnt[i]+=cnt[i-1];
        for (int i = 1; i <= n; i++) {
            if (cnt[100000]-cnt[arr[i]]<=cnt[Math.max(0,arr[i]-1)]){
                System.out.print(0+" ");
                continue;
            }
            int l=1,r=100000;
            while (l<r){
                int mid=l+r>>1;
                if (cnt[100000]-cnt[arr[i]+mid]<=cnt[arr[i]-1+mid]-1) r=mid;
                else l=mid+1;
            }
            System.out.print(l+" ");
        }
    }
}

试题 E: 求阶乘

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?

如果这样的 N 不存在输出 −1。

【输入格式】

一个整数 K。

【输出格式】

一个整数代表答案。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 30% 的数据，1 ≤ K ≤ 106.

对于 100% 的数据，1 ≤ K ≤ 1018.

数据范围很大，如果直接暴力的话肯定会超时。

首先应该要清楚末尾为0显然是2*5才能构成一个0，即求得数中含有多少个5就含有多少个0

当数字太小时，含5的个数少于k，当数字太大时，含5的个数大于k，即具有单调性质，可以采用二分答案的方法快速找到答案，那么二分的上限值为多少呢？有k个0就要包含k个5，即上限值为5*k

最后怎么快速判断阶乘中含有多少个5？可以对除以5的n次幂的结果进行累加即可。

直接上代码


import java.util.Scanner;

public class E {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long k=sc.nextLong(),l=5,r=k*5,mid,cnt;
        while (l<=r){
            mid=l+r>>1;
            cnt=0;
            for (long i = 5; i <=mid ; i*=5) cnt+=mid/i;
            if (cnt==k){
                System.out.println(mid-mid%5);
                return;
            }
            if (cnt<k) l=mid+1;
            else r=mid-1;
        }
        System.out.println(-1);
    }
}

试题 F: 最大子矩阵

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

小明有一个大小为 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，表示限制。

【输出格式】

输出一个整数，分别表示小明选择的子矩阵的最大面积。

【样例输入】

【样例输出】

【样例说明】

满足稳定度不大于 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

这题的关键是如何把时间复杂度降低

观察数据范围，n的范围比m小得多，因此n2是完全可以接受的，可以维护两个三维数组

max[i][j][k]、min[i][j][k]，分别记录的是第k列[i-j]行的最大值和最小值时间复杂度为O(n2m)。

然后再来分析，当i和j固定时，k增大当前矩阵的最大值和最小值的差只可能保持不变或者跟着增大，k减小当前矩阵的最大值和最小值的差只可能保持不变或者跟着减小，可见具有单调性，可以对k进行二分，找到满足条件的k最大值。

矩阵确定后，如何快速找出该矩阵的最大最小值从而判断是否满足<=limit的条件？此时可以用双端队列进行维护，枚举k列的最大最小值，始终保持最大值队列的队头为当前最大值，最小值队列的队头为当前最小值,即可在线性时间内确定是否满足条件。

这样下来时间复杂度控制在O(n2mlog2m)


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;

public class F {
    static int n,m,limit;
    static int[][][] max,min;
    static final StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static int nextInt(){
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }
    public static void main(String[] args) {
        n=nextInt();
        m=nextInt();
        int[][] arr=new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j]=nextInt();
            }
        }
        limit=nextInt();
        max=new int[n+1][n+1][m+1];
        min=new int[n+1][n+1][m+1];
        for (int k = 1; k <= m; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = i; j <= n; j++) {
                    if (i==j){
                        max[i][j][k]=arr[i][k];
                        min[i][j][k]=arr[i][k];
                        continue;
                    }
                    max[i][j][k]=Math.max(max[i][j-1][k],arr[j][k]);
                    min[i][j][k]=Math.min(min[i][j-1][k],arr[j][k]);
                }
            }
        }
        int ans=0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int l=1,r=m,res=0;
                while (l<r){
                    int mid=l+r+1>>1;
                    if (check(i,j,mid)) {
                        l=mid;
                        res=Math.max(res,(j-i+1)*mid);
                    }
                    else r=mid-1;
                }
                ans=Math.max(ans,res);
            }
        }
        System.out.println(ans);
    }

    public static boolean check(int x1, int x2, int k) {
        Deque<Integer> maxq =new ArrayDeque<>();
        Deque<Integer> minq =new ArrayDeque<>();
        for (int i = 1; i <= m; i++) {
            if (!maxq.isEmpty()&&maxq.peekFirst()<i-k+1) maxq.pollFirst();
            while (!maxq.isEmpty()&&max[x1][x2][maxq.peekLast()]<max[x1][x2][i]) maxq.pollLast();
            maxq.offerLast(i);
            if (!minq.isEmpty()&&minq.peekFirst()<i-k+1) minq.pollFirst();
            while (!minq.isEmpty()&&min[x1][x2][minq.peekLast()]>min[x1][x2][i]) minq.pollLast();
            minq.offerLast(i);
            if (i>=k&&max[x1][x2][maxq.peekFirst()]-min[x1][x2][minq.peekFirst()]<=limit) return true;
        }
        return false;
    }
}

试题 G: 数组切分

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

已知一个长度为 N 的数组：A1, A2, A3, ...AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且

每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如对于 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 个整数，代表 A 数组。

【输出格式】

输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值

4
1 3 2 4

【样例输出】

【评测用例规模与约定】

对于 30% 评测用例，1 ≤ N ≤ 20.

对于 100% 评测用例，1 ≤ N ≤ 10000.

很明显的动态规划题，当然想不出来可以暴力求解大概能过一半的数据。

当子数组的最大值和最小值之差恰好等于子数组个数+1的情况下，子数组便是一段连续的自然数组。

维护一个f[i]数组，i表示以第i个数字作为结尾的方案数。

构造状态转移方程，可以从最后一步出发，当第[i-n]个数组成一个连续自然数组时，状态转移方程便是f[n]+=f[i-1];根据状态转移方程，我们就可以先正序遍历数组，然后倒序寻找可以当前枚举到的数字作为结尾的连续自然数组。


import java.util.Scanner;

public class G {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),mod= (int) (1e9+7);
        int[] arr=new int[n+1],f=new int[n+1];
        for (int i = 1; i <= n; i++) arr[i]=sc.nextInt();
        f[0]=1;
        for (int i = 1; i <=n ; i++) {
            int max=arr[i],min=arr[i];
            for (int j = i; j > 0 ; j--) {
                max=Math.max(max,arr[j]);
                min=Math.min(min,arr[j]);
                if (max-min==i-j) f[i]=(f[i]+f[j-1])%mod;
            }
        }
        System.out.println(f[n]);
    }
}

试题 H: 回忆迷宫

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

爱丽丝刚从一处地下迷宫中探险归来，你能根据她对于自己行动路径的回忆，帮她画出迷宫地图吗？

迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步骤，每个移动步骤可能是上下左右四个方向中的一种，表示爱丽丝往这个方向走了一格。你需要根据这些移动步骤给出一个迷宫地图，并满足以下条件：

1、爱丽丝能在迷宫内的某个空地开始，顺利的走完她回忆的所有移动步骤。

2、迷宫内不存在爱丽丝没有走过的空地。

3、迷宫是封闭的，即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处视为迷宫外，所有不与迷宫外联通的空地都视为是迷宫内。（迷宫地图为四联通，即只有上下左右视为联通）

4、在满足前面三点的前提下，迷宫的墙的数量要尽可能少。

【输入格式】

第一行一个正整数 N，表示爱丽丝回忆的步骤数量。

接下来一行 N 个英文字符，仅包含 UDLR 四种字符，分别表示上（Up）、下（Down）、左（Left）、右（Right）。

【输出格式】

请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行，用字符 ‘*’表示墙，用 ‘ ’（空格）表示非墙。

你的输出需要保证以下条件：

1、至少有一行第一个字符为 ‘*’。

2、第一行至少有一个字符为 ‘*’。

3、每一行的最后一个字符为 ‘*’。

4、最后一行至少有一个字符为 ‘*’。

【样例输入】

17
UUUULLLLDDDDRRRRU

【样例输出】

【样例说明】

爱丽丝可以把第六行第六个字符作为起点。

外墙墙墙墙墙外

墙内内内内内墙

墙内墙墙墙内墙

墙内内内内内墙

外墙墙墙墙墙外

【评测用例规模与约定】

对于所有数据，0 < N ≤ 100.

模拟题，首先需要开个大点的图全部用‘.’标记，然后从居中的点出发，用‘ ’标记走过的路线，然后再遍历一遍路线，将路线上下左右非标记的点标记成墙‘*’，这时围墙就就搭建起来了。

问题是迷宫中间可能还有成块的城墙，由于迷宫是封闭的，我们可以把围墙外的先用‘ ’标记，然后剩余的‘.’便是迷宫内的墙，标记成‘*’。

最后注意题目输出的要求即可


import java.util.*;

public class H {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),N=400;
        sc.nextLine();
        char[] c = sc.nextLine().toCharArray();
        char[][] map= new char[N][N];
        for (int i = 0; i < N; i++) Arrays.fill(map[i],'.');
        Map<Character,int[]> dir=new HashMap<>();
        dir.put('U',new int[]{-1,0});
        dir.put('D',new int[]{1,0});
        dir.put('L',new int[]{0,-1});
        dir.put('R',new int[]{0,1});
        int x=200,y=200,x1=x,x2=x,y1=y,y2=y;
        map[x][y]=' ';
        for (int i = 0; i < n; i++) {
            int[] arr = dir.get(c[i]);
            x+=arr[0];
            y+=arr[1];
            x1=Math.min(x,x1);
            x2=Math.max(x,x2);
            y1=Math.min(y,y1);
            y2=Math.max(y,y2);
            map[x][y]=' ';
        }
        Queue<int[]> q=new LinkedList<>();
        int[][] d=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        int[][] vis=new int[N][N];
        q.offer(new int[]{200,200});
        vis[200][200]=1;
        while (!q.isEmpty()){
            int[] head = q.poll();
            for (int i = 0; i < 4; i++) {
                int a=head[0]+d[i][0];
                int b=head[1]+d[i][1];
                if (map[a][b]=='.') map[a][b]='*';
                if (vis[a][b]==0&&map[a][b]==' '){
                    vis[a][b]=1;
                    q.offer(new int[]{a,b});
                }
            }
        }
        q=new LinkedList<>();
        vis=new int[N][N];
        vis[0][0]=1;
        q.offer(new int[]{0,0});
        while (!q.isEmpty()){
            int[] head = q.poll();
            for (int i = 0; i < 4; i++) {
                int a=head[0]+d[i][0];
                int b=head[1]+d[i][1];
                if (a>=0&&a<N&&b>=0&&b<N&&vis[a][b]!=1&&map[a][b]!='*'){
                    vis[a][b]=1;
                    map[a][b]=' ';
                    q.offer(new int[]{a,b});
                }
            }
        }
        for (int i = x1-1; i <= x2+1 ; i++) {
            String s="";
            for (int j = y1-1; j <= y2+1 ; j++) {
                if (map[i][j]=='.') s+='*';
                else s+=map[i][j];
            }
            while (s.charAt(s.length()-1)==' '){
                s=s.substring(0,s.length()-1);
            }
            if (i!=x2+1)System.out.println(s);
            else System.out.print(s);
        }
    }
}

试题 I: 红绿灯

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

爱丽丝要开车去上班，上班的路上有许多红绿灯，这让爱丽丝很难过。为了上班不迟到，她给自己的车安装了氮气喷射装置。现在她想知道自己上班最短需要多少时间。

爱丽丝的车最高速度是 1/v米每秒，并且经过改装后，可以瞬间加速到小于等于最高速的任意速度，也可以瞬间停止。

爱丽丝家离公司有 N 米远，路上有 M 个红绿灯，第 i 个红绿灯位于离爱丽丝家 Ai 米远的位置，绿灯持续 Bi 秒，红灯持续 Ci 秒。在初始时（爱丽丝开始计时的瞬间），所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红的瞬间到达红绿灯，她会停下车等红灯，因为她是遵纪守法的好市民。氮气喷射装置可以让爱丽丝的车瞬间加速到超光速（且不受相对论效应的影响！），达到瞬移的效果，但是爱丽丝是遵纪守法的好市民，在每个红绿灯前她都会停下氮气喷射，即使是绿灯，因为红绿灯处有斑马线，而使用氮气喷射装置通过斑马线是违法的。此外，氮气喷射装置不能连续启动，需要一定时间的冷却，表现为通过 K 个红绿灯后才能再次使用。（也就是说，如果 K = 1，就能一直使用啦！）初始时，氮气喷射装置处于可用状态。

【输入格式】

第一行四个正整数 N、M、K、V，含义如题面所述。

接下来 M 行，每行三个正整数 Ai、Bi、Ci，含义如题面所述。

【输出格式】

输出一个正整数 T，表示爱丽丝到达公司最短需要多少秒。

【样例输入】