2022年蓝桥杯JavaB组 省赛 题目解析（含AC_Code）

前言（必读）

2022年 第13届蓝桥杯JavaB组省赛，一共有10道题目，由于小编时间、精力、能力有限，仅提供前9道题目的解析以及AC代码。

目录中AC代码部分，直接ctrl+cv 在平台跑，均可AC。（除第二题，填空题 “山” 需要在本地IDE上跑出结果，然后在平台输出答案才能AC）

每道题目的最后标注了小编对这道题目难度的主观评价，实际难度因人而异，可能更简单，可能更难。

这是真题的官方连接：蓝桥云课

好的废话不多说，咋们开始吧！

第一题：星期计算 （简单）

题目链接

问题描述

已知今天是星期六，问 $20^{22}$ 天后是星期几？

• 数字 $1$ 到 $7$ 分别表示 星期一到星期日。
• 今天是 星期六（即数字 $6$）。

要解决这个问题，我们需要计算从已知的某一天（星期六）开始，经过20²²天之后是星期几。为了防止数据溢出，我们会使用 Java 中的 BigInteger 类来处理大数运算。

思路

1. 求余法：
   • 一周有 7 天，所以 星期循环周期为 7。
   • 给定某天之后的第 ( n ) 天，可以通过取余运算来确定当天是星期几。
   • 公式为：
     $$目标星期=(起始星期+n)mod7$$
2. 起始条件：
   • 已知今天是星期六，起始数字是 6。
   • 我们要计算 20²² 天 后是星期几。
3. 使用 BigInteger：
   • 由于数字 20²² 很大，我们使用 Java 中的 BigInteger 来处理计算。

AC代码

下面是完整的 Java 代码：

import java.util.Scanner;
import java.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {

    private static BigInteger fastPow(BigInteger base,int x){
        BigInteger result = BigInteger.ONE;
        while(x>0){

            //判断是否是奇数，相当于x%2==1
            if((x&1)==1)result=result.multiply(base);
            base=base.multiply(base);
            x>>=1;//相当于x/=2
        }
        return result;
    }
    public static void main(String[] args) {
        BigInteger base=new BigInteger("20");
        BigInteger sum=fastPow(base,22);
        sum=sum.add(new BigInteger("6"));//加上起始星期数
        
        BigInteger ans=sum.mod(new BigInteger("7"));//模上7

        //注意如果ans是0 说明是星期天
        if(ans.equals(BigInteger.ZERO)){
            System.out.println(7);
            return;
        }
        System.out.println(ans.toString());
    }
}

总结

第一题填空题还是比较简单的，主要考察了求余运算以及Java中BigInteger的使用。

第二题 山 （简单）

题目链接

问题描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

这天小明正在学数数。

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

题目分析

题目要求我们统计在区间 ([2022, 2022222022]) 中，有多少个数符合 “山形数” 的特征。

山形数定义

一个 山形数 满足以下条件：

1. 回文数：即从左到右读和从右到左读相同。例如：12321, 14541。
2. 单调特性：数字先单调不减，后单调不增。例如：123565321、145541。

解题思路

这道题的核心在于同时满足回文和山形数的定义。我们可以使用以下步骤解决：

1. 回文数判断：

   • 使用双指针（对撞指针）法，一个指针从左向右遍历，一个从右向左遍历，判断两侧对应位置的字符是否相等。

2. 山形数判断：

   • 在遍历过程中，我们还需要检查数位是否符合"山形"的单调特性：
     • 数字先递增或保持不变，达到某一峰值后，再单调递减。
     • 我们在判断回文时，可以同时判断是否满足“山”的单调特性。

3. 遍历区间：

   • 遍历给定的区间 ([2022, 2022222022])，对每个数进行上述检查。
   • 如果符合条件，则计数器加1。

代码实现解析

我们可以将代码分为两个部分：

1. 判断回文和“山形”特征的函数 isOK。
2. 遍历区间的主函数。

代码详解

回文和“山形”判断函数

private static boolean isOK(char[] s) {
    int left = 0;
    int right = s.length - 1;
    // 双指针遍历
    while (left <= right) {
        // 判断是否是回文
        if (s[left] != s[right]) {
            return false;
        }
        // 判断是否符合“山”的单调特征
        if (left != 0 && (s[left] < s[left - 1] || s[right] < s[right + 1])) {
            return false;
        }
        // 左右指针继续收缩
        left++;
        right--;
    }
    return true;
}

说明：

• left 和 right 分别从字符串的两端向中间靠拢。
• 首先检查回文特性，即 s[left] == s[right]。
• 然后检查“山形”特征：
  • 从第2个字符开始比较，确保当前字符不小于前一个字符（单调不减）。
  • 左右对称检查可以同时验证“山形”特征。

主函数

