第十四届蓝桥杯三月真题刷题训练——第 23 天
目录
第 1 题:长草
题目描述
输入描述
输出描述
输入输出样例
运行限制
代码:
思路:
第 2 题:蓝肽子序列_LCS_最长公共子序列dp问题
题目描述
输入描述
输出描述
输入输出样例
运行限制
代码:
思路:
第 3 题:迷宫与陷阱
第 4 题:送礼物
第 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();}}
}
思路:
这题没啥好讲的,裸bfs板子,跟day19的灌溉一模一样
第十四届蓝桥杯三月真题刷题训练——第 19 天_小羊不会飞的博客-CSDN博客第 1 题:灌溉第 2 题:小朋友崇拜圈第 3 题:括号序列第 4 题:砍竹子 题解链接:砍竹子题解
https://blog.csdn.net/m0_55858611/article/details/129701723?spm=1001.2014.3001.5501
第 2 题:蓝肽子序列_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();}
}
思路:
这道题目考察两个点:
(1)字符串切割(存储每个以大写字母为开头的单词)
(2)最长公共子序列问题(LCS)
- 最长公共子序列我们需要分别遍历字符串S1和字符串S2
- 遍历比较的时候只会出现两种情况:字符串相等或字符串不等
- 对应这两种状态分别给出两种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有类似的题目:
力扣
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,动态规划 最长公共子串 全网最详讲解教程
https://www.bilibili.com/video/BV1S3411e7C8/?spm_id_from=333.337.search-card.all.click&vd_source=eb072ba6b610daa77b0adfe79fcc5879
第 3 题:迷宫与陷阱
第 4 题:送礼物
相关文章:

第十四届蓝桥杯三月真题刷题训练——第 23 天
目录 第 1 题:长草 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码: 思路: 第 2 题:蓝肽子序列_LCS_最长公共子序列dp问题 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码: 思路&am…...

基于springboot实现医院信息管理系统【源码+论文】
基于springboot实现医院信管系统演示开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包…...
CODESYS增量式PID功能块(ST完整源代码)
增量式PID的详细算法公式和博途源代码,请参看下面的文章链接: 博途1200/1500PLC增量式PID算法(详细SCL代码)_博图scl语言pid增量编码器_RXXW_Dor的博客-CSDN博客SMART200PLC增量式PID可以参看下面这篇博文,文章里有完整的增量式PID算法公式,这里不在赘述西门子SMARTPLC增量…...

代码质量提升,代码扫描 review 之 Codacy 工具使用
目录一、什么是Codacy二、GitHub 上使用 Codacy三、Codacy上导入GitHub项目一、什么是Codacy Codacy 是用于代码 review 检测(即代码审查)的工具,目前支持对40多种编程语言检测,如 c、c、c#、java 、python、javascript 等。 Codacy 可用于 GitHub 和 …...
Centos Linux 正确安装 Redis 的方式
官方文档 Getting started with Redis | Redis 第一步 、下载源代码 源代码的下载方式有很多种,可以去源代码仓库下载,或者使用下面的命令下载 wget https://download.redis.io/redis-stable.tar.gz 第二步 、编译代码 tar -xzvf redis-stable.tar.…...
C++Primer第五版【阅读笔记】
CPrimer第五版 阅读笔记 第1章开始1.1 编写一个简单的C程序1.1.1 编译、运行程序1.2 初识输入输出第1章开始 学习一门新的程序设计语言的最好方法就是练习编写程序。 1.1 编写一个简单的C程序 每个C程序都包含一个或多个函数,其中一个必须命名为 main,…...

ERD Online 4.0.11 在线数据库建模、元数据协作平台(免费、私有部署)
ERD Online 是全球第一个开源、免费在线数据建模、元数据管理平台。提供简单易用的元数据设计、关系图设计、SQL查询等功能,辅以版本、导入、导出、数据源、SQL解析、审计、团队协作等功能、方便我们快速、安全的管理数据库中的元数据。 4.0.11 ❝ :memo: fix(erd):…...

3.数组算法、动态规划
文章目录数组算法1.数组表示2.基本操作3.插入操作算法实例1实例2输出3.删除操作算法实例1输出4.搜索操作算法实例2输出5.更新操作算法实3例输出2.动态规划对照实例1数组算法 Array是一个容器,可以容纳固定数量的项目,这些项目应该是相同的类型。大多数数…...

项目管理工具哪个好?最新排名
项目管理工具当下已经成为项目团队的重要榜首,一款合适好用的项目管理工具可以帮助处理很多机械化工作,将管理者更多精力投入到更有价值的工作中,还可以帮助团队组织和计划项目,跟踪进度,处理预算和协作。该如何挑选帮…...

