当前位置: 首页 > 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;以创造新型的艺术表…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...