public static void main(String[] args) {
    int start = 2022;
    int end = 2022222022;
    int ans = 0;
    // 遍历整个区间
    for (int i = start; i <= end; i++) {
        // 如果符合“山形”条件，则计数加1
        if (isOK(String.valueOf(i).toCharArray())) {
            ans++;
        }
    }
    System.out.print(ans);
}

说明：

• 遍历区间 ([2022, 2022222022])。
• 对每个整数调用 isOK() 判断是否是“山形数”。
• 统计满足条件的数，并输出结果。
• 最终输出答案是3138

AC代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {


    //对撞指针判断回文和是否是"山"
    private static boolean isOK(char[] s){
        int left=0;
        int right=s.length-1;
        while(left<=right){
            //不是回文，不符合条件，返回假
            if(s[left]!=s[right]){return false;}

            //不是“山”的形状，不符合条件，返回假
            if(left!=0&&(s[left]<s[left-1]||s[right]<s[right+1])){return false;}

                //符合条件继续枚举
                left++;
                right--;
        }
        return true;
    }

    public static void main(String[] args) {
        int start=2022;
        int end=2022222022;
        int ans=0;
        for(int i=start;i<=end;i++){
            if(isOK(String.valueOf(i).toCharArray()))ans++;
        }
        System.out.print(ans);

    }
}

复杂度分析

• 时间复杂度：区间的大小为 (10^9) 量级，直接遍历整个区间相对来讲时间比较长。但是这是一道填空题，我们现在控制台跑一会儿，答案出来直接在平台输出正确结果即可！
• 空间复杂度：只需常数级空间来存储中间变量，因此为 (O(1))。

总结

• 本题主要考察回文数和单调性的判断技巧。
• 使用了双指针和条件判断相结合的方法，确保同时满足“山形数”的两个要求。

第三题 字符统计 （简单）

题目链接

问题描述

给定一个只包含大写字母的字符串 S，要求找出其中出现次数最多的字符。如果有多个字符出现次数相同且为最多，则按字母表顺序依次输出所有这些字符。

解题思路

1. 统计字符出现次数：

   • 使用一个长度为26的数组 arr，对应26个大写字母 A-Z，下标 0 对应 A，下标 1 对应 B，依此类推。
   • 遍历字符串 S，对于每个字符 c，通过 c - 'A' 计算其在数组中的索引，并将对应位置的计数加1。

2. 寻找最大出现次数：

   • 遍历计数数组 arr，找到其中的最大值 max，即为出现次数最多的次数。

3. 收集所有出现次数为最大值的字符：

   • 再次遍历数组 arr，将所有计数等于 max 的字符按照字母顺序输出。

AC代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[26]; // 用于统计26个大写字母的出现次数
        String tem = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        char[] zimu = tem.toCharArray(); // 存储字母表顺序
        char[] s = sc.nextLine().toCharArray(); // 读取输入字符串并转为字符数组

        // 统计每个字符的出现次数
        for(int i = 0; i < s.length; i++){
            arr[s[i] - 'A']++;
        }

        // 找到最大出现次数
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++){
            if(max < arr[i]) max = arr[i];
        }

        // 输出所有出现次数等于最大值的字符，按字母顺序
        for(int i = 0; i < arr.length; i++){
            if(max == arr[i]){
                System.out.print(zimu[i]);
            }
        }
    }
}

代码说明

1. 输入处理：

   • 使用 Scanner 读取输入字符串，并将其转换为字符数组 s 以便遍历。

2. 字符计数：

   • 初始化一个长度为26的整型数组 arr，用于存储每个字母的出现次数。
   • 遍历字符数组 s，通过 s[i] - 'A' 计算当前字符在数组中的索引，并将对应位置的计数加1。

3. 确定最大频次：

   • 初始化 max 为最小整数值。
   • 遍历 arr 数组，更新 max 为数组中的最大值。

4. 输出结果：

   • 再次遍历 arr 数组，找到所有计数等于 max 的字母，并按字母表顺序输出。

复杂度分析

• 时间复杂度：O(N + 26)，其中 N 是字符串 S 的长度。统计字符和查找最大值的过程各自为线性时间，常数项可忽略。
• 空间复杂度：O(1)，使用固定大小的数组 arr 存储26个字母的计数。

总结

这道题目的解法运用了类似哈希的方式取记录每一个字母出现的次数，进而提高效率。这种方法在22年之前的真题中也出现过，具体我记不清了，大家可以去探索一下。

第四题：最小刷题数 （中等）

题目链接

问题描述

小蓝老师的编程课有 ( N ) 名学生，编号依次为 ( 1, 2, …, N )。每个学生在这学期刷了 ( A_i ) 道题。对于每个学生，我们需要计算他至少还要再刷多少道题，才能确保全班中刷题数不低于他的学生人数比他少。

输入：

• 第一行包含一个整数 ( N )（学生人数）。
• 第二行包含 ( N ) 个整数 ( A_1, A_2, …, A_N )（每个学生的刷题数）。

输出：

• 输出 ( N ) 个整数，表示每个学生分别至少还需要再刷多少道题。

