第十四届省赛大学B组(C/C++)子串简写
原题链接:子串简写
程序猿圈子里正在流行一种很新的简写方法:
对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。
例如 internationalization
简写成 i18n
,Kubernetes
简写成 K8s
,Lanqiao
简写成 L5o
等。
在本题中,我们规定长度大于等于 K 的字符串都可以采用这种简写方法(长度小于 K 的字符串不配使用这种简写)。
给定一个字符串 S 和两个字符 c1 和 c2,请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写?
输入格式
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符 c1 和 c2。
输出格式
一个整数代表答案。
数据范围
对于 20% 的数据,2≤K≤|S|≤10000。
对于 100% 的数据,2≤K≤|S|≤5×10^5。S 只包含小写字母。c1 和 c2 都是小写字母。
|S| 代表字符串 S 的长度。
输入样例:
4
abababdb a b
输出样例:
6
样例解释
符合条件的子串如下所示,中括号内是该子串
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
解题思路:
此题主要是考察前缀和,此题暴力的话只会过部分测试点,会超时。我们定义前缀和presumb[i]表示第i个位置之前(包括第i个位置)有多少个b,这样确定了尾,我们再遍历一遍只要是头,那么就可以利用前缀和求出方案,以下为样例为例。
那么我们怎么求方案数,当我们遍历到第i个位置上的首字符时,题目中要求最短字串为N,那么我们再往后走N-1个,第N-1个及到最后凡是有尾字符的都是一种情况,那么方案数就是presumb[s.zize()-1]-presumb[i+n-2],下面以i=2为例。
AC代码:
#include <iostream>
#include<cstring>
using namespace std;
typedef long long ll;//注意开longlong
const int N=5e5+5;
string s;
char a,b;
ll n,ans,res;
ll presumb[N];
int main()
{cin>>n>>s>>a>>b;for(int i=0;i<s.size();i++){if(s[i]==b) presumb[i]=presumb[i-1]+1;else presumb[i]=presumb[i-1];}for(int i=0;i<s.size();i++){if(s[i]==a&&i+n<=s.size()){res+=presumb[s.size()-1]-presumb[i+n-2];}}cout<<res<<endl;return 0;
}
相关文章:

第十四届省赛大学B组(C/C++)子串简写
原题链接:子串简写 程序猿圈子里正在流行一种很新的简写方法: 对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。 例如 internationalization 简写成 i18n,Kubernetes 简写成 K8s&#…...

深入浅出 -- 系统架构之微服务架构
1.1 微服务的架构特征: 单一职责:微服务拆分粒度更小,每一个服务都对应唯一的业务能力,做到单一职责 自治:团队独立、技术独立、数据独立,独立部署和交付 面向服务:服务提供统一标准的接口&…...
YoloV8改进策略:下采样改进|自研下采样模块(独家改进)|疯狂涨点|附结构图
摘要 本文介绍我自研的下采样模块。本次改进的下采样模块是一种通用的改进方法,你可以用分类任务的主干网络中,也可以用在分割和超分的任务中。已经有粉丝用来改进ConvNext模型,取得了非常好的效果,配合一些其他的改进,发一篇CVPR、ECCV之类的顶会完全没有问题。 本次我…...

Python从0到100(十):Python集合介绍及运用
一、集合定义 定义: 由不同元素组成的集合,集合是一组无序排列 可hash值,可作为字典的key。 特性: 集合的目的是将不同的值存放在一起,不同的集合间用来做关系运算,无须纠结于集合中的单个值。 ࿰…...

实用技巧:如何取消app的截屏禁用
因为我想要在小鹅通App做笔记,但是被小鹅通App禁用截屏了,这真是一个很糟糕的使用体验,虽然可能是为了保护商家权益…… 方法1 可以让商家设置课程可以截屏 方法2 手机root,安装Xposed框架,利用Xposed框架上面的插件我们可以对手机进行高度定制化,而安装Xposed框架的…...

【氮化镓】GaN SP-HEMT的栅极可靠性
概括总结: 本文研究了氮化镓(GaN)肖特基型p-栅高电子迁移率晶体管(GaN SP-HEMT)的栅极鲁棒性和可靠性,通过一种新的电路方法评估了在实际转换器中栅极电压(VGS)过冲波形的栅极电压应…...
Linux基础和进阶用法
Linux是一个广泛使用的开源操作系统,下面是一些Linux基础用法的详细介绍:文件和目录操作:ls:列出文件和目录的详细信息,包括权限、所有者、大小等。cd:切换到指定目录。使用cd ~返回用户主目录,…...
Linux运维-SHELL编程之正则表达式与流编辑处理器
Linux运维-SHELL编程之正则表达式与流编辑处理器 什么是正则表达式 正则表达式是一种用来描述字符序列的强大工具,通常用于字符串的匹配、搜索和替换操作。它由普通字符(例如字母、数字)和特殊字符(称为元字符)组成&…...

openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint
文章目录 openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint256.1 功能描述256.2 语法格式256.3 参数说明 openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint 256.1 功能描述 设置本次查询执行内生效的…...
flex:1的作用是什么?
占满剩余的高度 <div classfather><div classson1></div><div classson2></div> </div>当给father添加display:flex之后,假设给son2添加flex:1,那么son2将会占满除son1之外的高度...

Mysql安装(命令方式安装)
下载mysql压缩包 Mysql可以使用界面安装,也可以使用命令的方式安装,今天我们使用命令的方式安装mysql。首先下载mysql压缩包(下载地址:https://dev.mysql.com/downloads/mysql/),解压到你想要安装的目录。 …...
Vben Admin实战-系统管理之用户管理-(第12节)
系列文章目录 第一节:Vben Admin介绍和初次运行 第二节:Vben Admin 登录逻辑梳理和对接后端准备 第三节:Vben Admin登录对接后端login接口 第四节:Vben Admin登录对接后端getUserInfo接口 第五节:Vben Admin权限-前端控制方式 第六节:Vben Admin权限-后端控制方式 第七节…...
Oracle常规操作
1、查看用户和密码 select username,password from dba_users; --修改用户和密码 alter user system identified by manager; alter user system identified by values 2D594E86F93B17A1; --解锁用户 alter user system account unlock; -- 用SYSDBA身份进入数据库,然…...
「33」如何让你的直播场景增加透视感?
「33」模糊滤镜增强背景画面透视感 在直播中,背景一直是作为一种陪衬而存在的,位于主场景的后面,其实,说得更直白一些,背景的存在就犹如“绿叶”,是为了衬托红花更加艳丽。所以…… 你通过画面背景的调整,可以从整体上对视频或图片的画面进行装饰,有助于增加画面的空间…...

Macbook文件清理软件 Mac电脑清理垃圾文件怎么清理
为了维护Macbook电脑的系统健康,我们需要定期给电脑进行全面清理,清除系统垃圾文件、软件缓存和系统内存。那么好用的Macbook文件清理软件有哪些呢?今天就给大家介绍几款好用的电脑清理软件并介绍Mac电脑清理垃圾文件怎么清理。 一、Macbook…...

【Java基础】Java基础知识整合
文章目录 1. 转义字符2. 变量2.1 字符串与整型相加2.2 byte和short的区别2.3 float和double的区别2.4 char类型2.5 boolean类型2.6 自动类型转换及运算2.7 强制类型转换2.8 String的转换2.9 除法运算2.10 取模规则 3. 自增4. 逻辑运算符5. 赋值运算 6. 三元运算符:7…...
构建集创建、售卖、转让于一体,且基于ERC721 token的NFT平台,从编写智能合约开始(Web3项目四实战之一)
NFT 全称是 non-fungible token(非同质化代币或不可篡改代币)是记录在区块链上的唯一数字标识符,用于证明所有权和真实性。NFT 的所有权记录在区块链中,所有者可以转让,从而允许 NFT 出售和交易。任何人都可以创建 NFT,创建 NFT 几乎不需要任何编码技能。NFT 通常包含对艺…...

跨境金融区块链服务平台
跨境金融服务是因企业及个人跨境经营、交易、投资、往来等活动而产生的资金使用、调拨、配置等需求,而提供的金融服务。近年来,随着我国经济的快速稳步增长和全球化经济一体化的不断深入发展,跨境金融业务增长迅速,监管也开始转化…...

运筹学经典问题(八):CVRP和VRP-TW
文章目录 问题描述问题建模决策变量数学建模基于容量的消除子环的约束 (load-based SECs) CVRP完整的数学模型加上时间窗限制的CVRP 问题描述 给定一个图,图上的点代表客户,边代表客户之间的路线,边的权重代表客户之间…...
AI与技术美术(TechArt)
AI技术与TA 人工智能(AI)技术在技术美术(TechArt)领域的应用,为创业者开辟了一片新的天地。技术美术作为一个跨学科领域,融合了传统美术和现代技术,特别是AI技术,以创造新型的艺术表…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...