第十四届省赛大学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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1323676.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

JavaSE-11笔记【多线程2(+2024新)】

文章目录 6.线程安全6.1 线程安全问题6.2 线程同步机制6.3 关于线程同步的面试题6.3.1 版本16.3.2 版本26.3.3 版本36.3.4 版本4 7.死锁7.1 多线程卖票问题 8.线程通信8.1 wait()和sleep的区别&#xff1f;8.2 两个线程交替输出8.3 三个线程交替输出8.4 线程通信-生产者和消费者…

单片机家电产品学习记录--IO推挽输出

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 单片机家电产品–IO推挽输出 前言 记录学习单片机家电产品内容 已转载记录为主 一、知识点 1 单片机IO口科普&#xff1a;推挽输出、开漏输出详解 推挽输出既可以输出低…

数据分析,Pandas 软件包详解与应用示例

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir 在中土大地上&#xff0c;有一位名为"数据剑客"的江湖人士&#xff0c;他手持一柄闪烁着银光的利剑&#xff0c;剑法犀利&…

Python向带有SSL/TSL认证服务器发送网络请求小实践(附并发http请求实现asyncio+aiohttp)

1. 写在前面 最近工作中遇到这样的一个场景&#xff1a;给客户发送文件的时候&#xff0c;为保证整个过程中&#xff0c;文件不会被篡改&#xff0c;需要在发送文件之间&#xff0c; 对发送的文件进行签名&#xff0c; 而整个签名系统是另外一个团队做的&#xff0c; 提供了一…

RC滤波电路

RC滤波电路 综述&#xff1a;本文简单讲述了RC低通滤波电路和RC高通滤波电路。 滤波电路是指过滤输入信号中不需要的信号&#xff0c;保留需要的信号。 一、RC低通滤波电路 1.定义&#xff1a;RC低通滤波电路&#xff1a;保留低频信号&#xff0c;衰减高频信号。 2.截止频率…

GBK文件批量转UTF-8,python脚本

import os import codecsdef convert_encoding(file_path):try:# 尝试以gb18030编码打开文件并读取内容with codecs.open(file_path, r, gb18030) as f:content f.read()except UnicodeDecodeError:# 如果出现解码错误&#xff0c;尝试使用utf-8编码打开文件with codecs.open(…

Beaver Builder Pro v2.8.0.6:最佳的WordPress页面构建器插件

如果你正在寻找一个能帮助你轻松创建具有专业外观的网站的工具&#xff0c;那么Beaver Builder Pro v2.8.0.6就是你的最佳选择。这个高级WordPress插件提供了一个直观的前端可视化页面构建器&#xff0c;让你可以通过拖放元素来快速构建无限的自定义帖子和页面。 Beaver Buil…

重磅发布!2024中国快消企业数字化转型:增长密码与实战解析

目 录 一、导语 二、2024快消行业趋势&#xff1a;深刻的供应链变革 三、快消企业如何构建全渠道数字化营销能力&#xff1f; 四、快消企业数字化转型案优秀案例 案例一&#xff1a;杨国福用CRM构建招商加盟数字化管理 案例二&#xff1a;德庄集团&#xff1a;CRM系统助…

认识什么是Git

目录 1. 认识Git 1.1. 问题引入 1.2. 概念 1.3. 作用 1.4. 如何学 1.5. Git 安装 1.6. Git配置用户信息 2. Git仓库 2.1. Git 仓库&#xff08;repository&#xff09; 2.2. 创建 2.3. 需求 3. Git的三个区域 3.1. Git 使用时的三个区域 3.2. 工作区的内容&#…

备战蓝桥杯---DP刷题2

1.树形DP&#xff1a; 即问那几个点在树的直径上&#xff0c;类似ROAD那题&#xff0c;我们先求一下每一个子树根的子树的最大值与次大值用d1,d2表示&#xff0c;直径就是d1d2的最大值&#xff0c;那么我们如何判断是否在最大路径上&#xff0c;其实就是看一下从某一点出发的所…

聊一聊单点登录