样例输入

5
12 10 15 20 6

样例输出

0 3 0 0 7

思路分析

这道题的目标是对于每个学生，计算他需要刷的最少题目数，使得他在班级内刷题数不低于其他同学的人数比他少。

解题思路：

1. 统计刷题数的频次：

   • 使用一个数组 cnt，其中 cnt[i] 表示刷题数小于等于 ( i ) 的学生人数。

2. 前缀和：

   • 对 cnt 数组进行前缀和计算，确保 cnt[i] 包含刷题数小于等于 ( i ) 的学生总数。

3. 寻找需要刷题的最小数量：

   • 遍历所有可能的刷题数 ( i )，找到符合条件的最小 ( i )，即使得 cnt[i-1] >= n - cnt[i] 成立。
   • 此时，如果学生当前的刷题数 ( A_i ) 小于 ( i )，那么需要刷到 ( i ) 才能满足条件。

算法步骤

1. 初始化：

   • 读取输入数据。
   • 使用数组 cnt 统计每个刷题数的频次，同时记录最大刷题数 maxT。

2. 计算前缀和：

   • 更新 cnt 数组，使其存储刷题数小于等于某个值的学生人数。

3. 寻找需要刷题的最小数量：

   • 遍历可能的刷题数，找到满足条件的 pos 和 sign，分别表示第一次满足要求的刷题数和最小需要刷到的题数。

4. 输出结果：

   • 对每个学生，计算需要再刷的题数。如果当前题数已经大于等于需要刷题的最小数，则输出 0，否则输出还需要再刷的题数。

AC代码

import java.util.Scanner;

public class Main {

    private static int max(int a, int b) { return a > b ? a : b; }
    
    // cnt[i] 表示刷题数小于等于 i 的人数
    static int[] cnt = new int[100010];
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 班级人数
        int maxT = Integer.MIN_VALUE; // 最大刷题数
        int[] A = new int[n + 1]; // 第 i 个同学的刷题数
        
        // 读取输入并统计刷题数频次
        for (int i = 1; i <= n; i++) {
            A[i] = in.nextInt();
            cnt[A[i]]++;
            maxT = max(maxT, A[i]);
        }

        // 计算前缀和
        for (int i = 1; i <= maxT; i++) {
            cnt[i] += cnt[i - 1];
        }

        // 定义 pos 和 sign，用于找到满足条件的最小刷题数
        int pos = -1;
        int sign = -1;
        for (int i = 1; i <= maxT; i++) {
            // 寻找 pos，使得 cnt[i-1] >= n - cnt[i]
            if (cnt[i - 1] >= n - cnt[i]) {
                if (pos == -1) pos = i;
            }
            
            // 寻找 sign，使得 cnt[i-1] - 1 >= n - cnt[i]
            if (cnt[i - 1] - 1 >= n - cnt[i]) {
                if (sign == -1) {
                    sign = i;
                    break;
                }
            }
        }

        // 输出结果
        if (pos == -1) {
            // 如果不存在满足条件的 pos，输出 0
            for (int i = 1; i <= n; i++) {
                System.out.print(0 + " ");
            }
        } else {
            // 对于每个学生，计算需要刷的最少题数
            for (int i = 1; i <= n; i++) {
                if (A[i] >= pos) {
                    System.out.print("0 ");
                } else {
                    int t = sign - A[i];
                    System.out.print(t + " ");
                }
            }
        }
    }
}

代码解析

1. 读取输入：

   • 读取学生人数 ( N ) 和每个学生的刷题数。

2. 统计频次：

   • cnt 数组统计各个刷题数的频次。

3. 计算前缀和：

   • 更新 cnt 数组，使其存储小于等于某个值的学生人数。

4. 寻找最小刷题数：

   • 遍历所有可能的刷题数，找到满足条件的 pos 和 sign。

5. 输出结果：

   • 根据 pos 和 sign 计算每个学生需要刷的最少题数。

总结

这道题考察了如何通过前缀和和频次统计解决刷题数比较的问题。

第五题 求阶乘 （中等）

题目链接

问题描述

给定一个整数K，寻找最小的整数N，使得N!（N的阶乘）末尾恰好有K个0。如果不存在这样的N，则输出-1。

示例

输入：

2

输出：

10

解释：10! = 3628800，末尾有2个0。

将问题转换为求阶乘中5的个数

要确定阶乘N!末尾有多少个0，我们需要理解0是由因子10产生的。而10可以分解为2和5的乘积。因此，阶乘N!中因子2和5的数量决定了末尾0的个数。

在阶乘中，因子2的数量通常多于因子5的数量。因此，末尾0的个数实际上由因子5的数量决定。因此，问题转化为：找到N!中因子5的数量恰好为K。

具体来说，N!中因子5的数量可以通过以下公式计算：

