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

AcWing 蓝桥杯集训·每日一题2025·密接牛追踪2

密接牛追踪2

农夫约翰有 N 头奶牛排成一排,从左到右依次编号为 1∼N。

不幸的是,有一种传染病正在蔓延。

最开始时,只有一部分奶牛受到感染。

每经过一个晚上,受感染的牛就会将病毒传染给它左右两侧的牛(如果有的话)。

一旦奶牛被感染,它就会一直被感染,无法自愈。

给定一个经过若干个夜晚后的奶牛的整体状态,其中哪些奶牛已经被感染,哪些奶牛尚未被感染统统已知。

请你计算,最开始时就受到感染的奶牛的最小可能数量。

输入格式

第一行包含整数 N。
第二行包含一个长度为 N 的 01序列,用来表示给定的奶牛的整体状态,其中第 i个字符如果是 1 则表示第 i 头奶牛已经被感染,如果是 0 则表示第 i 头奶牛尚未被感染。

输出格式

一个整数,表示最开始时就受到感染的奶牛的最小可能数量。

输入样例

5
11111

输出样例

4

题意 : 给定01字符串, 求最开始时, 01串中含1的数量,每天01串中的1都会扩散扩散方式如下:

  • 每天 1 会向俩端扩展,知道全部 0 变为 1 为止

解题思路:

将扩散转换为区间问题, 查找最大天数, 因为每个1 每天的扩展区间为 2r + 1 其中 r 为天数, 可以用一个变量cnt统计出每段去间1的数量, 然后套用公式计算出最大天数, 根据最大天数, 计算该段 1 的连续区间最少的 1 的数量。

AC Code

// Problem: 密接牛追踪2
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5441/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
typedef long long ll; // 确保 ll 在使用前被定义
using namespace std;
using i64 = long long;
#define f for(int i = 0; i < n;++i)
#define ff for(int i = 1; i <= n;++i)
#define int long long 
#define pii pair<int,int>
#define In \ll n; \std::cin >> n;\

const int mod = 1e9 + 7, N = 1e7;void solve(){In; std::string s;std::cin >> s;int ans = 0;std::vector<pii> ss;// 遍历每段区间, 将每段区间记录for(int i = 0, j = 0; i < n; i = j) {while(s[i] == '0') i++;j = i;while(j < n and s[j] == '1') j++;if(j > i) ss.push_back({i , j - 1});}if(ss.size() == 0) {std::cout << 0 << "\n";return ;}// 计算最小天数int R = 1e9;for(auto &[l , r] : ss) {// 最后和首位要特判if(l == 0 or r == n - 1) R = std::min(r - l + 1, R);else R = min((r - l + 2) / 2, R);}// 最后根据答案计算最小感染牛for(auto &[l, r] : ss) {ans += (r - l) / (2 * R - 1) + 1;}std::cout << ans << "\n";
}signed main(){std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);ll T = 1;//std::cin >> T;for(int i = 1; i <= T; ++i) solve();
}

相关文章:

AcWing 蓝桥杯集训·每日一题2025·密接牛追踪2

密接牛追踪2 农夫约翰有 N 头奶牛排成一排&#xff0c;从左到右依次编号为 1∼N。 不幸的是&#xff0c;有一种传染病正在蔓延。 最开始时&#xff0c;只有一部分奶牛受到感染。 每经过一个晚上&#xff0c;受感染的牛就会将病毒传染给它左右两侧的牛&#xff08;如果有的话…...

LeetCode 每日一题 2025/2/24-2025/3/2

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/24 1656. 设计有序流2/25 2502. 设计内存分配器2/26 1472. 设计浏览器历史记录2/27 2296. 设计一个文本编辑器2/28 2353. 设计食物评分系统3/1 131. 分割回文串3/2 132. …...

TeX Live 2025 最新版安装与中文环境配置全教程(Windows/Mac/Linux)

一、软件定位与特性 TeX Live 是由国际TeX用户组&#xff08;TUG&#xff09;维护的跨平台专业排版系统&#xff0c;支持LaTeX、XeLaTeX等多种排版引擎&#xff0c;广泛应用于学术论文、书籍出版等领域。2025版核心升级&#xff1a; 智能编译&#xff1a;自动检测编码错误并提…...

Android实现漂亮的波纹动画

Android实现漂亮的波纹动画 本文章讲述如何使用二维画布canvas和camera、矩阵实现二、三维波纹动画效果&#xff08;波纹大小变化、画笔透明度变化、画笔粗细变化&#xff09; 一、UI界面 界面主要分为三部分 第一部分&#xff1a;输入框&#xff0c;根据输入x轴、Y轴、Z轴倾…...

JAVA学习笔记038——bean的概念和常见注解标注

什么是bean? Bean 就是 被 Spring 管理的对象&#xff0c;就像工厂流水线上生产的“标准产品”。这些对象不是你自己 new 出来的&#xff0c;而是由 Spring 容器&#xff08;一个超级工厂&#xff09;帮你创建、组装、管理。 由 Component、Service、Controller 等注解标记的…...

自然语言处理NLP入门 -- 第十节NLP 实战项目 2: 简单的聊天机器人

一、为什么要做聊天机器人&#xff1f; 在互联网时代&#xff0c;我们日常接触到的“在线客服”“自动问答”等&#xff0c;大多是以聊天机器人的形式出现。它能帮我们快速回复常见问题&#xff0c;让用户获得及时的帮助&#xff0c;并在一定程度上减少人工客服的压力。 同时&…...

