第十四届蓝桥杯省赛C++B组G题【子串简写】题解(AC)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

题目大意

给定字符串 s s s,字符 a , b a, b a,b,问字符串 s s s 中有多少个 a a a 开头 b b b 结尾的子串。

解题思路

20pts

使用二重循环枚举左端点和右端点,判断是否为 a a a 开头 b b b 结尾的字符串,是则答案加一。

100pts

数据范围较大,我们需要将时间复杂度控制在 O ( n log ⁡ n ) O(n\log n) O(nlogn) 以内。

法一

我们需要找到所有 a a a 开头 b b b 结尾的字符串,那么我们可以对于每个字符 b b b,去看 b b b 的左侧有几个 a a a,那么这些 a … b a\dots b ab 就是合法的字符串。统计某个位置的左侧有几个字符 a a a,我们可以使用前缀和算法进行维护。

法二

我们可以去遍历整个字符串,对于每个 a a a 字符的右侧有几个字符 b b b,那么这些 a … b a \dots b ab 都是合法的字符串。统计某个位置之后字符 b b b 的个数,可以使用后缀和算法进行维护。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 5e5 + 10;int n, m;
string str;
char a, b;
int s[N];int main()
{cin >> m >> str >> a >> b;n = str.size();str = ' ' + str;for (int i = n; i; -- i )s[i] = s[i + 1] + (str[i] == b);LL res = 0;for (int i = 1; i + m - 1 <= n; ++ i )if (str[i] == a)res += s[i + m - 1];cout << res << endl;return 0;
}

【在线测评】

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/371340.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【74CH160组成60进制0-59】2021-11-22

缘由60进制计数 到达60后显示ff-嵌入式-CSDN问答 缘由《数电》用两片74160接成29进制计数器应该怎么接呢&#xff1f;-嵌入式-CSDN问答

Gitlab Fork Workflow(协作工作流)

Gitlab Fork WorkFlow&#xff08;协作工作流&#xff09; Fork WorkFlow用于团队间的协作开发。在开发过程中&#xff0c;我们都需要将最新修改的代码合并到代码库上&#xff0c;在代码合并之前&#xff0c;为了保证代码符合上传要求&#xff08;符合需求、代码规范等&#xf…

【MySQL基础篇】多表查询

1、多表关系 概述&#xff1a;项目开发中&#xff0c;在进行数据库表结构操作设计时&#xff0c;会根据业务需求及业务模板之间的关系&#xff0c;分析并设计表结构&#xff0c;由于业务之间相互关联&#xff0c;所以各个表结构之间也存在着各种联系&#xff0c;基本上分为三种…

Windows如何查看端口是否占用,并结束端口进程

需求与问题&#xff1a;前后端配置了跨域操作&#xff0c;但是仍然报错&#xff0c;可以考虑端口被两个程序占用&#xff0c;找不到正确端口或者后端接口书写是否规范&#xff0c;特别是利用Python Flask书写时要保证缩进是否正确&#xff01; Windows操作系统中&#xff0c;查…

实验五 图像增强—空域滤波

一、实验目的 了解图像平滑滤波器&#xff08;均值滤波和中值滤波&#xff09;和图像锐化算子&#xff08;Sobel算子、Prewitt算子、Laplacian算子&#xff09;在工程领域中的应用&#xff1b;理解图像平滑滤波器和图像锐化算子的工程应用范围&#xff1b;掌握图像平滑滤波器和…

Winform中使用HttpClient实现调用http的post接口并设置传参content-type为application/json示例

场景 Winform中怎样使用HttpClient调用http的get和post接口并将接口返回json数据解析为实体类&#xff1a; Winform中怎样使用HttpClient调用http的get和post接口并将接口返回json数据解析为实体类_winform解析json-CSDN博客 上面使用HttpClient调用post接口时使用的HttpCon…

SQL-DCL(三)

一.DCL介绍 DCL英文全称是Data Control Language(数据库控制语言),用来管理数据库 用户,控制数据库的访问权限。 二.两个方面 1.数据库可以由那些用户访问 2.可以访问那些内容 三.DCL-管理用户 1.查询用户 USE mysql SELECT * FROM user 2.创建用户 CREATE USER…

k8s 部署 springboot 项目内存持续增长问题分析解决

写在前面 工作中遇到&#xff0c;请教公司前辈解决&#xff0c;简单整理记忆博文内容涉及一次 GC 问题的分析以及解决理解不足小伙伴帮忙指正 &#x1f603;,生活加油 99%的焦虑都来自于虚度时间和没有好好做事&#xff0c;所以唯一的解决办法就是行动起来&#xff0c;认真做完…

