当前位置：首页 > news >正文

【蓝桥杯】水质检测

news 来源：原创 2025/6/28 17:43:45

水质检测

题目描述

小明需要在一条 $\times n$ 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 $A$ 和 $B$ 连通， $B$ 和 $C$ 连通，那么 $A$ 和 $C$ 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

输入格式

输入共两行，表示一个 $\times n$ 的河床。

每行一个长度为 $n$ 的字符串，仅包含 # 和 .，其中 # 表示已经存在的检测器，. 表示空白。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例 #1

输入 #1

##.....#
#.#.#...

输出 #1

说明/提示

样例说明

其中一种方案：

###....#
#.######

增加了 5 个检测器。

评测用例规模与约定

对于 $100\%$ 的评测用例，保证 $\leq 1000000$ 。

P12135 [蓝桥杯 2025 省 B] 水质检测

【思路分析】

状态表示

f[i][j] 代表第 i 行（i 取值为 0 或 1，分别对应第一行和第二行）使得到第 j 个位置的所有检测器连通的最小安装机器数量。

状态计算

状态转移方程

每个位置的状态可以从同一行的上一个位置或者另一行的上一个位置转移过来，因此状态转移方程如下：

f[0][j] = Math.min(f[0][j - 1] + a[0][j], f[1][j - 1] + a[1][j] + a[0][j])
f[1][j] = Math.min(f[1][j - 1] + a[1][j], f[0][j - 1] + a[1][j] + a[0][j])

import java.io.*;
import java.util.*;
public class Main {// 定义数组的最大长度，考虑到 n 的最大值为 1000000，这里设置为 1000010static final int N = 1000010;// 是否遇见了第一个机器的标志static boolean isFirstMachine;// f 数组用于存储动态规划的状态static int[][] f = new int[2][N];// a 数组用于预处理每个位置是否需要新增检测器，需要为 1，不需要为 0static int[][] a = new int[2][N];// 最后一个机器的位置static int lastMachine = 0;public static void main(String[] args) throws Exception {// 使用 BufferedReader 读取输入，提高读取效率BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String str1 = br.readLine();String str2 = br.readLine();// 获取输入字符串的长度，即河床的列数int n = str1.length();// 预处理所有位置是否需要新增一个机器for(int i = 0; i < n; i++) {// 第一行的第 i 个位置如果是机器，第一行的下一个位置就不需要填充机器if(str1.charAt(i) == '#') {a[0][i + 1] = 0;// 更新最后一个机器的位置lastMachine = i + 1;} else if(str1.charAt(i) == '.') {a[0][i + 1] = 1;}// 第二行的第 i 个位置如果是机器，第二行的下一个位置就不需要填充机器if(str2.charAt(i) == '#') {a[1][i + 1] = 0;// 更新最后一个机器的位置lastMachine = i + 1;} else if(str2.charAt(i) == '.') {a[1][i + 1] = 1;}}// 状态计算for(int i = 1; i <= lastMachine; i++) {// 找到第一个机器的位置if(isFirstMachine == false && (a[0][i] == 0 || a[1][i] == 0)) {isFirstMachine = true;}if(isFirstMachine) {// 状态转移方程，计算第 0 行第 i 个位置的最小安装机器数量f[0][i] = Math.min(f[0][i - 1] + a[0][i], f[1][i - 1] + a[1][i] + a[0][i]);// 状态转移方程，计算第 1 行第 i 个位置的最小安装机器数量f[1][i] = Math.min(f[1][i - 1] + a[1][i], f[0][i - 1] + a[1][i] + a[0][i]);}}// 输出结果，取第 0 行和第 1 行最后一个机器位置的最小安装机器数量System.out.println(Math.min(f[0][lastMachine], f[1][lastMachine]));// 关闭 BufferedReaderbr.close();} 
}

【蓝桥杯】水质检测

水质检测题目描述小明需要在一条 2 n 2 \times n 2n 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 A A A 和 B B B 连通…...

编程日记 2025/6/28 17:43:45

【晶振】晶振的工作原理及其与单片机关系

晶振（晶体振荡器）是电子设备中常见的元件，其核心功能是提供稳定的时钟信号，而单片机（MCU）依赖这一信号来同步内部操作。以下是晶振的工作原理及其与单片机关系的详细说明：一、晶振的工作原理压电效应与谐振晶振的核心是石英晶体，利用其压电效应：当在晶体两端施加电…...

编程日记 2025/6/28 16:51:04

配置 C/C++ 语言智能感知（IntelliSense）的 c_cpp_properties.json 文件内容

