第十四届蓝桥杯三月真题刷题训练——第 23 天

悠悠 2023-09-27 16:44 47阅读 0赞

**目录**

第 1 题：长草

题目描述

输入描述

输出描述

输入输出样例

运行限制

代码：

思路：

第 2 题：蓝肽子序列\_LCS\_最长公共子序列dp问题

题目描述

输入描述

输出描述

输入输出样例

运行限制

代码：

思路：

第 3 题：迷宫与陷阱

第 4 题：送礼物

--------------------

## 第 1 题：[长草][Link 1] ##

> #### 题目描述 ####
> 
> 小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
> 
> 小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
> 
> 这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
> 
> 这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。
> 
> #### 输入描述 ####
> 
> 输入的第一行包含两个整数 n,m。
> 
> 接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
> 
> 接下来包含一个整数 k。 其中，2≤n,m≤1000，1≤k≤1000。
> 
> #### 输出描述 ####
> 
> 输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
> 
> #### 输入输出样例 ####
> 
> 示例
> 
> > 输入
> 
>     4 5
>     .g...
>     .....
>     ..g..
>     .....
>     2
> 
> > 输出
> 
>     gggg.
>     gggg.
>     ggggg
>     .ggg.
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 256M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day23;
    
    import java.io.*;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * @author yx
     * @date 2023-03-26 19:37
     */
    public class 长草__BFS {
        static PrintWriter out =new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
        static int[] X=new int[]{0,0,-1,1};
        static int[] Y=new int[]{1,-1,0,0};
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         *
         * 输出
         * out.print();
         * out.flush();
         *
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        public static void main(String[] args) throws IOException {
            String[] sp=ins.readLine().split(" ");
            int n=Integer.parseInt(sp[0]);
            int m=Integer.parseInt(sp[1]);
            String[][]map=new String[n][m];
            boolean[][] isTrue=new boolean[n][m];
            Queue<int[]> queue=new LinkedList<>();
            for (int i = 0; i < n; i++) {
                map[i]=ins.readLine().split("");
                for (int j = 0; j < m; j++) {
                    if(map[i][j].equals("g")){
    //                    System.out.println(i+" "+j);
                        queue.offer(new int[]{i,j});
                        isTrue[i][j]=true;
                    }
                }
            }
            int K=Integer.parseInt(ins.readLine());
    //        in.nextToken();
    //        int K=(int) in.nval;
            int i=0;
            while (i<K){
                i++;
                int length=queue.size();
                for (int l = 0; l < length; l++) {
                    int[] nums = queue.poll();
                    int x=nums[0];
                    int y=nums[1];
                    for (int j = 0; j < 4; j++) {
                        int newX = x + X[j];
                        int newY = y + Y[j];
                        if (newX < n && newY < m && newX >= 0 && newY >= 0 && !isTrue[newX][newY] && map[newX][newY].equals(".")) {
                            map[newX][newY] = "g";
    //                        System.out.println(newX + " " + newY);
                            isTrue[newX][newY]=true;
                            queue.offer(new int[]{newX, newY});
                        }
                    }
                }
            }
            /*
            这个地方out.flush放在最后
            不然输出会超时
            频繁的使用out.flush也会有开销
             */
    //        for (int j = 0; j < n; j++) {
    //            for (int k = 0; k < m; k++) {
    //                out.print(map[j][k]);
    //            }
    //            out.println();
    //        }
    //            out.flush();
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    System.out.print(map[j][k]);
                }
                System.out.println();
            }
        }
    }

![3a2accc3e1384faf90dd7443814b6403.png][]

### 思路： ###