Appium adb 获取appActivity

方法一&#xff08;最简单有效的方法&#xff09; 通过cmd命令&#xff0c;前提是先打开手机中你要获取包名的APP adb devices -l 获取连接设备详细信息 adb shell dumpsys activity | grep mFocusedActivity 有时获取到的不是真实的Activity 方法二 adb shell monkey -p …

从0-1实现一个前端脚手架

https://gitee.com/childe-jia/kfc-cli.git gitee完整地址 介绍 为什么需要脚手架&#xff1f; 脚手架本质就是一个工具&#xff0c;作用是能够让使用者专注于写代码&#xff0c;它可以让我们只用一个命令就生成一个已经配置好的项目&#xff0c;而不用我们再花时间去配置和安…

【排序算法】—— 快速排序

快速排序的原理是交换排序&#xff0c;其中qsort函数用的排序原理就是快速排序&#xff0c;它是一种效率较高的不稳定函数&#xff0c;时间复杂度为O(N*longN)&#xff0c;接下来就来学习一下快速排序。 一、快速排序思路 1.整体思路 以升序排序为例&#xff1a; (1)、首先随…

CC工具箱使用指南:【相交占比分析】

一、简介 需求场景如下&#xff0c;有【待分析地块】和【面积占比参考】2个图层。2个图层之间存在空间上的重叠。工具的目的是为了分析出【待分析地块】的每1个图斑中&#xff0c;和【面积占比参考】相交的面积&#xff0c;以及和总面积的占比。 举一个应用场景为例&#xff0…

Idea新增Module报错:sdk ‘1.8‘ type ‘JavaSDK‘ is not registered in ProjectJdkTable

文章目录 一&#xff0c;创建Module报错二&#xff0c;原因分析三&#xff0c;解决方案1&#xff0c;点击上图的加号&#xff0c;把JDK8添加进来即可2&#xff0c;点击左侧[Project]&#xff0c;直接设置SDK为JDK8 四&#xff0c;配置检查与验证 一&#xff0c;创建Module报错 …

【Linux】:程序地址空间

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关Linux程序地址空间的相关知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从…

PingCAP 成为全球数据库管理系统市场增速最快的厂商

近日&#xff0c;Gartner 发布的《Market Share Analysis: Database Management Systems, Worldwide, 2023》&#xff08;2024 年 6 月&#xff09;报告显示&#xff1a;“2023 年全球数据库管理系统&#xff08;DBMS&#xff09;市场的增长率为 13.4%&#xff0c;略低于去年的…

LLM4Decompile——专门用于反编译的大规模语言模型

概述 论文地址&#xff1a;https://arxiv.org/abs/2403.05286 反编译是一种将已编译的机器语言或字节码转换回原始高级编程语言的技术。该技术用于分析软件的内部工作原理&#xff0c;尤其是在没有源代码的情况下&#xff1b;Ghidra 和 IDA Pro 等专用工具已经开发出来&#…

学习笔记——动态路由——OSPF聚合(汇总)

十一、OSPF聚合(汇总) 1、路由聚合(汇总) 路由汇总是一种重要的思想&#xff0c;在大型的项目中是必须考虑的一个重点事项。随着网络的规模越来越大&#xff0c;网络中的设备所需维护的路由表项也就会越来越多&#xff0c;路由表的规模也就会逐渐变大&#xff0c;而路由表是需…

【TB作品】51单片机 Proteus仿真 超声波LCD1602ADC0832 身高体重测量仪

00024 超声波LCD1602ADC0832 实验报告&#xff1a;基于51单片机的身高体重测量仪设计 背景介绍 本实验设计并实现了一个基于51单片机的身高体重测量仪。该系统利用超声波传感器测量高度&#xff0c;通过ADC0832模数转换芯片获取重量数据&#xff0c;并使用LCD1602显示屏显示…

系统测试-测试方法学习

目录 &#xff08;1&#xff09;等价类 &#xff08;2&#xff09;边界值 &#xff08;3&#xff09;正交&#xff1a;&#xff08;只用于确定排列组合&#xff0c;不确定具体内容&#xff09; (4)判定表法 &#xff08;5&#xff09;流程分析法 &#xff08;6&#xff0…

Day05-04-持续集成总结

Day05-04-持续集成总结 1. 持续集成2. 代码上线目标项目 1. 持续集成 git 基本使用, 拉取代码,上传代码,分支操作,tag标签 gitlab 用户 用户组 项目 , 备份,https,优化. jenkins 工具平台,运维核心, 自由风格工程,maven风格项目,流水线项目, 流水线(pipeline) mavenpom.xmlta…