【C++】牛客 ——DP36 abb
✨题目链接:
DP36 abb
✨题目描述
leafee 最近爱上了 abb 型语句,比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串,她想知道有多少个 "abb" 型的子序列?
定义: abb 型字符串满足以下条件:
- 字符串长度为 3 。
- 字符串后两位相同。
- 字符串前两位不同。
✨输入描述:
第一行一个正整数 𝑛n
第二行一个长度为 𝑛n 的字符串(只包含小写字母)
1≤𝑛≤1051≤n≤105
✨输出描述:
"abb" 型的子序列个数。
✨示例1
📍输入
6 abcbcc
📍输出
8
📍说明
共有1个abb,3个acc,4个bcc
✨解题思路
动态规划:
-
初始化计数器和数组:
f[26]:用来记录每个字母对结果的当前贡献。g[26]:用来记录每个字母的出现次数。res:结果变量,用来存储符合条件的子序列个数。i:用来记录当前遍历到的字符的索引。
-
遍历字符串:
- 对于字符串中的每一个字符
e:- 将当前字符对结果的贡献加到
res中。 - 更新字符
e的贡献值:f[e-'a'] = f[e-'a'] + i - g[e-'a']。i代表当前字符之前的所有字符数。g[e-'a']是当前字符e之前出现的所有字符e的次数。- 通过计算
i - g[e-'a'],得到当前字符e之前所有非e字符的数量。
- 更新字符
e的出现次数:g[e-'a'] += 1。 - 增加遍历索引
i。
- 将当前字符对结果的贡献加到
- 对于字符串中的每一个字符
贡献值可以理解为在这以前区间有多少个 _ x (假设现在 i 位置字符为x)
✨代码
#include <iostream>
using namespace std;int main() {int n;cin >> n;string str;cin >> str;long long res = 0;int f[26]={0};int g[26]={0};long long i=0;for(auto e:str){res+=f[e-'a'];f[e-'a']=f[e-'a']+i-g[e-'a'];g[e-'a']=g[e-'a']+1;i++;}cout << res << endl;return 0;
}
※ 如果文章对你有帮助的话,可以点赞收藏!!谢谢支持
相关文章:
【C++】牛客 ——DP36 abb
✨题目链接: DP36 abb ✨题目描述 leafee 最近爱上了 abb 型语句,比如“叠词词”、“恶心心” leafee 拿到了一个只含有小写字母的字符串,她想知道有多少个 "abb" 型的子序列? 定义: abb 型字符串满足以下…...
SpringBoot如何实现跨域?
定义一个配置类,实现WebMvcConfigurer接口,重写addCorsMappings方法 Configuration public class CorsConfig implements WebMvcConfigurer {Overridepublic void addCorsMappings(CorsRegistry registry) {registry.addMapping("/**").allow…...
SW 草图偏移 先预选
因为有些不能用链全部选,可以先框选要偏移的,再点偏移命令...
5.23 Linux中超时检测方式+模拟面试
1.IO多路复用的原理? IO多路复用使得一个或少量线程资源处理多个连接的IO事件的技术。对于要处理的多个阻塞的IO操作,建立集合并存储它们的文件描述符,利用单个阻塞函数去监控集合中文件描述符事件到达的情况,(如果到…...
MySQL数据表索引命名规范
在数据库设计和开发过程中,索引是提高查询性能的重要工具。合理的索引命名规范不仅能提高代码的可读性,还能便于维护和管理。本文将详细介绍MySQL数据表索引的命名规范,包括不同类型索引的命名方法,并提供多个代码示例以说明如何命…...
python内置函数map/filter/reduce详解
在Python中,map(), filter(), 和 reduce() 是内置的高级函数(实际是class),用于处理可迭代对象(如列表、元组等)的元素。这些函数通常与lambda函数一起使用,以简洁地表达常见的操作。下面我将分别解释这三个函数。 1. …...
PICO VR眼镜定制播放器使用说明文档videoplayerlib-ToB.apk
安装高级定制播放器 高级定制播放器下载地址:https://download.csdn.net/download/ahphong/89360454 仅限用于PICO G2、G3、G4、NEO系列VR眼镜上使用, 用途:用于第三方APP(开发者)调用定制播放器播放2D、3D、180、360全景视频。 VR眼镜系统请升级到最新版,可在官网下载,…...
基于51单片机的超声波液位测量与控制系统
基于51单片机液位控制器 (仿真+程序+原理图PCB+设计报告) 功能介绍 具体功能: 1.使用HC-SR04测量液位,LCD1602显示; 2.当水位高于设定上限的时候,对应声光报警报警&am…...
详细分析Element中的MessageBox基本知识(附Demo)
目录 前言1. 基本知识2. Demo2.1 确认框2.2 警告框2.3 对话框 3. this.$confirm 前言 详细知识推荐阅读:详细分析Element Plus中的ElMessageBox弹窗用法(附Demo及模版) MessageBox则常用于Vue2 1. 基本知识 MessageBox 是 Element UI 提供…...
音视频开发8 音视频中SDL的使用,SDL 在windows上环境搭建,SDL 使用 以及 常用 API说明,show YUV and play PCM
1.SDL简介 SDL(Simple DirectMedia Layer),是一个跨平台的C语言多媒体开发库。 支持Windows、Mac OS X、Linux、iOS、Android 提供对音频、键盘、鼠标、游戏操纵杆、图形硬件的底层访问 很多的视频播放软件、模拟器、受欢迎的游戏都在使用…...
P1003 [NOIP2011 提高组] 铺地毯
题目传送门: P1003 [NOIP2011 提高组] 铺地毯 AC代码: #include<bits/stdc.h>using namespace std;int a[10005],b[10005],g[10005],k[10004];int main() {int n,x,y;cin>>n;for(int i1;i<n;i) cin>>a[i]>>b[i]>>g[…...
C语言学习笔记之指针(一)
目录 什么是指针? 指针和指针类型 指针的类型 指针类型的意义 指针-整数 指针的解引用 指针 - 指针 指针的关系运算 野指针 什么是野指针? 野指针的成因 如何规避野指针? 二级指针 什么是指针? 在介绍指针之前&#…...
化学中的不确定性。
化学中的不确定性TOC 基于元素分析的无机化学的理论大厦应该说早已落成了,但是却仍然存在着一些列的难解甚至是无解问题,这些大多是在使用理论解释现象时遇到的困难,有些则是在生产实践中生产工艺和生产工序设计和优化中发现的问题。于是&…...
AWS容器之Fargate
AWS Fargate是亚马逊提供的一种容器管理服务,它允许开发人员在AWS云中轻松运行容器化应用程序,而无需管理底层的服务器基础架构。Fargate可以自动管理容器的部署、扩展和负载平衡,并提供了与ECS和EKS等AWS容器服务集成的能力。适用于容器的无…...
C#面:DataReader与Dataset有什么区别
C#中的DataReader和DataSet都是用于处理数据的类,但它们有一些区别。 DataReader是一种轻量级的只进只读数据流,用于从数据库中检索数据。它是一种快速且高效的数据访问方式,适用于大量数据的读取。DataReader一次只能读取一行数据ÿ…...
操作系统课程实验1-进程调度模拟实验
操作系统课程实验1-进程调度模拟实验 一、实验介绍 1.1 实验目的 本实验模拟在单处理机环境下的处理机调度,帮助理解进程调度的概念,深入了解进程控制块的功能,以及进程的创建、撤销和进程各个状态间的转换过程。 1.2 实验内容 进程调度算…...
JVM CMS 在Full GC时针对跨代引用的优化
个人博客 JVM CMS 在Full GC时针对跨代引用的优化 | iwts’s blog 跨代引用问题 Full GC慢的一个很重要的问题:跨代引用。 简单描述就是: 现代JVM一般是根据对象存活的特性进行了分代,提高了垃圾收集的效率。但是像在回收新生代的时候&a…...
【Makefile】Makefile 编译 Keil 工程(Linux 环境)
本文使用的开发板为 stm32f103C8T6,使用的驱动库为stm32标准库。 目录 一、软件下载 1、stm32 标准库 2、arm-none-eabi 工具链 3、烧录器 二、Keil 工程改造 1、Keil 工程 2、基本 Makefile 工程 3、添加启动文件 4、添加链接脚本 5、去掉 core_cm3.c 三…...
Django的视图层——1HttpResponse对象详解
在django.http模块中定义了HttpResponse对象的APIHttpRequest对象由Django自动创建,HttpResponse对象由程序员创建在每一个视图函数中必须返回一个HttpResponse对象,当然也可以是HttpResponse子对象 1.不用模板,直接返回数据 from django.http import HttpRespons…...
企业活动想找媒体报道宣传怎样联系媒体?
在那遥远的公关江湖里,有一个传说,说的是一位勇士,手持鼠标和键盘,踏上了寻找媒体圣杯的征途。这位勇士,就是我们亲爱的市场部门小李,他的任务是为公司即将举行的一场盛大的企业活动找到媒体的聚光灯。 小李的故事,开始于一张空白的Excel表格,上面列着各大媒体的名称,旁边是一片…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