$${\text{Count}}_5(N!)=\lfloor \frac{N}{5}\rfloor +\lfloor \frac{N}{5^2}\rfloor +\lfloor \frac{N}{5^3}\rfloor +\cdots$$

其中，$\lfloor \cdot \rfloor$表示向下取整。

应用Legendre定理

上述公式实际上是Legendre定理的应用。Legendre定理用于计算一个质数在阶乘中的指数。对于质数p，N!中p的指数为：

$${\text{Count}}_p(N!)=\sum _{i=1}^{\infty }\lfloor \frac{N}{p^i}\rfloor$$

在本问题中，我们选择p=5，因为5的数量决定了末尾0的数量。

通过Legendre定理，我们可以高效地计算N!中因子5的数量，从而解决问题。

二分查找法

为了找到最小的N使得N!中因子5的数量恰好为K，我们可以使用二分查找法。具体步骤如下：

1. 初始化搜索范围：设定左边界left为0，右边界right为一个足够大的值（如$10^{18}$）。
2. 中间值计算：计算mid = left + (right - left) / 2。
3. 因子5的数量比较：
   • 如果${\text{Count}}_5(\text{mid})\ge K$，则记录当前mid为可能的答案，并将右边界right调整为mid - 1。
   • 否则，将左边界left调整为mid + 1。
4. 循环终止：当left > right时，检查记录的答案是否满足${\text{Count}}_5(\text{ans})=K$，如果满足，则输出ans，否则输出-1。

这种方法的时间复杂度为$O(\log N)$，在处理大规模数据时非常高效。

AC代码

以下是基于上述思路的Java_AC代码：

import java.math.BigInteger;
import java.util.*;

// Legendre定理
public class Main{

