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

[USACO2023-JAN-Bronze] T1 LEADERS 题解

一、题目描述

Farmer John 有 N 头牛 (2≤N≤10^5)。 每头牛有对应的品种:Guernsey or Holstein. 按照惯例,这些牛站成一排,编号从1到N。在某一天,每头牛写了一个数字, 第i头牛写的数字Ei明确地表示了一个范围,表示范围从i到Ei(i≤Ei≤N)的每一头牛都归它管(包含Ei)。FJ最近发现每个种类的牛都有它明确的头领。FJ不知道谁才是头领,但是他知道每个头领写的范围必须包含它的种类的所有牛,或者包含其他种类的牛的头领(或者都有)。帮助FJ计算有多少对可能的头领,数据确保至少有一对可能的头领。

输入

第一行包含一个整数 N.

第二行包含一个长度为N的字符串,第i个字符表示第i头牛的种类(G 表示 Guernsey , H 表示 Holstein). 数据确保至少有一头Guernsey 和一头Holstein.

第三行包含N个整数,表示E1……En。

输出

输出有多少对可行的头领。

样例

输入

复制

4

GHHG

2 4 3 4

输出

复制

1

输入

复制

3

GGH

2 3 3

输出

复制

2

说明

样例1说明:只有一对可行的头领(1,2). 第1头牛包含其他种类的头领(cow 2). 第二头牛包含所有它种类的牛(Holstein).没有其他可行的头领对。例如,(2,4)不行是因为第4头牛的范围没有包含其他种类的头领,也没有包含它的种类的其他所有牛。

样例2说明:有两个可行的头领对: (1,3) 和 (2,3).

• Inputs 3-5: N≤100

• Inputs 6-10: N≤3000

• Inputs 11-17: No additional constraints.

二、分析

  1. 头领的条件:第一,包含同类所有的牛,第二,包含异类首领。

  1. 后面的牛不可能包含前面的。

  1. G、H有前后顺序,后面种类的奶牛的第一个必是头领,后面的这种奶牛不可能是头领。

  1. 结论:靠后种类的奶牛只有一个头领,排名靠前的奶牛如果是第一头牛并且包含所有同种类的牛或者包含靠后种类的头领,则头领++