> **这题没啥好讲的，裸bfs板子，跟day19的灌溉一模一样**
> 
> [第十四届蓝桥杯三月真题刷题训练——第 19 天\_小羊不会飞的博客-CSDN博客第 1 题：灌溉第 2 题：小朋友崇拜圈第 3 题：括号序列第 4 题：砍竹子 题解链接：砍竹子题解![favicon32.ico][]https://blog.csdn.net/m0\_55858611/article/details/129701723?spm=1001.2014.3001.5501][19 _-CSDN_ 1 _ 2 _ 3 _ 4 _ _favicon32.ico_https_blog.csdn.net_m0_55858611_article_details_129701723_spm_1001.2014.3001.5501]

## 第 2 题：[蓝肽子序列\_LCS\_最长公共子序列dp问题][LCS_dp] ##

> #### 题目描述 ####
> 
> L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
> 
> 生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
> 
> 具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
> 
> 在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
> 
> 如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
> 
> 给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
> 
> #### 输入描述 ####
> 
> 输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
> 
> 其中有 ，两个字符串的长度均不超过 1000。
> 
> #### 输出描述 ####
> 
> 输出一个整数，表示最长的那个公共蓝肽子序列的长度。
> 
> #### 输入输出样例 ####
> 
> 示例
> 
> > 输入
> 
>     LanQiaoBei
>     LanTaiXiaoQiao
> 
> > 输出
> 
>     2
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 128M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day23;
    
    import java.io.*;
    import java.util.ArrayList;
    import java.util.HashMap;
    
    /**
     * @author yx
     * @date 2023-03-26 20:31
     */
    public class 蓝肽子序列 {
        static PrintWriter out =new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         *
         * 输出
         * out.print();
         * out.flush();
         *
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        public static void main(String[] args) throws IOException {
            String s1=ins.readLine();
            String s2=ins.readLine();
            char[] arr1=s1.toCharArray();
            char[] arr2=s2.toCharArray();
            int length1=s1.length();
            int length2=s2.length();
            int temp1=0;
            int temp2=0;
            ArrayList<String>list1=new ArrayList<>();
            ArrayList<String>list2=new ArrayList<>();
            for (int i = 1; i < length1; i++) {
                if(arr1[i]>='A'&&arr1[i]<='Z'){
                    list1.add(s1.substring(temp1,i));
                    temp1=i;
                    //最后一个单词为大写的情况
                    if(i==length1-1){
                        list1.add(arr1[i]+"");
                    }
                }else if(i==length1-1){
                    list1.add(s1.substring(temp1,length1));
                }
            }
            for (int i = 1; i < length2; i++) {
                if(arr2[i]>='A'&&arr2[i]<='Z'){
                    list2.add(s2.substring(temp2,i));
                    temp2=i;
                    //最后一个单词为大写的情况
                    if(i==length2-1){
                        list2.add(arr2[i]+"");
                    }
                }else if(i==length2-1){
                    list2.add(s2.substring(temp2,length2));
                }
            }
            int size1=list1.size();
            int size2=list2.size();
            int[][] dp=new int[size1+1][size2+1];
            for (int i = 0; i <size1 ; i++) {
                System.out.print(list1.get(i)+" ");
            }
            for (int j = 0; j < size2; j++) {
                System.out.print(list2.get(j)+" ");
            }
            for (int i = 1; i <= size1 ; i++) {
                for (int j = 1; j <= size2 ; j++) {
                    if(list1.get(i-1).equals(list2.get(j-1))){
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else {
                        dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                    }
                }
            }
            out.println(dp[size1][size2]);
            out.flush();
        }
    }

![afb62ae276bd480b96839975ffe2ad2e.png][]

### 思路： ###

> **这道题目考察两个点：**
> 
> **(1)字符串切割（存储每个以大写字母为开头的单词）**
> 
> **(2)最长公共子序列问题（LCS）**
> 
> 1.  最长公共子序列我们需要分别遍历字符串S1和字符串S2
> 2.  遍历比较的时候只会出现两种情况：字符串相等或字符串不等
> 3.  对应这两种状态分别给出两种dp状态转移方程：
> 
>  *  相等：dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1
>  *  不相等:dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i\]\[j-1\])
>  *  **dp\[i\]\[j\]的表示含义：**字符串S1的前i个字符和字符串S2的前j个字符可以构成最长公共子序列为:dp\[i\]\[j\]
> 
> **关于最长公共子序列,leetcode有类似的题目:**
> 
> [力扣![icon-default.png?t=N2N8][icon-default.png_t_N2N8]https://leetcode.cn/problems/longest-common-subsequence/][icon-default.png_t_N2N8_icon-default.png_t_N2N8_https_leetcode.cn_problems_longest-common-subsequence]**一个LCS讲的非常不错的B站视频：**
> 
> [包教包会～最长公共子序列\_哔哩哔哩\_bilibili\-, 视频播放量 16998、弹幕量 66、点赞数 638、投硬币枚数 491、收藏人数 506、转发人数 150, 视频作者 81895507389\_bili, 作者简介 ，相关视频：\[轻松掌握动态规划\]5.最长公共子序列 LCS，最长公共子序列，LCS, 一看就头疼，它真的有这么难懂吗？，06序列类dp-多序列问题-最长公共子序列，最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming，最长公共子序列与最长公共子串问题，LeetCode1940题排序数组之间的最长公共子序列，LeetCode1143-最长公共子序列-代码随想录11.29，DP最长公共子序列详细版本(LCS)，【动态规划】最长公共子序列 I，动态规划 最长公共子串 全网最详讲解教程![45abc0b0f39ffd415de9b4ad10d440616a639e83.jpg_100w_100h_1c.png_57w_57h_1c.png][]https://www.bilibili.com/video/BV1S3411e7C8/?spm\_id\_from=333.337.search-card.all.click&vd\_source=eb072ba6b610daa77b0adfe79fcc5879][bilibili_-_ _ 16998_ 66_ 638_ 491_ 506_ 150_ _ 81895507389_bili_ _ _5._ LCS_LCS_ _06_dp-_-_ - _ Longest Common Subsequence - Dynamic Programming_LeetCode1940_LeetCode1143-_-_11.29_DP_LCS_ I_ _ _45abc0b0f39ffd415de9b4ad10d440616a639e83.jpg_100w_100h_1c.png_57w_57h_1c.png_https_www.bilibili.com_video_BV1S3411e7C8_spm_id_from_333.337.search-card.all.click_vd_source_eb072ba6b610daa77b0adfe79fcc5879]

## 第 3 题：[迷宫与陷阱][Link 2] ##

## 第 4 题：[送礼物][Link 3] ##

[Link 1]: https://www.lanqiao.cn/problems/149/learning/?page=2&first_category_id=1&sort=students_count&tags=2020
[3a2accc3e1384faf90dd7443814b6403.png]: https://img-blog.csdnimg.cn/3a2accc3e1384faf90dd7443814b6403.png
[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[19 _-CSDN_ 1 _ 2 _ 3 _ 4 _ _favicon32.ico_https_blog.csdn.net_m0_55858611_article_details_129701723_spm_1001.2014.3001.5501]: https://blog.csdn.net/m0_55858611/article/details/129701723?spm=1001.2014.3001.5501
[LCS_dp]: https://www.lanqiao.cn/problems/1030/learning/?page=2&first_category_id=1&sort=students_count&tags=2020
[afb62ae276bd480b96839975ffe2ad2e.png]: https://img-blog.csdnimg.cn/afb62ae276bd480b96839975ffe2ad2e.png
[icon-default.png_t_N2N8]: https://csdnimg.cn/release/blog_editor_html/release2.2.4/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N2N8
[icon-default.png_t_N2N8_icon-default.png_t_N2N8_https_leetcode.cn_problems_longest-common-subsequence]: https://leetcode.cn/problems/longest-common-subsequence/
[45abc0b0f39ffd415de9b4ad10d440616a639e83.jpg_100w_100h_1c.png_57w_57h_1c.png]: https://i1.hdslb.com/bfs/archive/45abc0b0f39ffd415de9b4ad10d440616a639e83.jpg@100w_100h_1c.png@57w_57h_1c.png
[bilibili_-_ _ 16998_ 66_ 638_ 491_ 506_ 150_ _ 81895507389_bili_ _ _5._ LCS_LCS_ _06_dp-_-_ - _ Longest Common Subsequence - Dynamic Programming_LeetCode1940_LeetCode1143-_-_11.29_DP_LCS_ I_ _ _45abc0b0f39ffd415de9b4ad10d440616a639e83.jpg_100w_100h_1c.png_57w_57h_1c.png_https_www.bilibili.com_video_BV1S3411e7C8_spm_id_from_333.337.search-card.all.click_vd_source_eb072ba6b610daa77b0adfe79fcc5879]: https://www.bilibili.com/video/BV1S3411e7C8/?spm_id_from=333.337.search-card.all.click&vd_source=eb072ba6b610daa77b0adfe79fcc5879
[Link 2]: https://www.lanqiao.cn/problems/229/learning/?page=2&first_category_id=1&sort=students_count&tags=2018
[Link 3]: https://www.lanqiao.cn/problems/1416/learning/?page=1&first_category_id=1&sort=students_count&tags=ST%E8%A1%A8