    private static long get5(long a){
        long ans=0;
        while(a>0){
            ans += a / 5L;
            a /= 5L;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long k = in.nextLong();
        long left = 0L;
        long right = Long.MAX_VALUE;
        long ans = 0L;
        while(left <= right){
            long mid = left + (right - left) / 2;
            if(get5(mid) >= k){
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if(get5(ans) == k)
            System.out.print(ans);
        else
            System.out.print("-1");
    }
}

代码解析

1. get5方法：该方法根据Legendre定理计算给定数a中因子5的数量。
2. 主方法：
   • 读取输入的K值。
   • 初始化二分查找的左右边界。
   • 在循环中不断调整搜索范围，直到找到满足条件的最小N。
   • 最后，验证找到的N是否确实使N!中因子5的数量为K，若是则输出N，否则输出-1。

第六题 最大子矩阵 （简单）

题目链接

问题描述

给定一个20×20的矩阵，每个元素都是1到9之间的整数。我们的任务是找到所有可能的5×5子矩阵，并计算出其中元素之和的最大值。

示例矩阵（把空格都去掉，反正也不多就20行）

69859241839387868941
17615876963131759284
37347348326627483485
53671256556167864743
16121686927432329479
13547413349962773447
27979945929848824687
53776983346838791379
56493421365365717745
21924379293872611382
93919353216243561277
54296144763969257788
96233972513794732933
81443494533129939975
61171882988877593499
61216868895721348522
55485345959294726896
32124963318242554922
13593647191934272696
56436895944919899246

解题思路

为了找到最大5×5子矩阵的和，我们需要遍历上面的这个个20×20矩阵，计算每一个可能的5×5子矩阵的元素和，并记录其中的最大值。没错就这么简单。

步骤概述

1. 输入数据处理：

   • 将每一行的字符串转换为数字矩阵。

2. 遍历所有可能的5×5子矩阵：

   • 对于每一个可能的起始点（即左上角），计算其对应的5×5子矩阵的和。

3. 记录最大和：

   • 在遍历过程中，持续更新记录的最大和。

数学表示

设原矩阵为 $(M)$，其元素为 $(M_{i,j})$，其中 $(1\le i,j\le 20)$。

我们需要找到所有可能的5×5子矩阵 $(S)$，其左上角坐标为 $(a,b)$，满足 $(1\le a\le 16)$ 且 $(1\le b\le 16)$。

对于每一个子矩阵 $S(a,b)$，其和为：

$$\text{Sum}(a,b)=\sum _{i=a}^{a+4}\sum _{j=b}^{b+4}{M}_{i,j}$$

我们的目标是找到：

$$\underset{1\le a,b\le 16}{\max }\text{Sum}(a,b)$$

实现步骤

下面通过Java代码示例，具体展示如何实现上述步骤。

AC代码

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

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[][] matrix = new int[20][20];
        
        // 读取输入并构建数字矩阵
        for (int i = 0; i < 20; i++) {
            String line = scan.next();
            for (int j = 0; j < 20; j++) {
                matrix[i][j] = line.charAt(j) - '0';
            }
        }
        
        int maxSum = Integer.MIN_VALUE;
        
        // 遍历所有可能的5x5子矩阵
        for (int i = 0; i <= 15; i++) { // 行
            for (int j = 0; j <= 15; j++) { // 列
                int currentSum = 0;
                for (int x = i; x < i + 5; x++) {
                    for (int y = j; y < j + 5; y++) {
                        currentSum += matrix[x][y];
                    }
                }
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        
        // 输出最大和
        System.out.println(maxSum);
    }
}

代码说明

1. 输入处理：

   • 使用Scanner读取20行输入，每行包含20个数字。
   • 将每个字符转换为对应的整数，存储在二维数组matrix中。

2. 遍历子矩阵：

   • 外层两个循环i和j分别代表子矩阵左上角的行和列起始点，范围都是0到15（因为子矩阵大小为5）。
   • 内层两个循环x和y用于遍历当前子矩阵的所有元素，并计算其和currentSum。

3. 记录最大和：

   • 每计算一个子矩阵的和后，比较并更新maxSum。

4. 输出结果：

   • 最终打印出maxSum，即为所有5×5子矩阵中的最大和。

结果分析

通过上述方法，我们遍历了所有可能的5×5子矩阵，共计 $(16\times 16=256)$ 个子矩阵，并计算出了每个子矩阵的和。最终，maxSum存储了这些和中的最大值。

总结

第一道简单的模拟填空题，注意一下边界条件即可。答案是154，直接输出即可.

第七题 数组切分 （中等偏难）

题目链接

问题描述

给定一个长度为 ( N ) 的数组 ( A = [A_1, A_2, \dots, A_N] )，该数组是1到N的一个排列。要求将数组 ( A ) 切分成若干个（至少一个，最多N个）连续的子数组，使得每个子数组中的整数恰好可以组成一段连续的自然数。

示例

输入样例：

4
1 3 2 4

输出样例：

5

解释：
数组 ( A = [1, 3, 2, 4] ) 有以下5种切分方法：

1. 每个元素单独作为一个子数组：([1], [3], [2], [4])
2. ([1], [3, 2], [4])
3. ([1], [3, 2, 4])
4. ([1, 3, 2], [4])
5. 整个数组作为一个子数组：([1, 3, 2, 4])

总共5种不同的切分方法。

动态规划解法

为了高效计算所有可能的切分方法，我们采用动态规划的方法。以下是详细的解题步骤。

1、状态表示

我们定义一个数组 $(dp)$ ，其中 $(dp[i])$ 表示前 $(i)$ 个元素的切分方法总数。

2、状态初始化

• ( dp[0] = 1 )：表示空数组有一种切分方式，即不切分。

3、状态转移方程

对于每个位置 $(i)$（从1到N），我们考虑所有可能的前一个切分点 $(j)$（从1到i），判断子数组 $(A[j..i])$ 是否可以构成一段连续的自然数。如果可以，则将 $(dp[j-1])$ 加入到 $(dp[i])$ 中。

数学表达式为：

$$dp[i]=\sum _{j=1}^i\text{if }A[j..i]\text{ 是连续自然数段，则 }dp[i]+=dp[j-1]$$

这种状态方程可行的原因是如果区间[j,i]的数字是连续的，那么i之前的方案数(1到i)，就是j-1之前的方案数（1到j-1)！ 因为j到i的数字是连续的，算是一种切分方法啊！

判断子数组是否连续

为了判断子数组 ( A[j…i] ) 是否能构成一段连续的自然数，我们可以利用以下性质：

一个数组的元素是不重复的连续的自然数（题目说明给的数组是1到N的排列，所以满足），那么：

$$\text{max}(A[j..i])-\text{min}(A[j..i])+1=i-j+1=区间[j,i]中元素的个数$$

其中，$(max(A[j..i]))$ 表示子数组的最大值，$(min(A[j..i]))$ 表示子数组的最小值。
另外，上述式子中两边的+1可以消掉,+1主要是为了好理解为什么会有这个性质。

AC代码

以下是上述思路的Java代码：

import java.util.*;

public class Main{
    static int N=10010;
    static int[] arr=new int[N];

    private static int max(int a,int b){return a>b?a:b;}
    private static int min(int a,int b){return a<b?a:b;}
    
//把加法进行封装，自动取模
    private static long add(long a,long b){
        long mod=(long)1e9+7;
        return (a + b) % mod;
    }

    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        for(int i=1;i<=n;i++) arr[i]=in.nextInt();
        long[] dp=new long[n+1]; // dp[i]表示前i个数的切分方法数
        dp[0]=1;
        for(int i=1;i<=n;i++){
            long mins=Long.MAX_VALUE;
            long maxs=Long.MIN_VALUE;
            for(int j=i;j>=1;j--){
                mins = min(mins, arr[j]);
                maxs = max(maxs, arr[j]);
                // 判断子数组A[j..i]是否连续
                if(maxs - mins + 1 == i - j + 1){
                    dp[i] = add(dp[i], dp[j-1]);//等价于dp[i]+=dp[j-1]并且取mod 1e9+7
                }
            }
        }
        System.out.print(dp[n]);
    }
}

代码详解

1. 输入读取：首先读取数组的长度 ( N ) 和数组元素 ( A )。

2. DP数组初始化：初始化 ( dp[0] = 1 )，表示空数组有一种切分方式。

3. 双重循环遍历：

