Tokitsukaze and Average of Substring

devtools/2024/9/20 6:07:32/ 标签: 前缀和, 模拟, 字符串, string

原题链接:登录—专业IT笔试面试备考平台_牛客网

目录

1. 题目描述

2. 思路分析

3. 代码实现


1. 题目描述

2. 思路分析

前缀和

开一个int类型的前缀和数组pre[30][N](pre[i][j]表示某字符转成的数字 i 在一段区间的前缀个数。因为字母表有‘a’~'z'共26个字母,所以数组的一维至少开26,一般会多开一些,这里我开了30)。

读入字符串s,遍历字符串s(因为是前缀和的题目,所以下标要从1开始),我们将字符串s(string默认下标是从0开始的,所以之后是s[i-1])中的字符转成数字('a'转成1,'b’转成2,...'z'转成26)。 之后从1~26遍历 j(其实就是在遍历字符‘a’~'z'共26个字符),如果当前字符和上一个字符相同(即j==tmp),我们就让前缀和+1,即pre[j][i]=pre[j][i-1]+1;否则pre[j][i]=pre[j][i-1]。

因为n最大是5000。O(N^2)的复杂度不会超时,所以我们可以通过跑两重循环(外层循环枚举左端点,内层循环枚举右端点)来枚举左右区间 l,r 。再从1~26遍历k(还是从'a'遍历到‘z’),开一个变量tmp记录此时的pre[k][r]-pre[k][l-1](也就是字符k对应的数字在 l~r区间的个数),再通过tmp*(tmp-1) 算相同字符对数,并累加到cnt。不断更新ans的值,取max(ans,1.0*cnt/(r-l+1))即可。

因为是多组测试数据,所以每次循环结束要将pre[i][j]这个二维数组置空。

3. 代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5010;
int pre[30][N]; void solve(){int n; cin>>n;string s; cin>>s;for(int i=1;i<=n;i++){ //前缀和处理出26个字母的前缀和的数量;int tmp=s[i-1]-'a'+1; //字符串下标从0开始for(int j=1;j<=26;j++){  //判断当前枚举的字母是否和上一个字母相同if(j==tmp) pre[j][i]=pre[j][i-1]+1;else pre[j][i]=pre[j][i-1];}}double ans=0;for(int i=1;i<=n;i++){ //枚举每个区间,然后枚举每个字母,计算贡献。for(int j=i+1;j<=n;j++){int l=i,r=j;int cnt=0;for(int k=1;k<=26;k++){int tmp=pre[k][r]-pre[k][l-1];cnt+=tmp*(tmp-1)/2;}ans=max(ans,1.0*cnt/(r-l+1));}}cout<<fixed<<setprecision(6)<<ans<<endl;for(int i=1;i<=26;i++) //多组测试数据,所以每次循环结束将二维数组置空for(int j=1;j<=n;j++)pre[i][j]=0;
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin>>T;while(T--){solve();} return 0;
}


http://www.ppmy.cn/devtools/33767.html

相关文章

STM32 CAN开发步骤

STM32 CAN开发通常涉及以下步骤&#xff1a; 1. 配置CAN外设&#xff1a;根据具体的STM32系列和型号&#xff0c;选择并配置CAN外设。可以使用STM32CubeMX软件进行可视化配置&#xff0c;或者直接编写寄存器级的配置代码。 2. 初始化CAN外设&#xff1a;使用HAL库或者寄存器级…

ELK Stack 8 接入ElasticFlow

介绍 Netflow v5 / v9 / v10&#xff08;IPFIX&#xff09;&#xff0c;支持大部分网络厂商及VMware的分布式交换机。 NetFlow是一种数据交换方式。Netflow提供网络流量的会话级视图&#xff0c;记录下每个TCP/IP事务的信息。当汇集起来时&#xff0c;它更加易于管理和易读。…

【电子通识】为什么IC内部偏置会用到恒流源?

在查看芯片手册时,我们经常会发现芯片框图中出现恒流源。下图所示LM358运算放大器规格书中功能框图的恒流源: 电源芯片SS端内部的恒流源: 其实,IC内部电路的偏置,大多通过恒流源或者恒压源来提供。这与电源波动影响到模拟电路有关,因为电源波动会通过电…

正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-6.5--I.MX6U启动方式

前言&#xff1a; 本文是根据哔哩哔哩网站上“正点原子[第二期]Linux之ARM&#xff08;MX6U&#xff09;裸机篇”视频的学习笔记&#xff0c;在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。…

NPDP产品经理认证报考条件及流程

你是否经常感到无法准确了解用户需求&#xff0c;市场细分让你困扰不已&#xff1f;你是否经常觉得自己创意匮乏&#xff0c;无法持续进行创新&#xff1f;你是否时常发现沟通效率低下&#xff0c;团队协作总是充满摩擦&#xff1f;你是否因为提出的方案被否决而感到失望和挫折…

springboot全局处理sql异常

springboot全局异常处理&#xff0c;不会去拦截sql异常&#xff0c;导致错误返回到前端&#xff0c;&#xff0c;将sql中的字段暴露出来&#xff0c;很危险&#xff0c;&#xff0c; 因为ExceptionHandler 只认我们注入类的名称&#xff0c;&#xff0c;而SQLException不在里面…

mac自定义快捷键打开系统应用

最终效果是达成altg直接打开浏览器&#xff0c;解放双手、再也不需要移动鼠标双击打开应用啦&#xff01;&#xff01;&#xff01;&#xff5e; 1.commandspace输入自动操作 2.选择快速操作 3.选择使用工具、运行appleScrpit 4.输入打开浏览器代码 tell application "G…

Python的主要应用领域

Python是一种广泛应用的高级编程语言&#xff0c;以其强大的功能和简洁的语法受到开发者的青睐。自1991年首次发布以来&#xff0c;Python的应用范围已经从简单的脚本语言发展到支持多种编程范式&#xff08;包括面向对象、命令式、函数式编程和过程式&#xff09;的全功能语言…

仿知乎网站问答源码,开源版

仿知乎网站问答源码&#xff0c;开源版 需要一定动手能力 发文章&#xff0c;发视频&#xff0c;发想法&#xff0c;提问回答&#xff0c;注册登录 开发环境 使用技术&#xff1a;springbootthymeleafRedis&#xff1b; 开发环境&#xff1a;tomcat8.0&#xff0c;jdk8.0, ID…

农作物害虫检测数据集VOC+YOLO格式18975张97类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;18975 标注数量(xml文件个数)&#xff1a;18975 标注数量(txt文件个数)&#xff1a;18975 标…

C语言 | Leetcode C语言题解之第70题爬楼梯

题目&#xff1a; 题解&#xff1a; int climbStairs(int n) {double sqrt5 sqrt(5);double fibn pow((1 sqrt5) / 2, n 1) - pow((1 - sqrt5) / 2, n 1);return (int) round(fibn / sqrt5); }

【R语言数据分析】函数

目录 自定义函数 apply函数 分类汇总函数aggregate 自定义函数 R语言中的自定义函数更像是在自定义一种运算规则。 自定义函数的语法是 函数名 函数体 } 比如 表示定义了一个名为BMI_function的函数&#xff0c;这个函数代表了一种运算规则&#xff0c;就是把传入的x和…

游戏

Game {\color{White}\colorbox{Red}{你能AKIOI吗&#xff08;点击&#xff09;}}你能AKIOI吗&#xff08;点击&#xff09;​ {\color{White}\colorbox{Orange}{正常的2048}}正常的2048​ {\color{White}\colorbox{Yellow}{名称竞技场}}名称竞技场​ {\color{White}\colorb…

解决Uncaught TypeError: Cannot read properties of null (reading ‘getAttribute‘)

问题&#xff1a; 用了element ui 的echart ,初始化时候找不到指定id的元素&#xff0c;导致的问题&#xff0c;如下 浏览器控制台输出的错误信息如下 Echars echarts.min.js:22 Uncaught TypeError: Cannot read properties of null (reading getAttribute)at echarts.min.…

python数据分析——大数据和云计算

大数据和云计算 前言一、大数据二、大数据定义三、数据存储单位四、大数据存储技术五、大数据应用技术六、大数据特征七、数据容量八、数据类型的多样性8.1结构化数据8.2半结构化数据8.3非结构化数据 九、获取数据的速度十、可变性十一、真实性十二、复杂性十三、价值十四、云计…

19 内核开发-内核源码编译

19 内核开发-内核源码编译 (1)开始准备 安装好virtual box ubuntu 系统后&#xff0c;即可下载内核代码&#xff0c;进行编译 历史内核源码地址&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/kernel/v5.x/ 下载 linux-5.10.102.tar.gz 的包,可以使用wget 命令 创建编译目…

笔记12-远程服务器上配置linux深度学习C++环境全过程记录(笔记1和2的同样环境第3次配置)

&#xff08;笔记1和2在windows上装的同样环境在远程服务器上配置&#xff09; 文章目录 conda create -n zgp_m3dm_main python3.8&#xff08;失败&#xff09;反向代理[笔记10-linux服务器可以通过SSH连接但是没法上网](https://editor.csdn.net/md/?articleId137644653)c…

练习题(2024/5/5)

1左叶子之和 给定二叉树的根节点 root &#xff0c;返回所有左叶子之和。 示例 1&#xff1a; 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中&#xff0c;有两个左叶子&#xff0c;分别是 9 和 15&#xff0c;所以返回 24示例 2: 输入: root [1] 输…

【实时数仓架构】方法论

笔者不是专业的实时数仓架构&#xff0c;这是笔者从其他人经验和网上资料整理而来&#xff0c;仅供参考。写此文章意义&#xff0c;加深对实时数仓理解。 一、实时数仓架构技术演进 1.1 四种架构演进 1&#xff09;离线大数据架构 一种批处理离线数据分析架构&#xff0c;…

Istio基础知识

一、什么是Istio Istio 提供⼀种简单的⽅式来为已部署的服务建⽴⽹络&#xff0c;该⽹络具有 负载均衡、服务间认证、监控等功能&#xff0c;只需要对服务的代码进⾏⼀点或不需要做任何改动。想要让服务⽀持 Istio&#xff0c;只需要在您的环境中部署⼀个特殊的 sidecar 代 理&…