【网络安全 | 渗透工具】小程序反编译分析源码 | 图文教程

未经许可,禁止转载。 本文仅供学习使用,严禁用于非法渗透测试,笔者不承担任何责任。 文章目录 1、下载Proxifier2、下载反编译工具unveilr3、寻找小程序文件包4、对文件包进行反编译5、对源码进行分析6、渗透思路6.1、查找敏感信息泄露6.2、解析加解密逻辑6.3、枚举 API 接口…...

uniapp 系统学习,从入门到实战(六)—— 样式与布局

全篇大概 4700 字(含代码)&#xff0c;建议阅读时间 30min &#x1f4da; 目录 Flex 布局在 UniApp 中的应用响应式设计与适配多端使用 SCSS 提升样式开发效率实战案例演示总结 1. Flex 布局在 UniApp 中的应用 1.1 基础布局实现 通过 display: flex 快速构建弹性容器&#…...

‘ts-node‘ 不是内部或外部命令,也不是可运行的程序

新建一个test.ts文件 let message: string = Hello World; console.log(message);如果没有任何配置的前提下,会报错’ts-node’ 不是内部或外部命令,也不是可运行的程序。 此时需要安装一下ts-node。 npm install...

mysql 全方位安装教程

下载 MySQL 【官网下载地址】 注意要选择较大的哪个安装包&#xff0c;小的安装包是一个安装器。 我们不用登录&#xff0c;直接下载 直接运行下载好的安装包 MySQL如果是 安装包安装, 可以图形化界面自主配置 如果是压缩包解压, 可以配置 配置文件, 可以解压安装到指定的…...

22-接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 方法一&#xff1a;双指针法 思路 使用两个指针 left 和 right 分别指向数组的两端&#xff0c;同时记录左边的最大高度 leftMax 和右边的最大高度 rig…...

使用Spring Boot与达梦数据库(DM)进行多数据源配置及MyBatis Plus集成

使用Spring Boot与达梦数据库(DM)进行多数据源配置及MyBatis Plus集成 在现代企业级应用开发中&#xff0c;处理多个数据源是一个常见的需求。本文将详细介绍如何使用Spring Boot结合达梦数据库&#xff08;DM&#xff09;&#xff0c;并通过MyBatis Plus来简化数据库操作&…...

leetcode28 找出字符串第一个匹配值的下标 KMP算法

KMP 算法——快速的从主串中找到模式串 当出现字符串不匹配时&#xff0c;可以知道一部分之前已经匹配的文本内容&#xff0c;可以利用这些信息避免从头再去做匹配了。 KMP 算法 比较指针不回溯&#xff0c;仅仅是后移模式串。 每次不匹配的时候&#xff0c;找之前已匹配部分…...

【Bug】natten:安装报错(临近注意力机制的高效cuda内核实现)

正常安装natten报错 pip install natten 报错 可以尝试使用以下网站进行安装 https://shi-labs.com/natten/ 可以根据自己的cuda与pytorch版本进行安装 之间复制命令即可&#xff0c;不需要进行任何修改...

AI 实战2 - face -detect

人脸检测 环境安装源设置conda 环境安装依赖库 概述数据集wider_face转yolo环境依赖标注信息格式转换图片处理生成 train.txt 文件 数据集展示数据集加载和处理 参考文章 环境 安装源设置 conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/f…...

Spring Boot 项目开发流程全解析

目录 引言 一、开发环境准备 二、创建项目 三、项目结构 四、开发业务逻辑 1.创建实体类&#xff1a; 2.创建数据访问层&#xff08;DAO&#xff09;&#xff1a; 3.创建服务层&#xff08;Service&#xff09;&#xff1a; 4.创建控制器层&#xff08;Controller&…...

从Java到MySQL8源码:深入解析PreparedStatement参数绑定与执行机制

引言 在数据库开发中&#xff0c;PreparedStatement&#xff08;预处理语句&#xff09;是防止SQL注入、提升性能的重要工具。它通过分离SQL结构与参数值&#xff0c;不仅增强了安全性&#xff0c;还能利用预编译优化执行效率。本文将从Java JDBC驱动和MySQL 8源码的双重视角&…...

mysql的主从同步

1、异步复制&#xff1a;这是MySQL默认的复制模式。在这种模式下&#xff0c;主库在执行完客户端提交的事务后会立即将结果返回给客户端&#xff0c;并不关心从库是否已经接收并处理。这种模式的优点是实现简单&#xff0c;但缺点是如果主库崩溃&#xff0c;已经提交的事务可能…...

工程化与框架系列(10)--微前端架构

微前端架构 &#x1f3d7;️ 微前端是一种将前端应用分解成更小、更易管理的独立部分的架构模式。本文将详细介绍微前端的核心概念、实现方案和最佳实践。 微前端概述 &#x1f31f; &#x1f4a1; 小知识&#xff1a;微前端的核心理念是将前端应用分解成一系列独立部署、松耦…...

【3天快速入门WPF】11-附加属性

目录 1. 步骤1:定义附加属性2. 示例代码3. 步骤2:在XAML中使用附加属性3.1. 示例代码4. 步骤3:扩展使用场景4.1. 示例代码5. 总结上一篇讲到了依赖属性,本篇主要想说一下附加属性。 在WPF中,附加属性(Attached Property)是一种特殊的依赖属性,允许你在不属于某个类的控…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...

表单设计器拖拽对象时添加属性

背景&#xff1a;因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...