第十三届蓝桥杯复盘

参加了第十三届蓝桥杯JavaB组省赛，感觉还是很多题粗心错了。。坑坑挺多的。今年只有两道填空题，难度也稍微上来了。

试题A:星期计算

问题描述：

已知今天是星期六，请问 2022 天后是星期几？
注意用数字 1 到 7 表示星期一到星期日。

思路：直接求出值然后对7取余加1即可

import java.math.BigInteger;

public class Solution {

    public static void main(String[] args) {
        BigInteger n = new BigInteger("20");
        for (int i = 1; i <= 22; i++) {
            n = n.multiply(new BigInteger("20"));
        }
        System.out.println(n.remainder(new BigInteger("7")).add(new BigInteger("1")));
    }
}

输出: 7

试题B:山

问题描述：

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

这道题做的时候非常的粗心，抓住条件先单调不减，后单调不增,忽略了连续相等的数

思路：利用先单调不减，后单调不增这个条件进行判断，如果某数位的值大于相邻数位的值则不符合单调不减的条件，后面则相同

public class Solution {

    public static void main(String[] args) {
        int count = 0;
        for (int i = 2022; i <= 2022222022; i++) {
            if (check(i)) {
                count++;
            }
        }
        System.out.println(count);
    }

    private static boolean check(int i) {
        char[] chars = String.valueOf(i).toCharArray();
        for (int k = 0; k < chars.length / 2; k++) {
            if (chars[k] > chars[k + 1]) {
                return false;
            }
            if (chars[k] != chars[chars.length - 1 - k]) {
                return false;
            }
        }
        return true;
    }
}

输出: 3138

试题C:字符统计

问题描述:

给定一个只包含大写字母的字符串 S，请你输出其中出现次数最多的字母。
如果有多个字母均出现了最多次，按字母表顺序依次输出所有这些字母。

输入格式：一个只包含大写字母的字符串S

样例输入：BABBACAC

样例输出：AB

思路：这道题一开始是想用map去统计然后遍历求出最大值在比对字典序，写到一半发现根本不用这么麻烦，既然是字典序，那就直接new一个数组去存字符的ASCII码，根据题目全大写字母，已知A的ASCII是65, 将字母的ASCII减去A存入数组然后遍历最大值即可。

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] alphabet = new int[26];
        for (int i = 0; i < str.length(); i++) {
            alphabet[str.charAt(i) - 65]++;
        }
        int max = 0;
        for (int frequency : alphabet) {
            if (frequency > max) {
                max = frequency;
            }
        }
        for (int i = 0; i < alphabet.length; i++) {
            if (alphabet[i] == max) {
                System.out.print((char) (i + 65));
            }
        }
    }
}

试题D:最少刷题数

问题描述：

小蓝老师教的编程课有 N 名学生，编号依次是 1 . . . N。第 i 号学生这学期
刷题的数量是 Ai。
对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题
比他多的学生数不超过刷题比他少的学生数。

样例输入：

1 2	5 12 10 15 20 6

样例输出：0 3 0 0 7

思路：

这里要利用中位数，条件是比他多的学生数 <= 比他少的学生数，那么我们可以利用中位数，求每个数离中位数差多少位，设中位数为midVal，比midVal大的数自然符合条件，如果比midVal小的数则需要刷到midVal + 1，但这里还要考虑一个奇偶的问题，以midVal为标准，统计两边的刷题数目leftNum和rightNum

1.奇数情况

leftNum >= rightNum且刷题数等于midVal，则不需要刷题

1.偶数情况

偶数只需要刷到和中位数相等即可

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] copyArr = Arrays.copyOfRange(arr, 0, arr.length);
        Arrays.sort(copyArr);
        int midVal = copyArr[copyArr.length / 2];
        int leftNum = 0;
        int rightNum = 0;
        // 统计中间值两边的权重
        for (int i = 0; i < n; i++) {
            if (copyArr[i] < midVal) {
                leftNum++;
                continue;
            }
            if (copyArr[i] > midVal) {
                rightNum++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (arr[i] > midVal || (leftNum >= rightNum && arr[i] == midVal)) {
                sb.append(0).append(" ");
                continue;
            }
            if (leftNum < rightNum || (arr[i] != midVal && leftNum == rightNum)) {
                sb.append(midVal + 1 - arr[i]).append(" ");
                continue;
            }
            sb.append(midVal - arr[i]).append(" "); //偶数
        }
        System.out.println(sb.toString());
    }
}

试题E:求阶乘

问题描述：