   • 外层循环遍历每个位置 ( i ) 从1到N。
   • 内层循环遍历每个可能的切分点 ( j ) 从 ( i ) 到1，逐步计算子数组 ( A[j…i] ) 的最小值和最大值。

4. 判断连续性：对于每个子数组 ( A[j…i] )，检查是否满足 $(textmax-min+1=i-j+1)$，如果满足，则更新 $(dp[i])$。

5. 结果输出：最终输出 ( dp[N] ) 即为答案。

第八题 回忆迷宫 （中等）

解题思路

本题要求根据爱丽丝在二维网格迷宫中的移动路径，重构出符合特定条件的迷宫地图。
我们的答题逻辑是：

1. 粗略判断迷宫的大体尺寸
2. 把整个迷宫全部设置成墙
3. 计算爱丽丝的起始位置在哪
4. 从爱丽丝的起始位置开始根据回忆进行移动，移动的地方设置成’空格，周围四个位置标记一下
5. 去除没有被标记的墙
6. 打印最终的迷宫

以下是逐步的解题思路：

1. 路径解析与边界确定

首先，根据爱丽丝的移动路径，确定她在迷宫中的所有经过的位置，从而确定迷宫的边界。

• 初始化位置：设爱丽丝的起始位置为 $(0,0)$。
• 遍历路径：逐步根据移动指令（‘U’、‘D’、‘L’、‘R’）更新当前坐标：
  • ‘U’：向上移动，$x$ 坐标减 $1$。
  • ‘D’：向下移动，$x$ 坐标加 $1$。
  • ‘L’：向左移动，$y$ 坐标减 $1$。
  • ‘R’：向右移动，$y$ 坐标加 $1$。
• 记录边界：在移动过程中，持续更新最小和最大 $x$、$y$ 坐标，记为 $\text{minx}$、$\text{maxx}$、$\text{miny}$、$\text{maxy}$，以确定迷宫的整体尺寸。

2. 计算迷宫尺寸与起始位置

根据路径遍历得到的边界，计算迷宫的高度 $H$ 和宽度 $W$：

$$H=\text{maxx}-\text{minx}+3$$

$$W=\text{maxy}-\text{miny}+3$$

这里增加 $3$ 是为了在迷宫四周留出足够的墙壁空间，确保迷宫的封闭性。
+1，是为了对齐下标，我们舍弃下标0，从下标1开始表示位置。
+2，是为了给左右或者上下的墙留位置。

确定爱丽丝的起始位置在迷宫网格中的坐标：

$$\text{start\_x}=2-\text{minx}$$

$$\text{start\_y}=2-\text{miny}$$

3. 构建初始迷宫网格

• 初始化网格：创建一个 $H\times W$ 的字符网格，初始全部填充为墙壁字符 '*'。
• 标记路径：根据爱丽丝的移动路径，从起始位置出发，按照移动指令逐步在网格中标记为非墙壁字符 ' '，表示通路。同时，记录每个位置周围的四个方向为可能的墙壁位置。

4. 移除多余的墙壁

为了满足迷宫内不存在未走过的空地，并使迷宫封闭，需要移除多余的墙壁：

• 识别外部空间：通过广度优先搜索（BFS）从迷宫边界开始，标记所有连通到外部的空白区域。
• 更新墙壁：将与外部连通的空白区域保持为 ' '，而不连通的部分则保持或恢复为墙壁 '*'。

这样确保迷宫内部只有爱丽丝实际经过的路径，没有多余的空地，同时迷宫与外部通过墙壁完全隔离。

5. 输出迷宫地图

按照题目要求输出迷宫地图时，需要满足以下条件：

• 边界条件：

  • 至少有一行第一个字符为 '*'。
  • 第一行至少有一个空格 ' '。
  • 每一行的最后一个字符为 '*'。
  • 最后一行至少有一个 '*'。

• 打印格式：逐行输出网格字符，构成最终的迷宫地图。

AC代码：

import java.util.*;

public class Main {

    //迷宫的边界
    static int minx, maxx, miny, maxy;

    //迷宫的实际边界
    static int H, W;

    //实际的图
    static char[][] g;

    //用来判断是否是迷宫空地周围的墙
    static boolean[][] isWall;

//用来上下左右移动
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        char[] dir = in.nextLine().toCharArray();

        //初始化所有数组
        g = new char[n + 4][n + 4];
        isWall = new boolean[n + 4][n + 4];


