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

第十四届省赛大学B组(C/C++)子串简写

原题链接:子串简写

程序猿圈子里正在流行一种很新的简写方法:

对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。

例如 internationalization 简写成 i18nKubernetes 简写成 K8sLanqiao 简写成 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++)子串简写

原题链接&#xff1a;子串简写 程序猿圈子里正在流行一种很新的简写方法&#xff1a; 对于一个字符串&#xff0c;只保留首尾字符&#xff0c;将首尾字符之间的所有字符用这部分的长度代替。 例如 internationalization 简写成 i18n&#xff0c;Kubernetes 简写成 K8s&#…...

深入浅出 -- 系统架构之微服务架构

1.1 微服务的架构特征&#xff1a; 单一职责&#xff1a;微服务拆分粒度更小&#xff0c;每一个服务都对应唯一的业务能力&#xff0c;做到单一职责 自治&#xff1a;团队独立、技术独立、数据独立&#xff0c;独立部署和交付 面向服务&#xff1a;服务提供统一标准的接口&…...

YoloV8改进策略:下采样改进|自研下采样模块(独家改进)|疯狂涨点|附结构图

摘要 本文介绍我自研的下采样模块。本次改进的下采样模块是一种通用的改进方法,你可以用分类任务的主干网络中,也可以用在分割和超分的任务中。已经有粉丝用来改进ConvNext模型,取得了非常好的效果,配合一些其他的改进,发一篇CVPR、ECCV之类的顶会完全没有问题。 本次我…...

Python从0到100(十):Python集合介绍及运用

一、集合定义 定义&#xff1a; 由不同元素组成的集合&#xff0c;集合是一组无序排列 可hash值&#xff0c;可作为字典的key。 特性&#xff1a; 集合的目的是将不同的值存放在一起&#xff0c;不同的集合间用来做关系运算&#xff0c;无须纠结于集合中的单个值。 &#xff0…...

实用技巧:如何取消app的截屏禁用

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

【氮化镓】GaN SP-HEMT的栅极可靠性

概括总结&#xff1a; 本文研究了氮化镓&#xff08;GaN&#xff09;肖特基型p-栅高电子迁移率晶体管&#xff08;GaN SP-HEMT&#xff09;的栅极鲁棒性和可靠性&#xff0c;通过一种新的电路方法评估了在实际转换器中栅极电压&#xff08;VGS&#xff09;过冲波形的栅极电压应…...

Linux基础和进阶用法

Linux是一个广泛使用的开源操作系统&#xff0c;下面是一些Linux基础用法的详细介绍&#xff1a;文件和目录操作&#xff1a;ls&#xff1a;列出文件和目录的详细信息&#xff0c;包括权限、所有者、大小等。cd&#xff1a;切换到指定目录。使用cd ~返回用户主目录&#xff0c;…...

Linux运维-SHELL编程之正则表达式与流编辑处理器

Linux运维-SHELL编程之正则表达式与流编辑处理器 什么是正则表达式 正则表达式是一种用来描述字符序列的强大工具&#xff0c;通常用于字符串的匹配、搜索和替换操作。它由普通字符&#xff08;例如字母、数字&#xff09;和特殊字符&#xff08;称为元字符&#xff09;组成&…...

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之后&#xff0c;假设给son2添加flex:1&#xff0c;那么son2将会占满除son1之外的高度...

Mysql安装(命令方式安装)

下载mysql压缩包 Mysql可以使用界面安装&#xff0c;也可以使用命令的方式安装&#xff0c;今天我们使用命令的方式安装mysql。首先下载mysql压缩包&#xff08;下载地址&#xff1a;https://dev.mysql.com/downloads/mysql/&#xff09;&#xff0c;解压到你想要安装的目录。 …...

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电脑的系统健康&#xff0c;我们需要定期给电脑进行全面清理&#xff0c;清除系统垃圾文件、软件缓存和系统内存。那么好用的Macbook文件清理软件有哪些呢&#xff1f;今天就给大家介绍几款好用的电脑清理软件并介绍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. 三元运算符&#xff1a;7…...

构建集创建、售卖、转让于一体,且基于ERC721 token的NFT平台,从编写智能合约开始(Web3项目四实战之一)

NFT 全称是 non-fungible token(非同质化代币或不可篡改代币)是记录在区块链上的唯一数字标识符,用于证明所有权和真实性。NFT 的所有权记录在区块链中,所有者可以转让,从而允许 NFT 出售和交易。任何人都可以创建 NFT,创建 NFT 几乎不需要任何编码技能。NFT 通常包含对艺…...

跨境金融区块链服务平台

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

运筹学经典问题(八):CVRP和VRP-TW

文章目录 问题描述问题建模决策变量数学建模基于容量的消除子环的约束 &#xff08;load-based SECs&#xff09; CVRP完整的数学模型加上时间窗限制的CVRP 问题描述 给定一个图&#xff0c;图上的点代表客户&#xff0c;边代表客户之间的路线&#xff0c;边的权重代表客户之间…...

AI与技术美术(TechArt)

AI技术与TA 人工智能&#xff08;AI&#xff09;技术在技术美术&#xff08;TechArt&#xff09;领域的应用&#xff0c;为创业者开辟了一片新的天地。技术美术作为一个跨学科领域&#xff0c;融合了传统美术和现代技术&#xff0c;特别是AI技术&#xff0c;以创造新型的艺术表…...

二叉树层序遍历 及相关题目

1&#xff0c;力扣102 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]]示例…...

【前端面试3+1】11 http和https有何不同及https的加密过程、数组有哪些方法及作用、tcp三次握手四次挥手、【分发饼干】

