第十四届蓝桥杯省赛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 a…b 就是合法的字符串。统计某个位置的左侧有几个字符 a a a,我们可以使用前缀和算法进行维护。
法二
我们可以去遍历整个字符串,对于每个 a a a 字符的右侧有几个字符 b b b,那么这些 a … b a \dots b a…b 都是合法的字符串。统计某个位置之后字符 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;
}
【在线测评】

相关文章:
第十四届蓝桥杯省赛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 结尾的字符串,是则答案加一…...
实现Java Web应用的高性能负载均衡方案
实现Java Web应用的高性能负载均衡方案 大家好,我是微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在高并发的网络环境中,负载均衡是确保Web应用程序高性能和可靠性的关键策略之一。本文将探讨如何…...
医学预测模型web APP的制作建议
医学预测模型web APP的制作建议 医学预测模型类web APP定义为承载预测模型而便利预测模型临床应用的可视化客户端。 医学预测模型类web APP的功能是衔接预测模型和临床实践,让用户正确地,方便地使用预测模型并恰当地理解预测模型的结果,在此…...
gitlab每日备份以及restore
gitlab服务有非常简洁的每日备份命令, 从production的gitlab的每日备份中restore到backup环境也非常方便。 一、Production gitlab每日备份 1. Production gitlab环境上编写脚本 cat /root/gitlab_bak.shgitlab-rake gitlab:backup:create > /var/opt/gitl…...
2024-07-05 base SAS programming学习笔记9(variables)
1.在数据集增加累加变量值(SUM) 求和语句(SUM STATEMENT):variableexpression variable是累积求和的变量名,为数值型,默认初始值为0;该variable值则会保留到一个观测 当expression有缺失值,在求…...
kafka--发布-订阅消息系统
1. Kafka概述 1. kafka是什么 kafka是分布式的、高并发的、基于发布/订阅模式的消息队列软件系统。 kafka中的重要组件 Producer:消息生产者,发布消息到Kafka集群的终端或服务Consume:消费者,从Kafka集群中消费消息的终端或服…...
2024最新软件测试面试题。内附答案+文档
🍅 视频学习:文末有免费的配套视频可观看 🍅 点击文末小卡片,免费获取软件测试全套资料,资料在手,涨薪更快 1、你以前工作时的测试流程是什么? 参考答案:(灵活回答&…...
新加坡很火的slots游戏代投Facebook广告新流量趋势
新加坡很火的slots游戏代投Facebook广告新流量趋势 在新加坡这片充满活力的土地上,Slots游戏以其独特的魅力和吸引力,迅速成为了许多玩家的心头好。而Facebook,作为全球最大的社交媒体平台之一,为Slots游戏的推广提供了得天独厚的…...
C++ 实现字符串逆序
C 实现字符串逆序 思路: 输入一个字符串。使用双指针法,交换字符串的首尾字符,逐步向中间移动。输出逆序后的字符串。 #include <iostream> #include <string>using namespace std;void reverseString(string &str) {int …...
【项目实践】贪吃蛇
一、游戏效果展示二、博客目标三、使用到的知识四、Win32 API 介绍 4.1 WIn32 API4.2 控制台程序4.3 控制屏幕上的坐标COORD4.4 GetStdHandle4.5 GetConsoleCursorInfo 4.5.1 CONSOLE_CURSOR_INFO 4.6 SetConsoleCursorInfo4.7 SetConsoleCursorPosition4.8 GetAsyncKeyState 五…...
将exe文件添加到注册表中,实现开机时自动运行
目录 一、前言 二、代码 三、使用步骤 1.编译生成exe文件、 2.以管理员身份运行代码 3.打开注册表,验证结果 一、前言 在Windows操作系统中,将exe文件的路径添加到注册表下,主要用于实现程序的开机自动运行功能。 注册表路径为…...
SQL使用注意事项
作为开发人员日常最为熟悉的工具sql。但是在实际使用中,有一些坑需要尽量避免,本文是对一些常用注意事项的总结 查询需要的。不要全部都查询。禁止使用存储过程,禁止使用外键。使用sql进行计算,要小心。(数据量大的情况…...
uniapp小程序IOS端,uni.createInnerAudioContext()无声音
可能的问题 路径中有中文字符需要使用uni.getBackgroundAudioManager()播放其他问题 解决办法 首先我的路径中没有中文字符,如果有的,可能需要转义一下或者干脆不使用中文字符,第二个也是从其他博客中看到的,我这边分享一下我的…...
第二节-K8s词汇表
关键字词汇表 https://kubernetes.io/zh-cn/docs/reference/glossary/?fundamentaltrue API Group (API 组)Kubernetes API 中的一组相关路径。 API 服务器亦称作:kube-apiserver API 服务器是 Kubernetes 控制平面的组件, 该组件负责公开了 Kubernetes API&…...
命令行运行git reflog(reference log)报错的解决办法
文章目录 1. 检查 Git 是否已安装2. 检查 PATH 环境变量3. 重新安装 Git 在Git中, reflog的英文全称是 “ reference log”。意思是 引用日志(参考日志)。它记录了本地仓库中HEAD和分支引用所指向的提交的变更历史。这包括了你所有的提交&…...
python3 imwrite 中文路径不成功解决方法
filename 中文路径 #cv2.imwrite(filename, frame) cv2.imencode(.jpg, frame)[1].tofile(filename)...
tapd 与国内外主流的8大项目管理软件大对比
对比Tapd与8大项目管理工具:PingCode、Worktile、Redmine、Teambition、广联达、Jira、禅道、飞书。 Tapd 是腾讯推出的一款敏捷开发管理工具,特别适合那些需要高效协作和快速迭代的敏捷开发团队。它支持多种敏捷方法论,包括Scrum和Kanban&am…...
IP地址配置
1.为虚拟机配置IP地址,网关,DNS 例如:手动给虚拟机配置IP地址为 192.168.5.50/24;网关地址为:192.168.5.2;DNS地址为:192.168.5.2 解题步骤如下: #配置IP地址 [rootlocalhost ~]#…...
【C#】ProgressBar进度条异步编程思想
1.控件介绍 进度条通常用于显示代码的执行进程进度,在一些复杂功能交互体验时告知用户进程还在继续。 在属性栏中,有三个值常用: Value表示当前值,Minimum表示进度条范围下限,Maximum表示进度条范围上限。 2.简单实…...
深入浅出3D感知中的优化与基于学习的技术1(原创系列)
近期几乎看了所有有关NERF技术论文,本身我研究的领域不在深度学习技术方向,是传统的机器人控制和感知。所以总结了下这部分基于学习的感知技术,会写一个新的系列教程讲解这部分三维感知技术的发展到最新的技术细节,并支持自己最近…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...
