第十四届省赛大学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技术,以创造新型的艺术表…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...
