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

测试微信模版消息推送

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

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;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】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...