三、代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
char s[N];
int a[N];
int main() {scanf("%d%s",&n,s+1);for(int i=1;i<=n;i++) scanf("%d",&a[i]);int pos,last;for(int i=2;i<=n;i++){if(s[i]!=s[1]){        //找位置靠后种类奶牛的第一个位置pos=i;break;}}for(int i=1;i<=n;i++){if(s[i]==s[1]){        //第一头种类奶牛的最后一个位置last=i;}}int ans=0;for(int i=1;i<pos;i++){if((i==1&&a[i]>=last)||a[i]>=pos)ans++;}printf("%d",ans);return 0;
}

相关文章:

[USACO2023-JAN-Bronze] T1 LEADERS 题解

一、题目描述Farmer John 有 N 头牛 (2≤N≤10^5)。 每头牛有对应的品种&#xff1a;Guernsey or Holstein. 按照惯例&#xff0c;这些牛站成一排&#xff0c;编号从1到N。在某一天&#xff0c;每头牛写了一个数字, 第i头牛写的数字Ei明确地表示了一个范围&#xff0c;表示范围…...

第二章:unity性能优化之drawcall优化-1

目录 前言&#xff1a; 一、什么是drawcall 二、如何合批 1、什么是合批&#xff1f; 2、静态批处理 1、什么是静态批处理&#xff1a; 2、静态合批的规则 3、动态批处理 4、GPU Instancing 1、GPU instancing的定义 2、编写支持GPU instancing Shader步骤 5、…...

【2341. 数组能形成多少数对】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个下标从 0 开始的整数数组 nums 。在一步操作中&#xff0c;你可以执行以下步骤&#xff1a; 从 nums 选出 两个 相等的 整数从 nums 中移除这两个整数&#xff0c;形成一个 数对 请你在 nu…...

[TPAMI‘21] Heatmap Regression via Randomized Rounding

paper: https://arxiv.org/pdf/2009.00225.pdf code: https://github.com/baoshengyu/H3R 总结&#xff1a;本文提出一套编解码方法&#xff1a; 编码&#xff1a;random-round整数化 激活点响应值表征小数部分&#xff0c;使得GT可以通过编码后的heatmap解码得到&#xff1b…...

pytorch下tensorboard使用[远程服务器]

** 1、安装tensorboard ** pip install tensorboard可以不安装tensorflow&#xff0c;后续会有提示&#xff1a; TensorFlow installation not found - running with reduced feature set. 但是没有影响。 2、创建环境&#xff0c;导出数据 这一步由代码中的writer完成。 …...

CentOS下安装Nginx的详细步骤

1.安装依赖&#xff1a;yum -y install gcc gcc-c make libtool zlib zlib-devel openssl openssl-devel pcre pcre-devel 2.下载Nginx安装包&#xff1a;wget -c https://nginx.org/download/nginx-1.18.0.tar.gz 3.解压,进入解压目录&#xff1a; tar -zxvf nginx-1.18.0.…...

CSS编码规范

本篇文章是基于王叨叨大佬师父维护的文档梳理的&#xff0c;有兴趣可以去看一下原文CSS编码规范。 其实不管是HTML也好&#xff0c;还是CSS也好&#xff0c;有些规范其实是共通的。 1. 命名 class的命名应该偏向语义化&#xff0c;不是为了样式而去命名&#xff0c;而是通过…...

Linux下makefile 编译项目

文章目录1、规划makefile编写2、makefile文件2.1、根目录下common.mk2.2、config.mk2.3、根目录makefile2.4、其他目录下1、规划makefile编写 a、根目录下放三个文件&#xff1a; 1、makefile&#xff1a;是咱们编译项目的入口脚本&#xff0c;编译项目从这里开始&#xff0c;…...

Linux磁盘查看,使用(分区、格式化、挂载)

目录 0、观察磁盘分区状态&#xff1a;lsblk、blkid、parted 0.1 lsblk列出系统上的所有磁盘列表 0.2 blkid列出设备的UUID等参数 0.3 parted列出磁盘的分区表类型与分区信息 1、磁盘分区&#xff1a;gdisk、fdisk 1.1 fdisk 2、磁盘格式化&#xff08;创建文件系统…...

走进WebGL

什么是 WebGL&#xff1f; WebGL 是一种跨平台、免版税的 API&#xff0c;用于在 Web 浏览器中创建 3D 图形。基于 OpenGL ES 2.0&#xff0c;WebGL 使用 OpenGL 着色语言 GLSL&#xff0c;并提供熟悉的标准 OpenGL API。因为它在 HTML5 Canvas 元素中运行&#xff0c;所以 We…...

Unity 中 Awake 和 Start 时机与 GameObject的关系

Awake和Start很相似&#xff0c;都是在脚本的初始阶段执行 但是有两点重要不同&#xff1a; Awake先执行Awake即便在脚本 disabled &#xff08;即enabled false&#xff09;时&#xff0c;也会执行&#xff0c;但是Start就不会执行了 对一个物体&#xff1a; 当初始没有激…...

1月份 GameFi 行业报告

Jan. 2023&#xff0c; DanielData Source&#xff1a; January Monthly GameFi Report在经历了艰难的一年之后&#xff0c;1 月是对加密货币市场最有利的月份。虽然可以说的大部分内容适用于其他看涨周期&#xff0c;但有几个统计数据令 1 月在区块链领域非常有趣。例如&#…...

JVM - 调优

目录 调什么,如何调 内存方面 线程方面 如何调优 调优的目标,策略和冷思考 JVM调优的目标 常见调优策略 JVM调优冷思考 调优经验与内存泄漏分析 JVM调优经验 内存泄露 调什么,如何调 内存方面 JVM需要的内存总大小各块内存分配&#xff0c;新生代、老年代、存活区选…...

flask配置https协议

感谢https://blog.csdn.net/qq_33934427/article/details/127456673&#xff0c;文中多有参考再实践一、要用https协议需要有ca证书&#xff0c;在windows10先下载windows版本openssl&#xff0c;地址如下https://share.weiyun.com/vfjVrMAb我是64位的选择下载完毕安装后配置环…...

Springboot 我随手封装了一个万能的导出excel工具,传什么都能导出

前言 如题&#xff0c;这个小玩意&#xff0c;就是不限制你查的是哪张表&#xff0c;用的是什么类。 我直接一把梭&#xff0c;嘎嘎给你一顿导出。 我知道&#xff0c;这是很多人都想过的&#xff0c; 至少我就收到很多人问过我这个类似的问题。 我也跟他们说了&#xff0c;但…...

【Linux详解】——进程控制(创建、终止、等待、替换)

&#x1f4d6; 前言&#xff1a;本期介绍进程控制&#xff08;创建、终止、等待、替换&#xff09;。 目录&#x1f552; 1. 进程创建&#x1f558; 1.1 fork函数初识&#x1f558; 1.2 fork的返回值问题&#x1f558; 1.3 写时拷贝&#x1f558; 1.4 创建多个进程&#x1f552…...

HummerRisk V0.9.1:操作审计增加百度云,增加主机检测规则及多处优化

HummerRisk V0.9.0发布&#xff1a;增加RBAC 资源拓扑图&#xff0c;首页新增检查的统计数据&#xff0c;云检测、漏洞、主机等模块增加规则&#xff0c;对象存储增加京东云&#xff0c;操作审计增加金山云&#xff0c;镜像仓库新增设置别名。 感谢社区中小伙伴们的反馈&#…...

Rust入门(十六):手写web服务器和线程池

这一章将实现一个手写的 web server 和 多线程的服务器&#xff0c;用到之前学到的所有特性 简单的web server 作为一个 web 服务器&#xff0c;我们首先要能接收到请求&#xff0c;目前市面上的 web 服务大多数都是基于 HTTP 和 HTTPS 协议的&#xff0c;而他们有是基于 TCP…...

数据结构——第二章 线性表(1)——顺序结构

线性表1. 线性表1.1 线性表的定义1.1.1 访问型操作1.1.2 加工型操作1.2 线性表的顺序存储结构1.2.1 定义顺序表数据类型方法11.2.2 定义顺序表数据类型方法21.3 顺序表的基本操作实现1.3.1 顺序表的初始化操作1.3.2 顺序表的插入操作1.3.3 顺序表的删除操作1.3.4 顺序表的更新操…...

YOLO 格式数据集制作

目录 1. YOLO简介 2.分割数据集准备 3.代码展示 整理不易&#xff0c;欢迎一键三连&#xff01;&#xff01;&#xff01; 1. YOLO简介 YOLO&#xff08;You Only Look Once&#xff09;是一种流行的目标检测和图像分割模型&#xff0c;由华盛顿大学的 Joseph Redmon 和 Al…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...