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

【C++】牛客 ——DP36 abb

✨题目链接:

DP36 abb


✨题目描述 

leafee 最近爱上了 abb 型语句,比如“叠词词”、“恶心心”

leafee 拿到了一个只含有小写字母的字符串,她想知道有多少个 "abb" 型的子序列?
定义: abb 型字符串满足以下条件:

  1. 字符串长度为 3 。
  2. 字符串后两位相同。
  3. 字符串前两位不同。

✨输入描述:

第一行一个正整数 𝑛n

第二行一个长度为 𝑛n 的字符串(只包含小写字母)

1≤𝑛≤1051≤n≤105

✨输出描述:

"abb" 型的子序列个数。 

✨示例1

📍输入

6 abcbcc

📍输出

8

📍说明

共有1个abb,3个acc,4个bcc 

✨解题思路

 动态规划:

  1. 初始化计数器和数组

    • f[26]:用来记录每个字母对结果的当前贡献。
    • g[26]:用来记录每个字母的出现次数。
    • res:结果变量,用来存储符合条件的子序列个数。
    • i:用来记录当前遍历到的字符的索引。
  2. 遍历字符串

    • 对于字符串中的每一个字符e
      1. 将当前字符对结果的贡献加到res中。
      2. 更新字符e的贡献值:f[e-'a'] = f[e-'a'] + i - g[e-'a']
        • i代表当前字符之前的所有字符数。
        • g[e-'a']是当前字符e之前出现的所有字符e的次数。
        • 通过计算i - g[e-'a'],得到当前字符e之前所有非e字符的数量。
      3. 更新字符e的出现次数:g[e-'a'] += 1
      4. 增加遍历索引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

✨题目链接&#xff1a; DP36 abb ✨题目描述 leafee 最近爱上了 abb 型语句&#xff0c;比如“叠词词”、“恶心心” leafee 拿到了一个只含有小写字母的字符串&#xff0c;她想知道有多少个 "abb" 型的子序列&#xff1f; 定义&#xff1a; abb 型字符串满足以下…...

SpringBoot如何实现跨域?

定义一个配置类&#xff0c;实现WebMvcConfigurer接口&#xff0c;重写addCorsMappings方法 Configuration public class CorsConfig implements WebMvcConfigurer {Overridepublic void addCorsMappings(CorsRegistry registry) {registry.addMapping("/**").allow…...

SW 草图偏移 先预选

因为有些不能用链全部选,可以先框选要偏移的,再点偏移命令...

5.23 Linux中超时检测方式+模拟面试

1.IO多路复用的原理&#xff1f; IO多路复用使得一个或少量线程资源处理多个连接的IO事件的技术。对于要处理的多个阻塞的IO操作&#xff0c;建立集合并存储它们的文件描述符&#xff0c;利用单个阻塞函数去监控集合中文件描述符事件到达的情况&#xff0c;&#xff08;如果到…...

MySQL数据表索引命名规范

在数据库设计和开发过程中&#xff0c;索引是提高查询性能的重要工具。合理的索引命名规范不仅能提高代码的可读性&#xff0c;还能便于维护和管理。本文将详细介绍MySQL数据表索引的命名规范&#xff0c;包括不同类型索引的命名方法&#xff0c;并提供多个代码示例以说明如何命…...

python内置函数map/filter/reduce详解

在Python中&#xff0c;map(), filter(), 和 reduce() 是内置的高级函数(实际是class)&#xff0c;用于处理可迭代对象&#xff08;如列表、元组等&#xff09;的元素。这些函数通常与lambda函数一起使用&#xff0c;以简洁地表达常见的操作。下面我将分别解释这三个函数。 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单片机液位控制器 &#xff08;仿真&#xff0b;程序&#xff0b;原理图PCB&#xff0b;设计报告&#xff09; 功能介绍 具体功能&#xff1a; 1.使用HC-SR04测量液位&#xff0c;LCD1602显示&#xff1b; 2.当水位高于设定上限的时候&#xff0c;对应声光报警报警&am…...

详细分析Element中的MessageBox基本知识(附Demo)

