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

贡献法:USACO 2021 December Contest Bronze:孤独的照片

Farmer John 最近购入了 N 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。

奶牛目前排成一排,Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。

然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。

在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。

给定奶牛的排列方式,请帮助 Farmer John 求出他会扔掉多少张孤独的照片。

如果两张照片以不同位置的奶牛开始或结束,则认为它们是不同的。

输入格式

输入的第一行包含 N。

输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛,则字符串的第 i 个字符为 G。否则,第 i 头奶牛是荷斯坦牛,该字符为 H

输出格式

输出 Farmer John 会扔掉的孤独的照片数量。

数据范围

3≤N≤5×105

输入样例:
5
GHGHG
输出样例:
3
样例解释

这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被 Farmer John 扔掉。

所有更长的子串(GHGHHGHG 和 GHGHG)都可以被接受。

可以通过 l 和 r 数组记录 每头牛左右两边有多少连续的不同种类的牛数量

然后孤独照片数量就是通过 l[i] 和 r[i] 分三类相加得出

找出当前这个牛的左边相邻的连续不同的牛 *  右边的相邻连续不同的牛 + 左边的不同牛的长度 - 1 + 右边不同的牛的长度 - 1

为什么左右两边的长度要减1,因为照片长度至少3,假如是 GHHHH,右边不同长度的牛为4,可方案为,GHH,GHHH,GHHHH,为3,需要减一。

AC code:

#include<bits/stdc++.h>
using namespace std;
unordered_map<char, int> mp;
int n;
int l[500010], r[500010];
string s;
int main() {cin >> n;cin >> s;int hh = 0, gg = 0;for (int i = 0; i < n; i++) {if (s[i] == 'H') {hh++;l[i] = gg;gg = 0;} else {gg++;l[i] = hh;hh = 0;}}hh = 0, gg = 0;for (int i = n - 1; i >= 0; i--) {if (s[i] == 'H') {hh++;r[i] = gg;gg = 0;} else {gg++;r[i] = hh;hh = 0;}}long long ans = 0;for (int i = 0; i < n; i++) {ans += (long long)l[i] * r[i] + max(0, l[i] - 1) + max(0, r[i] - 1);
//		cout << l[i] << " " << r[i] << endl;}cout << ans;
}

相关文章:

贡献法:USACO 2021 December Contest Bronze:孤独的照片

Farmer John 最近购入了 N 头新的奶牛&#xff0c;每头奶牛的品种是更赛牛&#xff08;Guernsey&#xff09;或荷斯坦牛&#xff08;Holstein&#xff09;之一。 奶牛目前排成一排&#xff0c;Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而&#xff0c;他…...

Java实现简单的通讯录

每日一言 泪眼问花花不语&#xff0c;乱红飞过秋千去。 —欧阳修- 简单的通讯录实现&#xff0c;跟写Java实现图书管理系统差不多&#xff0c;用到的知识也差不多&#xff0c;就当个小练习&#xff0c;练习一下写Java程序的手感。 Java实现图书管理系统 关于通讯录的代码都写…...

服务器数据恢复—raid5热备盘上线同步数据失败的如何恢复数据

服务器数据恢复环境&故障&分析&#xff1a; 一台存储上有一组由多块硬盘组建的raid5阵列&#xff0c;该raid5阵列中的一块硬盘掉线&#xff0c;热备盘自动上线同步数据的过程中&#xff0c;raid阵列中又有一块硬盘掉线&#xff0c;热备盘的数据同步被中断&#xff0c;r…...

探索C语言中的循环结构

循环结构是程序设计中一种重要的控制结构&#xff0c;它允许程序重复执行特定的代码块&#xff0c;直到满足某个条件为止。在C语言中&#xff0c;循环结构有多种形式&#xff0c;如for循环、while循环和do-while循环。本文将介绍C语言中的循环结构&#xff0c;并讨论它们的用法…...

数学建模-估计出租车的总数

文章目录 1、随机抽取的号码在总体的排序 1、随机抽取的号码在总体的排序 10个号码从小到大重新排列 [ x 0 , x ] [x_0, x] [x0​,x] 区间内全部整数值 ~ 总体 x 1 , x 2 , … , x 10 总体的一个样本 x_1, x_2, … , x_{10} ~ 总体的一个样本 x1​,x2​,…,x10​ 总体的一个样…...

设计模式在芯片验证中的应用——装饰器

一、装饰器模式 装饰器模式(Decorator)是一种结构化软件设计模式&#xff0c;它提供了一种通过向类对象添加行为来修改类对象的方法&#xff0c;而不会影响同一类的其它对象行为。该模式允许在不修改抽象类的情况下添加类功能。它从本质上允许基类代码对不可预见的修改具有前瞻…...

Python 查找并高亮PDF中的指定文本

在处理大量PDF文档时&#xff0c;有时我们需要快速找到特定的文本信息。本文将提供以下三个Python示例来帮助你在PDF文件中快速查找并高亮指定的文本。 查找并高亮PDF中所有的指定文本查找并高亮PDF某个区域内的指定文本使用正则表达式搜索指定文本并高亮 本文将用到国产第三方…...

LEETCODE LCS 03. 主题空间

题目描述如上&#xff0c;这个题主要运用了DFS的思想&#xff0c;同时走过的路径标记为6&#xff0c;即可在后续的遍历中过滤掉重复的元素&#xff0c;其他则类似边界条件的判断和题目条件的判断&#xff0c;求最大值&#xff0c;只需要一次遍历中累加对比每一次得即可。 模板&…...

【Spring Boot 源码学习】深入应用上下文初始化器实现

《Spring Boot 源码学习系列》 深入应用上下文初始化器实现 一、引言二、往期内容三、主要内容3.1 spring-boot 子模块中内置的实现类3.1.1 ConfigurationWarningsApplicationContextInitializer3.1.2 ContextIdApplicationContextInitializer3.1.3 DelegatingApplicationConte…...

【Docker】一文趣谈Docker

&#x1f3e1;浩泽学编程&#xff1a;个人主页 &#x1f525; 推荐专栏&#xff1a;《深入浅出SpringBoot》《java对AI的调用开发》 《RabbitMQ》《Spring》《SpringMVC》《项目实战》 &#x1f6f8;学无止境&#xff0c;不骄不躁&#xff0c;知行合一 文章目录 …...

代码随想录day19(2)二叉树:二叉树的最大深度(leetcode104)

题目要求&#xff1a;求出二叉树的最大深度 思路&#xff1a;首先要区分二叉树的高度与深度。二叉树的高度是任一结点到叶子结点的距离&#xff0c;而二叉树的深度指的是任一节点到根节点的距离&#xff08;从1开始&#xff09;。所以求高度使用后序遍历&#xff08;从下往上&…...

Lua中文语言编程源码-第五节,更改lcorolib.c协程库函数, 使Lua加载中文库关键词(与所有的基础库相关)

源码已经更新在CSDN的码库里&#xff1a; git clone https://gitcode.com/funsion/CLua.git 在src文件夹下的lcorolib.c协程库函数&#xff0c;Coroutine Library&#xff1a;表明这个C源文件实现了Lua的协程库&#xff08;Coroutine Library&#xff09;&#xff0c;即提供了…...

Docker学习之数据管理(超详解析)

Docker存储资源类型&#xff1a; 用户在使用 Docker 的过程中&#xff0c;势必需要查看容器内应用产生的数据&#xff0c;或者需要将容器内数据进行备份&#xff0c;甚至多个容器之间进行数据共享&#xff0c;这必然会涉及到容器的数据管理&#xff1a; &#xff08;1&#xff…...

FDTD液晶折射率各项异性表示方法

由于FDTD的数据都是沿坐标轴的&#xff0c;各向异性材料的参数也需要根据坐标轴来输入。 首先要了解坐标变换。 坐标变换 这里以二维坐标变化为例。 矢量下我们可以发现OP可在两个坐标系下分别表示 接下来将两个坐标相互关联&#xff0c;这里以Xb举例&#xff0c;Yb同理 注…...

RoketMQ主从搭建

vim /etc/hosts# IP与域名映射&#xff0c;端口看自己的#nameserver 192.168.126.132 rocketmq-nameserver1 192.168.126.133 rocketmq-nameserver2# 注意主从节点不在同一个主机上 #broker 192.168.126.132 rocketmq-master1 192.168.126.133 rocketmq-master2#broker 192.168…...

Linux网络瑞士军刀 nc(netcat)

1.命令简介 nc&#xff08;netcat&#xff09;是一个短小精悍、功能实用、简单可靠的网络工具&#xff0c;主要有如下作用&#xff1a; &#xff08;1&#xff09;端口侦听&#xff0c;nc 可以作为 server 以 TCP 或 UDP 方式侦听指定端口&#xff1b; &#xff08;2&#x…...

1.Spring入门

1.1 Spring简介 Spring是一个轻量级Java 企业级应用程序开发框架&#xff0c;目的是为了解决企业级应用开发的业务逻辑层和其他各层的耦合问题。它是一个分层的JavaSE/EEfull-stack(一站式) 轻量级开源框架&#xff0c;为开发Java应用程序提供全面的基础架构支持。 Spring Fra…...

【JavaEE Spring 项目】消息队列的设计

消息队列的设计 一、消息队列的背景知识二、需求分析核心概念⼀个⽣产者, ⼀个消费者N 个⽣产者, N 个消费者Broker Server 中的相关概念核⼼ API交换机类型 (Exchange Type)持久化⽹络通信消息应答 三、 模块划分四、 项⽬创建五、创建核心类创建 Exchange创建 MSGQUeue创建 B…...

SpringFramework学习笔记(Spring IoC,aop,tx)

SpringFramework 本篇笔记是基于尚硅谷学习资料的整理&#xff0c;涉及到其笔记的简化&#xff0c;补充&#xff0c;以及我在学习中遇到的与无法理解的问题及解决&#xff0c;如果想看完整及后续的笔记&#xff0c;可以去https://www.wolai.com/v5Kuct5ZtPeVBk4NBUGBWF查看官方…...

口腔管理平台 |基于springboot框架+ Mysql+Java+B/S结构的口腔管理平台 设计与实现(可运行源码+数据库+lw文档)

推荐阅读100套最新项目 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 目录 前台功能效果图 管理员功能登录前台功能效果图 会员功能 系统功能设计 数据库E-R图设计 lunwen参考…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...