一、http和https有何不同&#xff1f;https的加密过程 1、不同&#xff1a; HTTP和HTTPS的主要区别在于安全性。HTTP是超文本传输协议&#xff0c;是一种用于传输数据的协议&#xff0c;但是传输的数据是明文的&#xff0c;容易被窃听和篡改。而HTTPS是在HTTP基础上加入了SSL/T…...

替代 Redis 和 Memcached:25 倍吞吐量! | 开源日报 No.213

dragonflydb/dragonfly Stars: 22.4k License: NOASSERTION Dragonfly 是一个内存数据存储&#xff0c;适用于现代应用工作负载&#xff0c;可替代 Redis 和 Memcached。与传统的内存数据存储相比&#xff0c;Dragonfly 提供了 25 倍的吞吐量、更高的缓存命中率和更低尾部延…...

Qt与OpenCV实现图像模板匹配

在 Qt 中使用 OpenCV 实现模板匹配可以通过集成 OpenCV 库和使用其相关函数来完成。以下是一般的步骤&#xff1a; 安装 OpenCV&#xff1a;首先&#xff0c;确保你已经安装了 OpenCV 库&#xff0c;并将其配置到你的开发环境中。 创建 Qt 项目&#xff1a;使用 Qt creator 或…...

OpenHarmony实战:CMake方式组织编译的库移植

以double-conversion库为例&#xff0c;其移植过程如下文所示。 源码获取 从仓库获取double-conversion源码&#xff0c;其目录结构如下表&#xff1a; 表1 源码目录结构 名称描述double-conversion/cmake/CMake组织编译使用到的模板double-conversion/double-conversion/源…...

Linux云计算之Linux基础3——Linux基本认识操作

1、终端 终端(terminal)&#xff1a;人和系统交互的必要设备&#xff0c;人机交互最后一个界面&#xff08;包含独立的输入输出设备&#xff09; 物理终端(console)&#xff1a;直接接入本机器的键盘设备和显示器虚拟终端(tty)&#xff1a;通过软件方式虚拟实现的终端。它可以…...

canvas画图,画矩形、圆形、直线可拖拽移动,可拖拽更改尺寸大小

提示&#xff1a;canvas画图&#xff0c;画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖拽移动 文章目录 前言一、画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖拽移动总结 前言 一、画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖…...

Github 2024-04-04 Go开源项目日报 Top10

根据Github Trendings的统计,今日(2024-04-04统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Go项目10Python项目1Prometheus监控系统和时间序列数据库 创建周期:4149 天开发语言:Go协议类型:Apache License 2.0Star数量:52463 个Fork…...

并发与限流实战:如何利用 RabbitMQ 在 SpringBoot 应用中实现并发控制与流量限制

在高并发场景下&#xff0c;如大促销、秒杀等&#xff0c;我们可以采用 RabbitMQ 配合 SpringBoot 来实现并发控制与流量限制。你可以将 RabbitMQ 作为一个缓冲区&#xff0c;暂存大量并发请求&#xff0c;然后消费者可以根据自身处理能力去处理这些请求。下面就以一个高并发订…...

VUE实现下一页的功能

实现步骤&#xff1a;1、确定分页参数&#xff1a;确定当前页码和每页显示的数量&#xff1b;2、获取数据&#xff1a;使用vue的axios或其他http库向后端发送请求&#xff0c;传递当前页码和每页显示的数量作为参数&#xff1b;3、更新数据&#xff1a;在vue组件中&#xff0c;…...

中国网站设计欣赏/关键词优化收费标准

首先说明一下&#xff0c;第一次写博客&#xff0c;难免会有纰漏&#xff0c;如果有不足的地方希望大家指正&#xff0c;谢谢生成器都有什么用处生成器可以用来存放一些数据&#xff0c;像列表元组那样&#xff0c;在生成器的高端用法里被用作协程(py3.4以前)&#xff0c;可以用…...

珠海网站建设 金蝶/手机网站建设

在Java中&#xff0c;提供了对信号量Semaphore的支持。Semaphore类是一个计数信号量&#xff0c;必须由获取它的线程释放&#xff0c;通常可以用于限制并发访问的线程数目。Semaphore的使用获得Semaphore对象public Semaphore(int permits, boolean fair)permits&#xff1a;初…...

自己免费建设网站/寻找客户的渠道和方法

之前一直用图形化界面&#xff0c;加上考研期间也没动&#xff0c;竟然把我的数据库密码给忘了&#xff0c;无地自容.......找了找教程&#xff0c;问题如下&#xff1a;MySQL从低版本向高版本迭代变化的过程&#xff0c;越来越严谨的安全性是其一大特点之一&#xff0c;在版本…...

微信开放平台登录入口/seo关键词排名优化如何

记录一下 今天使用Hexo GitHub搞个博客&#xff0c;在使用npm全局安装hexo的时候出现了这个问题,zsh:command not found: hexo npm install -g hexo hexo init myBlog 复制代码解决 两种方法 reinstall npm with a version manager 重新安装npmchange npms default directory m…...

nas做网站服务器/今天发生的重大新闻

写在前面 官方文档地址 ES 的查询语言称为 DSL 即 Domain Specific Language 领域专用语言。 本文查询将以下列索引结构为例子展开。 PUT /dying_gq_bookstore {"mappings": {"properties": {"book_id": {"type": "long"…...

wordpress数据库软件/百度推广优化技巧

LM35温度传感器驱动 文章目录 LM35温度传感器驱动1、LM35介绍2、硬件准备3、软件准备4、驱动实现1、LM35介绍 LM35 系列是精密集成电路温度传感器,其输出电压与摄氏(摄氏度)温度成线性比例。 因此,LM35 优于以开尔文校准的线性温度传感器,因为用户无需从其输出中减去较大…...