满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?
如果这样的 N 不存在输出 −1。

样例输入：2

样例输出：10

当时直接暴力过例子了，30%没问题，要知道阶乘的增幅是很恐怖的，暴力是过不了全部例子，复盘才发现数学的神奇之处 数学很重要(确信)

思路：

排除暴力算法，从数学的角度看问题，既然题目要求尾数0的个数，那么我们可以联想一下0是从何而来？肯定是有因子相乘等于10产生0，也就是
10 = 2 * 5

再看阶乘，比如10!，但凡是偶数肯定能分出因子2，所以因子2肯定会比5多，那么问题就可以转化成有几个5，就有几个0出现，这样问题就简单起来了，10!中，10可以提供一个5，5本身是一个，那么就有两个，也就是说10!末尾有两个0

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long k = sc.nextLong();
        long pre = k * 5;
        while (pre - 5 >= 5 && process(pre - 5) >= k) {
            pre -= 5;
        }
        if (process(pre) == k) {
            System.out.println(pre);
        } else {
            System.out.println(-1);
        }
    }

    private static long process(long l) {
        int res = 0;
        while (l >= 5) {
            res += (l / 5);
            l /= 5;
        }
        return res;
    }
}

试题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，表示限制

样例输入：

样例输出：6

太难了QAQ 复盘也不会，我是菜菜，不过这道题的原型好像是滑动窗口的单调队列，先挖个坑，往后肯定补上:P

试题G:数组切分

问题描述：

已知一个长度为 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，是一段连续的自然数。

样例输入：

1
2

4
1 3 2 4

样例输出：5

思路：

第一种可以暴力递归，第二种可以用动态规划去解决，暴力递归的话，关键在于连续切有一个规律，只要区间的最大值 - 最小值 + 1 = 区间长度，则可以认为此区间的数字是连续的，然后可以不断的去递归找到全部答案

import java.util.Scanner;

public class Solution {

    static int n;
    static int[] a;
    static int ans = 0;
    static int mod = (int) (1e9 + 7);

    private static void dfs(int start) {
        if (start >= n) {
            ans++;
            if (ans == mod) ans = 0;
            return;
        }
        int max = a[start];
        int min = a[start];
        for (int len = 1; start + len <= n; len++) {
            if (max - min + 1 == len) {
                dfs(start + len);
            }
            max = Math.max(max, a[start + len]);
            min = Math.min(min, a[start + len]);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        dfs(0);
        System.out.println(ans);
    }
}

试题H:回忆迷宫

问题描述：

爱丽丝刚从一处地下迷宫中探险归来，你能根据她对于自己行动路径的回
忆，帮她画出迷宫地图吗？
迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步
骤，每个移动步骤可能是上下左右四个方向中的一种，表示爱丽丝往这个方向
走了一格。你需要根据这些移动步骤给出一个迷宫地图，并满足以下条件：
1、爱丽丝能在迷宫内的某个空地开始，顺利的走完她回忆的所有移动步
骤。
2、迷宫内不存在爱丽丝没有走过的空地。
3、迷宫是封闭的，即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处
视为迷宫外，所有不与迷宫外联通的空地都视为是迷宫内。（迷宫地图为四联
通，即只有上下左右视为联通）
4、在满足前面三点的前提下，迷宫的墙的数量要尽可能少。

思路：暴力qvq

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[] steps = sc.next().toCharArray();
        char[][] maze = new char[256][256];
        //初始化迷宫
        for (char[] row : maze) {
            Arrays.fill(row, '*');
        }
        //初始化坐标
        int x = 100, y = 100;
        maze[x][y] = ' ';
        int u = 99, d = 101, l = 99, r = 101;
        for (char step : steps) {
            switch (step) {
                case 'U':
                    x--;
                    if (u >= x) {
                        u = x - 1;
                    }
                    maze[x][y] = ' ';
                    break;
                case 'L':
                    y--;
                    if (l >= y) {
                        l = y - 1;
                    }
                    maze[x][y] = ' ';
                    break;
                case 'D':
                    x++;
                    if (d <= x) {
                        d = x + 1;
                    }
                    maze[x][y] = ' ';
                    break;
                case 'R':
                    y++;
                    if (r <= y) {
                        r = y + 1;
                    }
                    maze[x][y] = ' ';
                    break;
            }
        }
        //修正边框
        maze[u][l] = maze[u][r] = maze[d][l] = maze[d][r] = ' ';
        for (int i = u; i <= d; i++) {
            for (int j = l; j <= r; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }
}