        //计算迷宫的边界
        int nx = 0, ny = 0;
        for (int i = 0; i < n; i++) {
            switch (dir[i]) {
                case 'U':
                    nx--;
                    break;
                case 'D':
                    nx++;
                    break;
                case 'L':
                    ny--;
                    break;
                case 'R':
                    ny++;
                    break;
            }
            if (minx > nx) minx = nx;
            if (maxx < nx) maxx = nx;
            if (miny > ny) miny = ny;
            if (maxy < ny) maxy = ny;
        }

        H = maxx - minx + 3;
        W = maxy - miny + 3;

        //先把图都变成墙
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) g[i][j] = '*';
        }

        //爱丽丝的起始坐标
        nx = 2 - minx;
        ny = 2 - miny;

        g[nx][ny] = ' ';
        mark(nx, ny);

        //按照路径，标记周围，从而知道迷宫内
        for (int i = 0; i < n; i++) {
            switch (dir[i]) {
                case 'U':
                    nx--;
                    break;
                case 'D':
                    nx++;
                    break;
                case 'L':
                    ny--;
                    break;
                case 'R':
                    ny++;
                    break;
            }
            g[nx][ny]=' ';
            mark(nx,ny);
        }

        //把周围不是墙的地方改成' '
        //用bfs改
        Queue<Integer> queue=new ArrayDeque<>();
        for(int i=1;i<=H;i++){
            for(int j=1;j<=W;j++){
                if(!isWall[i][j]&&(i==1||i==H||j==1||j==W)){
                    queue.add(i*200+j);
                    g[i][j]=' ';
                }
            }
        }

        //开始bfs
        while(!queue.isEmpty()){
            int pack=queue.poll();
            int x=pack/200;
            int y=pack%200;
            for(int i=0;i<4;i++){
                int xx=x+dx[i];
                int yy=y+dy[i];
                if(xx>=1&&xx<=H&&yy>=1&&yy<=W&&!isWall[xx][yy]&&g[xx][yy]=='*'){
                    g[xx][yy]=' ';
                    queue.add(xx*200+yy);
                }
            }
        }

        //打印数组
        for(int i=1;i<=H;i++){
            for(int j=1;j<=W;j++){
                System.out.print(g[i][j]);
            }
            System.out.println();
        }

    }

    //把周围标记成true isWall
    private static void mark(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx>=1&&xx<=H&&yy>=1&&yy<=W){
                isWall[xx][yy] = true;
            }
        }

    }
}

总结

通过上述步骤，我们能够根据爱丽丝的移动路径准确重构出一个符合题目要求的迷宫地图。关键在于：

1. 边界确定：通过遍历路径找到迷宫的最小和最大坐标，计算出迷宫的尺寸。
2. 路径标记：在网格中标记爱丽丝实际经过的路径，确保迷宫内没有未走过的空地。
3. 墙壁优化：利用 BFS 移除多余墙壁，保证迷宫的封闭性和最少的墙壁数量。

这种方法不仅确保了迷宫的正确性，还优化了墙壁的数量，满足题目中的所有约束条件。

第九题 红绿灯 （中等偏难）

题目链接

问题概述

爱丽丝需要驾驶汽车从家出发前往公司，距离是N路上有M个红绿灯。汽车的最快速度是1/V。为了尽量缩短通勤时间，爱丽丝给汽车安装了氮气喷射装置，能够实现瞬移和瞬间停止，但使用有一定限制，需要经过k个红绿灯才可以再次使用，并且只能瞬移到下一个最近的红绿灯，因为过红绿灯不能加速。我们的目标是计算爱丽丝到达公司的最短时间。第i个红绿灯离家的距离是A[i],绿灯持续时间是B[i]，红灯持续时间时间是B[i]。（i在区间[1,M]中）

动态规划求解

为什么可以使用动态规划？
动态规划（Dynamic Programming, DP）适用于这类具有最优子结构和重叠子问题的优化问题。在本题中，爱丽丝在每一个红绿灯前的决策（是否使用氮气喷射装置，也就是瞬移）会影响之后的状态，而每个红绿灯的状态依赖于之前的决策。这种逐步决策并且每一步决策依赖于之前状态的特性，使得动态规划成为解决此问题的理想方法。

状态表示的定义

我们定义一个二维的动态规划数组 dp[i][j]，表示在恰好通过第 i 个红绿灯后，还需要经过 j 个红绿灯才能再次使用氮气喷射装置的最小时间。

• i：表示已经通过的红绿灯编号（从 0 到 M+1，其中 M+1 表示到达公司）。
• j：表示在当前状态下，还需经过多少个红绿灯才能再次使用氮气喷射装置（0 表示装置可用）。

状态转移方程的推导

对于每一个红绿灯 i，我们有两种选择：

1. 使用氮气喷射装置瞬间通过红绿灯：

   • 这要求当前装置是可用的（即 j = 0）。
   • 使用装置后，需要等待 K 个红绿灯冷却，故新的状态为 j = K-1。
   • 需要考虑当前红绿灯的状态（绿灯或红灯）是否需要等待。