互联网工程师 一、单点登录的概念 单点登录&#xff08;Single Sign-On&#xff0c;简称SSO&#xff09;是一种身份认证和授权技术&#xff0c;旨在解决用户在访问多个应用系统时需要重复登录的问题。该技术允许用户在一个应用系统中完成登录后&#xff0c;就可以访问其他相互信…

地表径流分布数据/水文站点分布/降雨量分布/辐射分布数据

引言 大气降水落到地面后&#xff0c;一部分蒸发变成水蒸气返回大气&#xff0c;一部分下渗到土壤成为地下水&#xff0c;其余的水沿着斜坡形成漫流&#xff0c;通过冲沟&#xff0c;溪涧&#xff0c;注入河流&#xff0c;汇入海洋。这种水流称为地表径流。 正文 数据简介 来自…

Linux简单介绍

Linux简单介绍 编译器VMware虚拟机Ubuntu——LinuxOS为什么使用LinuxOS&#xff1f; 目录结构Windows目录结构Linux操作系统home是不是家目录&#xff1f; Linux常用命令终端命令行提示符与权限切换命令tab 作用&#xff1a;自动补全上下箭头pwd命令ls命令mkdir命令touch命令rm…

基于SSM的师生交流平台

目录 背景 技术简介 系统简介 界面预览 背景 传统的师生互动平台主要依赖于面对面的线下交流&#xff0c;用户必须亲自到场以获取和交流相关信息。然而&#xff0c;随着信息技术的广泛传播&#xff0c;众多教育机构开始转向线上发展&#xff0c;寻求更多样化的发展途径。线…

QML嵌套页面的实现学习记录

StackView是一个QML组件&#xff0c;用于管理和显示多个页面。它提供了向前和向后导航的功能&#xff0c;可以在堆栈中推入新页面&#xff0c;并在不需要时将页面弹出。 ApplicationWindow {id:rootvisible: truewidth: 340height: 480title: qsTr("Stack")// 抽屉:…

计算机的发展历程

本文 我们来说说计算机的发展历程 世界上第一台计算机 1946年2月世界上第一台计算机埃尼阿克ENIAC (Electronic Numerical Integrator AndComputer 电子数字积分式计算机) 在美国诞生 是由宾夕法尼亚大学物理学家约翰.莫克利(J.Mauchly) 和工程师普雷斯伯.埃克特(J.P.Eckert…

redis事务(redis features)

redis支持事务&#xff0c;也就是可以在一次请求中执行多个命令。redis中的事务主要是通过MULTI和EXEC这两个命令来实现的。 MULTI命令用来开启一个事务&#xff0c;事务开启之后&#xff0c;所有的命令就都会被放入到一个队列中&#xff0c;最后通过一个EXEC命令来执行事务中…

windows@软件显示模糊@屏幕显示器分辨率和精细度

文章目录 refsDPIPPIPPI (Pixels Per Inch)DPI (Dots Per Inch) 屏幕尺寸数windows中DPI设置对单个应用设置DPI兼容性设置使用系统全局设置 获取屏幕(监视器)信息&#x1f47a;获取监视器的型号pnp 监视器windows 获取屏幕分辨率 高分辨率屏幕高分辨率和高精细度屏幕&#x1f4…

数字化赋能农业创新:数字乡村促进农村产业融合

随着信息技术的迅猛发展和广泛应用&#xff0c;数字化已经成为推动农业创新发展的重要引擎。数字乡村建设通过引入现代信息技术&#xff0c;为农业产业带来了前所未有的发展机遇&#xff0c;促进了农村产业的深度融合与升级。本文将从数字化赋能农业创新的角度&#xff0c;探讨…

ubuntu安装sublime3并设置中文

安装Sublime Text 3 在Ubuntu上安装Sublime Text 3可以通过以下步骤进行&#xff1a; 打开终端。 导入Sublime Text 3的GPG密钥&#xff1a; wget -qO- https://download.sublimetext.com/sublimehq-pub.gpg | sudo apt-key add - 添加Sublime Text 3的存储库&#xff1a; …