贡献法: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 扔掉。
所有更长的子串(
GHGH、HGHG和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 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。 奶牛目前排成一排,Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而,他…...
Java实现简单的通讯录
每日一言 泪眼问花花不语,乱红飞过秋千去。 —欧阳修- 简单的通讯录实现,跟写Java实现图书管理系统差不多,用到的知识也差不多,就当个小练习,练习一下写Java程序的手感。 Java实现图书管理系统 关于通讯录的代码都写…...
服务器数据恢复—raid5热备盘上线同步数据失败的如何恢复数据
服务器数据恢复环境&故障&分析: 一台存储上有一组由多块硬盘组建的raid5阵列,该raid5阵列中的一块硬盘掉线,热备盘自动上线同步数据的过程中,raid阵列中又有一块硬盘掉线,热备盘的数据同步被中断,r…...
探索C语言中的循环结构
循环结构是程序设计中一种重要的控制结构,它允许程序重复执行特定的代码块,直到满足某个条件为止。在C语言中,循环结构有多种形式,如for循环、while循环和do-while循环。本文将介绍C语言中的循环结构,并讨论它们的用法…...
数学建模-估计出租车的总数
文章目录 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)是一种结构化软件设计模式,它提供了一种通过向类对象添加行为来修改类对象的方法,而不会影响同一类的其它对象行为。该模式允许在不修改抽象类的情况下添加类功能。它从本质上允许基类代码对不可预见的修改具有前瞻…...
Python 查找并高亮PDF中的指定文本
在处理大量PDF文档时,有时我们需要快速找到特定的文本信息。本文将提供以下三个Python示例来帮助你在PDF文件中快速查找并高亮指定的文本。 查找并高亮PDF中所有的指定文本查找并高亮PDF某个区域内的指定文本使用正则表达式搜索指定文本并高亮 本文将用到国产第三方…...
LEETCODE LCS 03. 主题空间
题目描述如上,这个题主要运用了DFS的思想,同时走过的路径标记为6,即可在后续的遍历中过滤掉重复的元素,其他则类似边界条件的判断和题目条件的判断,求最大值,只需要一次遍历中累加对比每一次得即可。 模板&…...
【Spring Boot 源码学习】深入应用上下文初始化器实现
《Spring Boot 源码学习系列》 深入应用上下文初始化器实现 一、引言二、往期内容三、主要内容3.1 spring-boot 子模块中内置的实现类3.1.1 ConfigurationWarningsApplicationContextInitializer3.1.2 ContextIdApplicationContextInitializer3.1.3 DelegatingApplicationConte…...
【Docker】一文趣谈Docker
🏡浩泽学编程:个人主页 🔥 推荐专栏:《深入浅出SpringBoot》《java对AI的调用开发》 《RabbitMQ》《Spring》《SpringMVC》《项目实战》 🛸学无止境,不骄不躁,知行合一 文章目录 …...
代码随想录day19(2)二叉树:二叉树的最大深度(leetcode104)
题目要求:求出二叉树的最大深度 思路:首先要区分二叉树的高度与深度。二叉树的高度是任一结点到叶子结点的距离,而二叉树的深度指的是任一节点到根节点的距离(从1开始)。所以求高度使用后序遍历(从下往上&…...
Lua中文语言编程源码-第五节,更改lcorolib.c协程库函数, 使Lua加载中文库关键词(与所有的基础库相关)
源码已经更新在CSDN的码库里: git clone https://gitcode.com/funsion/CLua.git 在src文件夹下的lcorolib.c协程库函数,Coroutine Library:表明这个C源文件实现了Lua的协程库(Coroutine Library),即提供了…...
Docker学习之数据管理(超详解析)
Docker存储资源类型: 用户在使用 Docker 的过程中,势必需要查看容器内应用产生的数据,或者需要将容器内数据进行备份,甚至多个容器之间进行数据共享,这必然会涉及到容器的数据管理: (1ÿ…...
FDTD液晶折射率各项异性表示方法
由于FDTD的数据都是沿坐标轴的,各向异性材料的参数也需要根据坐标轴来输入。 首先要了解坐标变换。 坐标变换 这里以二维坐标变化为例。 矢量下我们可以发现OP可在两个坐标系下分别表示 接下来将两个坐标相互关联,这里以Xb举例,Yb同理 注…...
RoketMQ主从搭建
vim /etc/hosts# IP与域名映射,端口看自己的#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(netcat)是一个短小精悍、功能实用、简单可靠的网络工具,主要有如下作用: (1)端口侦听,nc 可以作为 server 以 TCP 或 UDP 方式侦听指定端口; (2&#x…...
1.Spring入门
1.1 Spring简介 Spring是一个轻量级Java 企业级应用程序开发框架,目的是为了解决企业级应用开发的业务逻辑层和其他各层的耦合问题。它是一个分层的JavaSE/EEfull-stack(一站式) 轻量级开源框架,为开发Java应用程序提供全面的基础架构支持。 Spring Fra…...
【JavaEE Spring 项目】消息队列的设计
消息队列的设计 一、消息队列的背景知识二、需求分析核心概念⼀个⽣产者, ⼀个消费者N 个⽣产者, N 个消费者Broker Server 中的相关概念核⼼ API交换机类型 (Exchange Type)持久化⽹络通信消息应答 三、 模块划分四、 项⽬创建五、创建核心类创建 Exchange创建 MSGQUeue创建 B…...
SpringFramework学习笔记(Spring IoC,aop,tx)
SpringFramework 本篇笔记是基于尚硅谷学习资料的整理,涉及到其笔记的简化,补充,以及我在学习中遇到的与无法理解的问题及解决,如果想看完整及后续的笔记,可以去https://www.wolai.com/v5Kuct5ZtPeVBk4NBUGBWF查看官方…...
口腔管理平台 |基于springboot框架+ Mysql+Java+B/S结构的口腔管理平台 设计与实现(可运行源码+数据库+lw文档)
推荐阅读100套最新项目 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 目录 前台功能效果图 管理员功能登录前台功能效果图 会员功能 系统功能设计 数据库E-R图设计 lunwen参考…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