650. 只有两个键的键盘——【Leetcode每日一题】
650. 只有两个键的键盘 最初记事本上只有一个字符 A 。你每次可以对这个记事本进行两种操作: Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。Paste(粘贴)…...

【平常心无焦虑探讨】未来谁将被淘汰—在日常网络安全工作中使用GPT的感受
作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。所以可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。…...

【C语言】深度理解指针(下)
一. 前言💎昨晚整理博客时突然发现指针还少了一篇没写,今天就顺便来补一补。上回书说到,emmm忘记了,没事,我们直接进入本期的内容:本期我们带来了几道指针相关笔试题的解析,还算是相对比较轻松的。话不多说…...

【树与二叉树】树与二叉树的概念及结构--详解介绍
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录1.树概念及结构1.1 树…...

Spring Boot集成RocketMQ实现普通、延时、事务消息发送接收、PULL消费模式及开启ACL | Spring Cloud 30
一、前言 在前面我们通过以下章节对RocketMQ有了基础的了解: docker-compose 搭建RocketMQ 5.1.0 集群(双主双从模式) | Spring Cloud 28 docker-compose 搭建RocketMQ 5.1.0 集群开启ACL权限控制 | Spring Cloud 29 现在开始我们正式学习…...

人人都能看懂的Spring源码解析,Spring如何解决循环依赖
人人都能看懂的Spring源码解析,Spring如何解决循环依赖原理解析什么是循环依赖循环依赖会有什么问题?如何解决循环依赖问题的根本原因如何解决为什么需要三级缓存?Spring的三级缓存源码走读Spring的三级缓存提前暴露getSingleton方法总结往期…...

Linux上搭建Discuz论坛
一.准备工作 1.下载php*,mariadb-server 2.上传Discuz3.5压缩包并解压 二.搭建过程 基于redhat 9 版本和Discuz3.5,php8.0,mariadb10.5演示 一.准备工作 1.下载php*,mariadb-server [rootredhat9 aaa]# yum install -y php*…...

【蓝桥杯专题】 树状数组(C++ | 洛谷 | acwing | 蓝桥)
菜狗现在才开始备战蓝桥杯QAQ 文章目录【蓝桥杯专题】 (C | 洛谷 | acwing | 蓝桥)什么是线段数组??1264. 动态求连续区间和数星星线段树AcWing 1270. 数列区间最大值PPPPPPP【蓝桥杯专题】 (C | 洛谷 | acwing | 蓝桥) 什么是…...

QCefView编译配置(Windows-MSVC)(11)
QCefView编译配置(Windows-MSVC) 文章目录QCefView编译配置(Windows-MSVC)1、概述2、准备工作3、添加环境变量4、更换cef源码版本5、CMake构建6、Visual Studio编译7、安装编译后的文件8、验证编译结果更多精彩内容👉个…...
Token原理
Q:分布式场景下如何生成token以及使用token的流程: 在分布式场景下,可以采用以下方式生成 token 和进行权限认证: 1. 生成 token: 使用JWT(JSON Web Token)生成 token。JWT 是一种基于 JSON …...

③【Java组】蓝桥杯省赛真题 持续更新中...
个人简介:Java领域新星创作者;阿里云技术博主、星级博主、专家博主;正在Java学习的路上摸爬滚打,记录学习的过程~ 个人主页:.29.的博客 学习社区:进去逛一逛~ 蓝桥杯真题--持续更新中...一、错误票据题目描…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
智能职业发展系统:AI驱动的职业规划平台技术解析
智能职业发展系统:AI驱动的职业规划平台技术解析 引言:数字时代的职业革命 在当今瞬息万变的就业市场中,传统的职业规划方法已无法满足个人和企业的需求。据统计,全球每年有超过2亿人面临职业转型困境,而企业也因此遭…...

如何做好一份技术文档?从规划到实践的完整指南
如何做好一份技术文档?从规划到实践的完整指南 🌟 嗨,我是IRpickstars! 🌌 总有一行代码,能点亮万千星辰。 🔍 在技术的宇宙中,我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...
FTXUI::Dom 模块
DOM 模块定义了分层的 FTXUI::Element 树,可用于构建复杂的终端界面,支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...

若依项目部署--传统架构--未完待续
若依项目介绍 项目源码获取 #Git工具下载 dnf -y install git #若依项目获取 git clone https://gitee.com/y_project/RuoYi-Vue.git项目背景 随着企业信息化需求的增加,传统开发模式存在效率低,重复劳动多等问题。若依项目通过整合主流技术框架&…...