配置 C/C 语言智能感知（IntelliSense）的 c_cpp_properties.json 文件内容 {"configurations": [{"name": "Linux","includePath": ["${workspaceFolder}/**","/opt/ros/humble/include/**&quo…...

编程日记 2025/6/28 16:42:28

Postgresql源码（143）统计信息基础知识（带实例）

概念与总结高频值（Most Common Values, MCV） 存储在 most_common_vals 中。每个高频值的频率通过 most_common_freqs 单独记录（例如 0.010966667 等）。MCV 用于优化等值查询（如 poid 33）&…...

编程日记 2025/5/14 17:54:50

【含文档+PPT+源码】基于SpringBoot+vue的疫苗接种系统的设计与实现

项目介绍本课程演示的是一款基于SpringBootvue的疫苗接种系统的设计与实现，主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含：项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署运行本套系…...

编程日记 2025/5/4 8:03:07

解决 Dart Sass 的旧 JS API 弃用警告的详细步骤和解决方案

以下是解决 Dart Sass 的旧 JS API 弃用警告的详细步骤和解决方案： 错误原因 Dart Sass 1.x 版本中使用的旧 JavaScript API（如 sass.render() 或 sass.compile() 的旧调用方式）将在 2.0.0 版本中被移除。需迁移到新 API 以避免未来报错。…...

编程日记 2025/6/26 19:11:43

Concepts (C++20)

C20 Concepts Concepts 是 C20 引入的核心特性，用于显式约束模板参数，提升代码可读性和错误提示。以下通过代码示例和原理分步骤解析其用法。 1. 基本概念目标：显式声明模板参数必须满足的条件。优势：替代复杂的 SFINAE 和 ena…...

编程日记 2025/5/20 11:14:19

CVE-2024-23897-Jenkins 2.441之前版本存在任意文件读取漏洞

1.漏洞介绍 Jenkins 2.441及更早版本，以及LTS 2.426.2及更早版本没有禁用其CLI命令解析器的一个功能，该功能会将参数中字符后跟的文件路径替换为该文件的内容，允许未经身份验证的攻击者读取Jenkins控制器文件系统上的任意文件。 2.poc利用下…...

编程日记 2025/6/27 2:25:20

利用 SSE 实现文字吐字效果：技术与实践

利用 SSE 实现文字吐字效果：技术与实践引言在现代 Web 应用开发中，实时交互功能愈发重要。例如，在线聊天、实时数据监控、游戏中的实时更新等场景，都需要服务器能够及时将数据推送给客户端。传统的请求 - 响应模式在处理实时性要求较高的场景时显得力不从心，而 Server…...

编程日记 2025/6/27 17:39:02

离线部署kubernetes

麒麟Linux服务器 AMR架构 🧰 离线部署 Kubernetes v1.25.9（麒麟系统 Docker） 一、验证Docker部署状态 ‌检查Docker服务运行状态‌ systemctl status docker 预期输出应显示 Active: active (running)，表明服务已启动‌18。 ‌…...

编程日记 2025/6/26 19:58:15

题目链接 #include<bits/stdc.h> using namespace std; using lllong long;int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n; cin>>n;vector<ll>a(n1);ll res0;for(int i1;i<n;i) cin>>a[i],resa[i];ll ans0;for(int i32;i>…...

编程日记 2025/5/8 2:37:37

第53讲农学科研中的AI伦理与可解释性——探索SHAP值、LIME等可解释工具与科研可信性建设之道

目录一、为什么农学科研中需要“可解释AI”？ ✅ 场景示例：二、常见可解释AI工具介绍 1. SHAP（SHapley Additive exPlanations） 2. LIME（Local Interpretable Model-agnostic Explanations）三、AI伦理问题在农学中的体现 🧭 公平性与偏见 🔐 数据隐私 🤖…...

编程日记 2025/5/8 17:56:14

《Python3网络爬虫开发实战（第二版）》配套案例 spa6

Scrape | Moviehttps://spa6.scrape.center/ 请求影片列表api时，不仅有分页参数，还多了一个token，通过重发请求发现token有时间限制，所以得逆向token的生成代码。通过xhr断点定位到接口请求位置刷新页面或者点翻页按钮&#x…...

编程日记 2025/6/27 7:06:17

面试题：Java程序CPU 100%问题排查指南

Java程序CPU 100%问题排查指南当Java程序出现CPU使用率达到100%的情况时，通常意味着程序存在性能瓶颈或无限循环等问题。以下是系统化的排查方法和解决方案： 1. 快速定位问题线程使用top命令初步定位 top -H -p <java_pid> # 查看Java进程的所有线程CPU占用线程…...

编程日记 2025/5/2 23:09:31

YOLOv12的注意力机制革新与实时检测性能分析——基于架构优化与历史版本对比

目录一、摘要二、引言三、YOLO架构的技术演变四、YOLOv12的架构设计主干网特征提取头部特征融合和目标检测五、YOLOv12的架构创新区域注意力模块残差高效层聚合网络（R-ELAN） 其他改进和效率提升六、YOLOv12 的基准评估延迟与精度…...

编程日记 2025/6/27 16:04:32

Ollama工具调用（Tool Calls）业务应用案例

场景：电商客服自动处理退货请求业务需求：用户通过聊天界面申请退货，模型需调用外部工具验证订单状态、触发退货流程，并返回处理结果。 1. 定义工具列表在请求中声明模型可调用的工具（函数）及其参数格式…...

编程日记 2025/6/2 22:38:30

输入捕获模式测频率

前提工作： PA6、PA0通过跳线相连，PA6测试PA0的输出频率本来只有下列函数，改变占空比但是我们需要测试频率，需要动态改变频率。 void PWM_SetCompare1(uint16_t Compare) {TIM_SetCompare1(TIM2, Compare); //设置CCR1的值 }…...

编程日记 2025/5/31 8:12:52

【Vue3 实战】插槽封装与懒加载

一、为什么需要插槽？从一个面板组件说起在电商首页开发中，经常遇到这样的场景： 「新鲜好物」「人气推荐」同样类型模块都需要相同的标题栏，但内容区布局不同这时候，插槽（Slot）就像一个「内容…...

编程日记 2025/6/26 23:19:54

Matlab 复合多层结构的隔声研究

应用转移矩阵的方法,就平面声波垂直入射的情况,对具有周期结构的无限大多层板的隔声特性进行了理论分析,并对结构不同的多层板的隔声特性进行了数值模拟.理论分析和数值模拟表明:与通常隔声用的单层或双层板相比,在保持面密度不变的条件下，采用多层板结构能够在某些…...

编程日记 2025/6/1 16:18:19

vulkanscenegraph显示倾斜模型(6)-帧循环

前言上一部分，通过十个章节的内容，对视景器的初始化与准备工作进行了系统性的剖析。本章将在该基础上，探讨vsg中的帧循环机制，主要包含前进到下一帧、事件处理、更新、记录与提交、呈现五个部分，同时整个过程包含了复…...

编程日记 2025/5/26 14:53:37

k8s 1.26版部署

环境规划： pod网段：10.244.0.0/16 service网段：10.10.0.0/16 注意： pod和service网段不可冲突，如果冲突会导致K8S集群安装失败。容器运行时本次使用containerd。主机规划：一、初始化系统（所有节点） 1. 主机名定义以及解析 2. 关闭防火墙 3. 关闭selinux 4. 时间同…...

编程日记 2025/5/27 5:17:37

Android之AI自动化测试--Midscene

文章目录前言一、准备工作1.安装2.准备 API Key3.安装 adb4.连接设备二、yaml格式自动化脚本1. 脚本案例2.执行结果三、文件结构变化android 部分前言字节 Web Infra团队官宣Midscene 从 v0.15 开始支持 Android 自动化测试，本篇文章介绍yaml方式的Android自动…...

编程日记 2025/6/27 17:38:02

Cadence 建立复合原理图封装时怎么切换页面

1.在当前页面A绘制完成，若要切换到下一页面B。怎么操作呢？ 见下面： CTRLN,切换到下一部分(CTRLB,切换到前一部分)继续放线以及管脚即：此时在原理图库的A部分此时按 CTRLN,切换到下一B部分...

编程日记 2025/5/31 3:27:37

Sharding-JDBC 系列专题 - 第八篇：数据治理与高级功能

Sharding-JDBC 系列专题 - 第八篇：数据治理与高级功能本系列专题旨在帮助开发者全面掌握 Sharding-JDBC，一个轻量级的分布式数据库中间件。本篇作为系列的第八篇文章，将重点探讨数据治理（Data Governance）和高级功能，包括数据加密、影子表、SQL 审计以及 ShardingSp…...

编程日记 2025/4/28 18:00:12

今日行情明日机会——20250424

指数依然是震荡走势，接下来两天调整的概率较大 2025年4月24日涨停主要行业方向分析一、主要方向化工（新能源材料） • 涨停家数：8家（最强方向）。 • 代表标的： ◦ 中欣氟材（3连板…...

编程日记 2025/6/27 2:12:42

Kubernetes 常用运维命令整理

目录 Kubernetes 常用运维命令整理一、集群管理二、Pod 和容器管理三、Deployment 和应用管理四、Service 和网络管理五、存储管理六、ConfigMap 和 Secret 管理七、资源使用与监控八、调度和容错九、Role 和权限管理十、清理资源总结 Kubernetes 常用运维命令整理 Kubernete…...

编程日记 2025/6/27 14:50:25

【Python爬虫基础篇】--4.Selenium入门详细教程

先解释：Selenium：n.硒；硒元素目录 1.Selenium--简介 2.Selenium--原理 3.Selenium--环境搭建 4.Selenium--简单案例 5.Selenium--定位方式 6.Selenium--常用方法 6.1.控制操作 6.2.鼠标操作 6.3.键盘操作 6.4.获取断言信息 6.5.…...

编程日记 2025/6/27 7:06:17

基于Vulkan Specialization Constants的材质变体系统

材质变体所谓材质变体，指的是一份材质代码文件，最终对应的是多份运行时gpu程序。比如，shader代码里面有开关或者选项，不同的组合对应不同的最终gpu program。那么，所有的这些组合对应的gpu program，可以统…...

编程日记 2025/6/27 20:46:11

Langchain+RAG+向量数据库

加载数据 import osimport lancedb from langchain_community.document_loaders import TextLoader from langchain_community.embeddings import BaichuanTextEmbeddings from langchain_community.vectorstores import LanceDB from langchain_core.output_parsers import St…...

编程日记 2025/6/28 6:37:04