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

第十四届蓝桥杯省赛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;
}

【在线测评】

在这里插入图片描述

相关文章:

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

题目大意 给定字符串 s s s&#xff0c;字符 a , b a, b a,b&#xff0c;问字符串 s s s 中有多少个 a a a 开头 b b b 结尾的子串。 解题思路 20pts 使用二重循环枚举左端点和右端点&#xff0c;判断是否为 a a a 开头 b b b 结尾的字符串&#xff0c;是则答案加一…...

实现Java Web应用的高性能负载均衡方案

实现Java Web应用的高性能负载均衡方案 大家好&#xff0c;我是微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 在高并发的网络环境中&#xff0c;负载均衡是确保Web应用程序高性能和可靠性的关键策略之一。本文将探讨如何…...

医学预测模型web APP的制作建议

医学预测模型web APP的制作建议 医学预测模型类web APP定义为承载预测模型而便利预测模型临床应用的可视化客户端。 医学预测模型类web APP的功能是衔接预测模型和临床实践&#xff0c;让用户正确地&#xff0c;方便地使用预测模型并恰当地理解预测模型的结果&#xff0c;在此…...

gitlab每日备份以及restore

gitlab服务有非常简洁的每日备份命令&#xff0c; 从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.在数据集增加累加变量值&#xff08;SUM&#xff09; 求和语句(SUM STATEMENT)&#xff1a;variableexpression variable是累积求和的变量名&#xff0c;为数值型&#xff0c;默认初始值为0&#xff1b;该variable值则会保留到一个观测 当expression有缺失值&#xff0c;在求…...

kafka--发布-订阅消息系统

1. Kafka概述 1. kafka是什么 kafka是分布式的、高并发的、基于发布/订阅模式的消息队列软件系统。 kafka中的重要组件 Producer&#xff1a;消息生产者&#xff0c;发布消息到Kafka集群的终端或服务Consume&#xff1a;消费者&#xff0c;从Kafka集群中消费消息的终端或服…...

2024最新软件测试面试题。内附答案+文档

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、你以前工作时的测试流程是什么&#xff1f; 参考答案&#xff1a;&#xff08;灵活回答&…...

新加坡很火的slots游戏代投Facebook广告新流量趋势

新加坡很火的slots游戏代投Facebook广告新流量趋势 在新加坡这片充满活力的土地上&#xff0c;Slots游戏以其独特的魅力和吸引力&#xff0c;迅速成为了许多玩家的心头好。而Facebook&#xff0c;作为全球最大的社交媒体平台之一&#xff0c;为Slots游戏的推广提供了得天独厚的…...

C++ 实现字符串逆序

C 实现字符串逆序 思路&#xff1a; 输入一个字符串。使用双指针法&#xff0c;交换字符串的首尾字符&#xff0c;逐步向中间移动。输出逆序后的字符串。 #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.打开注册表&#xff0c;验证结果 一、前言 在Windows操作系统中&#xff0c;将exe文件的路径添加到注册表下&#xff0c;主要用于实现程序的开机自动运行功能。 注册表路径为&#xf…...

SQL使用注意事项

作为开发人员日常最为熟悉的工具sql。但是在实际使用中&#xff0c;有一些坑需要尽量避免&#xff0c;本文是对一些常用注意事项的总结 查询需要的。不要全部都查询。禁止使用存储过程&#xff0c;禁止使用外键。使用sql进行计算&#xff0c;要小心。&#xff08;数据量大的情况…...

uniapp小程序IOS端,uni.createInnerAudioContext()无声音

可能的问题 路径中有中文字符需要使用uni.getBackgroundAudioManager()播放其他问题 解决办法 首先我的路径中没有中文字符&#xff0c;如果有的&#xff0c;可能需要转义一下或者干脆不使用中文字符&#xff0c;第二个也是从其他博客中看到的&#xff0c;我这边分享一下我的…...

第二节-K8s词汇表

关键字词汇表 https://kubernetes.io/zh-cn/docs/reference/glossary/?fundamentaltrue API Group (API 组)Kubernetes API 中的一组相关路径。 API 服务器亦称作:kube-apiserver API 服务器是 Kubernetes 控制平面的组件&#xff0c; 该组件负责公开了 Kubernetes API&…...

命令行运行git reflog(reference log)报错的解决办法

文章目录 1. 检查 Git 是否已安装2. 检查 PATH 环境变量3. 重新安装 Git 在Git中&#xff0c; reflog的英文全称是 “ reference log”。意思是 引用日志&#xff08;参考日志&#xff09;。它记录了本地仓库中HEAD和分支引用所指向的提交的变更历史。这包括了你所有的提交&…...

python3 imwrite 中文路径不成功解决方法

filename 中文路径 #cv2.imwrite(filename, frame) cv2.imencode(.jpg, frame)[1].tofile(filename)...

tapd 与国内外主流的8大项目管理软件大对比

对比Tapd与8大项目管理工具&#xff1a;PingCode、Worktile、Redmine、Teambition、广联达、Jira、禅道、飞书。 Tapd 是腾讯推出的一款敏捷开发管理工具&#xff0c;特别适合那些需要高效协作和快速迭代的敏捷开发团队。它支持多种敏捷方法论&#xff0c;包括Scrum和Kanban&am…...

IP地址配置

1.为虚拟机配置IP地址&#xff0c;网关&#xff0c;DNS 例如&#xff1a;手动给虚拟机配置IP地址为 192.168.5.50/24&#xff1b;网关地址为&#xff1a;192.168.5.2&#xff1b;DNS地址为&#xff1a;192.168.5.2 解题步骤如下&#xff1a; #配置IP地址 [rootlocalhost ~]#…...

【C#】ProgressBar进度条异步编程思想

1.控件介绍 进度条通常用于显示代码的执行进程进度&#xff0c;在一些复杂功能交互体验时告知用户进程还在继续。 在属性栏中&#xff0c;有三个值常用&#xff1a; Value表示当前值&#xff0c;Minimum表示进度条范围下限&#xff0c;Maximum表示进度条范围上限。 2.简单实…...

深入浅出3D感知中的优化与基于学习的技术1(原创系列)

近期几乎看了所有有关NERF技术论文&#xff0c;本身我研究的领域不在深度学习技术方向&#xff0c;是传统的机器人控制和感知。所以总结了下这部分基于学习的感知技术&#xff0c;会写一个新的系列教程讲解这部分三维感知技术的发展到最新的技术细节&#xff0c;并支持自己最近…...

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

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

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Android15默认授权浮窗权限

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

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...