目录 前言1. 基本知识2. Demo2.1 确认框2.2 警告框2.3 对话框 3. this.$confirm 前言 详细知识推荐阅读&#xff1a;详细分析Element Plus中的ElMessageBox弹窗用法&#xff08;附Demo及模版&#xff09; MessageBox则常用于Vue2 1. 基本知识 MessageBox 是 Element UI 提供…...

音视频开发8 音视频中SDL的使用,SDL 在windows上环境搭建,SDL 使用 以及 常用 API说明,show YUV and play PCM

1.SDL简介 SDL&#xff08;Simple DirectMedia Layer&#xff09;&#xff0c;是一个跨平台的C语言多媒体开发库。 支持Windows、Mac OS X、Linux、iOS、Android 提供对音频、键盘、鼠标、游戏操纵杆、图形硬件的底层访问 很多的视频播放软件、模拟器、受欢迎的游戏都在使用…...

P1003 [NOIP2011 提高组] 铺地毯

题目传送门&#xff1a; P1003 [NOIP2011 提高组] 铺地毯 AC代码&#xff1a; #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语言学习笔记之指针(一)

目录 什么是指针&#xff1f; 指针和指针类型 指针的类型 指针类型的意义 指针-整数 指针的解引用 指针 - 指针 指针的关系运算 野指针 什么是野指针&#xff1f; 野指针的成因 如何规避野指针&#xff1f; 二级指针 什么是指针&#xff1f; 在介绍指针之前&#…...

化学中的不确定性。

化学中的不确定性TOC 基于元素分析的无机化学的理论大厦应该说早已落成了&#xff0c;但是却仍然存在着一些列的难解甚至是无解问题&#xff0c;这些大多是在使用理论解释现象时遇到的困难&#xff0c;有些则是在生产实践中生产工艺和生产工序设计和优化中发现的问题。于是&…...

AWS容器之Fargate

AWS Fargate是亚马逊提供的一种容器管理服务&#xff0c;它允许开发人员在AWS云中轻松运行容器化应用程序&#xff0c;而无需管理底层的服务器基础架构。Fargate可以自动管理容器的部署、扩展和负载平衡&#xff0c;并提供了与ECS和EKS等AWS容器服务集成的能力。适用于容器的无…...

C#面:DataReader与Dataset有什么区别

C#中的DataReader和DataSet都是用于处理数据的类&#xff0c;但它们有一些区别。 DataReader是一种轻量级的只进只读数据流&#xff0c;用于从数据库中检索数据。它是一种快速且高效的数据访问方式&#xff0c;适用于大量数据的读取。DataReader一次只能读取一行数据&#xff…...

操作系统课程实验1-进程调度模拟实验

操作系统课程实验1-进程调度模拟实验 一、实验介绍 1.1 实验目的 本实验模拟在单处理机环境下的处理机调度&#xff0c;帮助理解进程调度的概念&#xff0c;深入了解进程控制块的功能&#xff0c;以及进程的创建、撤销和进程各个状态间的转换过程。 1.2 实验内容 进程调度算…...

JVM CMS 在Full GC时针对跨代引用的优化

个人博客 JVM CMS 在Full GC时针对跨代引用的优化 | iwts’s blog 跨代引用问题 Full GC慢的一个很重要的问题&#xff1a;跨代引用。 简单描述就是&#xff1a; 现代JVM一般是根据对象存活的特性进行了分代&#xff0c;提高了垃圾收集的效率。但是像在回收新生代的时候&a…...

【Makefile】Makefile 编译 Keil 工程(Linux 环境)

本文使用的开发板为 stm32f103C8T6&#xff0c;使用的驱动库为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自动创建&#xff0c;HttpResponse对象由程序员创建在每一个视图函数中必须返回一个HttpResponse对象,当然也可以是HttpResponse子对象 1.不用模板,直接返回数据 from django.http import HttpRespons…...

企业活动想找媒体报道宣传怎样联系媒体?

在那遥远的公关江湖里,有一个传说,说的是一位勇士,手持鼠标和键盘,踏上了寻找媒体圣杯的征途。这位勇士,就是我们亲爱的市场部门小李,他的任务是为公司即将举行的一场盛大的企业活动找到媒体的聚光灯。 小李的故事,开始于一张空白的Excel表格,上面列着各大媒体的名称,旁边是一片…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...