2. 不使用氮气喷射装置，按正常速度行驶：

   • 速度为 1/V 米/秒，从上一个红绿灯 i-1 到当前红绿灯 i 需要时间 T = (A[i] - A[i-1])*V。（题目挺好心的，给我们的是V，速度是1/V，这样避免了浮点数运算）
   • 到达当前红绿灯时可能需要等待红灯，此时需要计算等待时间。
   • 装置冷却时间相应减少，即 j 递减（不低于 0）。

具体的状态转移方程如下：

• 使用氮气喷射装置（前提 j = 0）：
  $$dp[i][K-1]=\min (dp[i][K-1],dp[i-1][0]+\text{等待时间})$$

• 不使用氮气喷射装置：
  $$dp[i][\max (0,j-1)]=\min (dp[i][\max (0,j-1)],dp[i-1][j]+T+\text{等待时间})$$

其中，等待时间根据当前到达时间与红绿灯的周期决定：

• 红绿灯周期为 $B[i]+C[i]$ 秒。
• 当前到达时间模周期若小于 $B[i]$，则为绿灯，可直接通过。
• 若大于等于 $B[i]$，则为红灯，需要等待 $B[i]+C[i]-(t\mathrm{mod}(B[i]+C[i]))$ 秒。

动态规划数组的初始化

• 我们初始化 dp[0][0] = 0，表示起点（家）处，氮气喷射装置可用，所需时间为 0。
• 其他状态初始化为无穷大（INF），表示初始时不可达。

详细算法步骤

1. 输入读取：

   • 读取总距离 N，红绿灯数量 M，氮气喷射装置冷却需要经过的红绿灯数量 K，以及最高速度 V。
   • 读取每个红绿灯的位置 A[i]，绿灯持续时间 B[i]，红灯持续时间 C[i]。

2. 动态规划表格填充：

   • 对每个红绿灯 i 从 1 到 M+1（M+1 表示公司）进行遍历。
   • 对每个可能的 j（从 0 到 K）进行状态更新：
     • 使用氮气喷射装置：
       • 仅当 j = 0 时可用。
       • 更新 dp[i][K-1]，并计算可能的等待时间。
     • 不使用装置：
       • 计算从 i-1 到 i 所需的时间 T = (A[i] - A[i-1])*V。
       • 计算到达时是否需要等待红灯，并相应增加等待时间。
       • 更新 dp[i][max(0, j-1)]。

3. 结果获取：

   • 遍历 dp[M+1][j]（所有冷却状态下到达公司的时间），取最小值作为最终答案。

AC代码

import java.util.*;

public class Main {

    // 定义一些辅助函数，用于求最大值和最小值
    static int max(int a, int b) { return a > b ? a : b; }
    static int min(int a, int b) { return a > b ? b : a; }
    static long max(long a, long b) { return a > b ? a : b; }
    static long min(long a, long b) { return a > b ? b : a; }

    static long INF=Long.MAX_VALUE;


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        long n=in.nextLong();
        int m=in.nextInt();
        int k=in.nextInt();
        long v=in.nextLong();

        long[] A=new long[m+2];
        long[] B=new long[m+2];
        long[] C=new long[m+2];
        for(int i=1;i<=m;i++){
            A[i]=in.nextLong();
            B[i]=in.nextLong();
            C[i]=in.nextLong();
        }

        //dp[i][j]表示恰好过了第i个红绿灯 还需要经过j个红绿灯才可以瞬移的最小时间
        long[][] dp=new long[m+2][k+1];
        for(int i=0;i<=m+1;i++)Arrays.fill(dp[i],INF);

        dp[0][0]=0;
        A[m+1]=n;
        B[m+1]=1;//这里是终点位置，初始化1的原因，下面状态转移会提及
        for(int i=1;i<=m+1;i++){
            //选择瞬移
            dp[i][k-1]=dp[i-1][0];

            //判断之前是否需要的等待红绿灯
            if(dp[i][k-1]%(B[i]+C[i])>=B[i]){
                dp[i][k-1]+=C[i]+B[i]-dp[i][k-1]%(B[i]+C[i]);//当i转移道m+1，如果B[m+1]等于0，对于模运算是非法的！！！我们可以把B[m+1]初始化成1，这样一来，任何数%B[m+1]都是0，不会影响结果！
            }

            // 不瞬移需要更新所有可能的冷却状态
            for(int j=0;j<=k;j++){
                if(dp[i-1][j]==INF)continue;//这个状态不可达，就不用管

                long t=dp[i-1][j]+(long)(A[i]-A[i-1])*v;

                if(t%(B[i]+C[i])>=B[i])t+=B[i]+C[i]-t%(B[i]+C[i]);
                dp[i][max(0,j-1)]=min(dp[i][max(0,j-1)],t);
            }

        }

        long ans=Long.MAX_VALUE;
        for(int i=0;i<=k;i++){
            ans=min(ans,dp[m+1][i]);
        }
        System.out.print(ans);



    }
}