Tokitsukaze and Average of Substring

server/2024/9/20 1:30:31/ 标签: 前缀和, 模拟, 字符串, 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/server/30655.html

相关文章

系统架构设计师错题集

在实时操作系统中&#xff0c;两个任务并发执行&#xff0c;一个任务要等待另一个任务发来消息&#xff0c;或建立某个条件后再向前执行&#xff0c;这种制约性合作关系被称为任务的&#xff08;9&#xff09;。 (9)A.同步 B.互斥 C.调度 D.执行 【答案】A 【解析】本题考查…

智慧能源数据监控平台

随着科技的飞速发展&#xff0c;能源管理已逐渐从传统的粗放型向精细化、智能化转变。在这个转型过程中&#xff0c;HiWoo Cloud平台的智慧能源数据监控平台以其独特的技术优势和创新理念&#xff0c;正引领着能源管理的新潮流。 一、智慧能源数据监控平台的概念 智慧能源数据…

硬盘选购指南

转载请注明出处&#xff01; author karrysmile date 2024年5月3日19:10:52 结论 先给用途分类和价格表 前置知识 没有不好的品牌&#xff0c;只有不好的系列。不用认准哪个品牌就不好&#xff0c;认准口碑好&#xff0c;稳定性好的系列买。&#xff08;杂牌别买&#xff0…

DFR初识

【0】前言 【1】什么Web的开发模式 web开发模式 目前主流的web开发模式有两种&#xff1a; 基于服务端渲染的传统web开发模式 - -前后端混合&#xff1a;BBS项目&#xff0c;图书管理系统-模板语言&#xff1a;dtl-flask&#xff0c;fastapi-go gin-vue&#xff0c;react-微信…

[报错解决]Starting zookeeper ... already running as process 15400.

报错一 ZooKeeper JMX enabled by default Using config: /usr/local/zookeeper-cluster/zookeeper-1/bin/../conf/zoo.cfg Starting zookeeper ... already running as process 15400.解决 netstat -anp | grep 端口号 # 如果集群没有启动&#xff0c;那么该端口不应该被占…

Jenkins持续化集成

Jenkins是一个用于持续集成和持续交付的开源自动化服务器。通过Jenkins&#xff0c;开发团队可以自动化构建、测试和部署他们的项目。下面是一个简单的示例&#xff0c;介绍如何在Jenkins中设置一个基本的持续集成流程。 假设你已经在Jenkins中创建了一个名为"MyProject&…

数据结构——循环结构:for循环

今天是星期五&#xff0c;明天休息&#xff0c;后天补课&#xff0c;然后就是运动会&#xff0c;接着是放假。&#xff08;但这些都和我没关系啊&#xff0c;哭死&#xff01;&#xff09;今天脑袋难得清醒一会儿&#xff0c;主要是醒的比较早吧&#xff0c;早起学了一会&#…

[C++基础学习]----04-一维数组和二维数组详解

前言 在C中&#xff0c;数组是一种用来存储相同类型元素的数据结构。一维数组是最简单的数组形式&#xff0c;它由一系列按顺序存储的元素组成。二维数组则是由一维数组构成的数组&#xff0c;可以看作是一堆一维数组堆叠在一起形成的矩阵。 正文 01-数组简介 一维数组和二维…

Unity 问题之 开发应用在设备上运行闪屏花屏问题的分析处理

Unity 问题之 开发应用在设备上运行闪屏花屏问题的分析处理 目录 Unity 问题之 开发应用在设备上运行闪屏花屏问题的分析处理 一、简单介绍 二、问题现象 三、问题分析 四、使用空后处理&#xff0c;解决闪屏花屏的显示问题 五、空后处理完整代码 一、简单介绍 Unity 在…

json.parse(json.stringify)的弊端

json.parse(json.stringify)的弊端使用JS0N.parse(JS0W.stringify())进行深拷贝对象时&#xff0c;存在一些弊端: 1.无法拷贝值为 umdefined的属性:在序列化(stringiy)阶段&#xff0c;如果对象中某个属性的值为 umdefined&#xff0c;那么这个属性会被忽略&#xff0c;不会出现…

文档笔记上线

Hello&#xff0c;我是"小恒不会java", 这些文档将会在后续依次开源&#xff0c;本文会不定时更新公布文档源代码地址 Matlab app designer java SpringBoot Django

R语言贝叶斯方法在生态环境领域中的应用

贝叶斯统计已经被广泛应用到物理学、生态学、心理学、计算机、哲学等各个学术领域&#xff0c;其火爆程度已经跨越了学术圈&#xff0c;如促使其自成统计江湖一派的贝叶斯定理在热播美剧《The Big Bang Theory》中都要秀一把。贝叶斯统计学即贝叶斯学派是一门基本思想与传统基于…

Tomcat PUT方法任意写文件漏洞(CVE-2017-12615)

1 漏洞原理 在Apache Tomcat服务器中&#xff0c;PUT方法通常用于上传文件。攻击者可以通过发送PUT请求&#xff0c;将恶意文件上传到服务器。 当攻击者发送PUT请求时&#xff0c;Tomcat服务器会将请求中的数据写入指定的文件。如果攻击者能够控制文件路径&#xff0c;那么他们…

【强训笔记】day7

NO.1 思路&#xff1a;双指针模拟&#xff0c;begin表示最长数字字符串最后一个字符&#xff0c;而len表示数字字符串的长度&#xff0c;i用来遍历&#xff0c;如果为数字&#xff0c;那么定义j变量继续遍历&#xff0c;直到不为数字&#xff0c;i-j如果大于len&#xff0c;就…

HTML中input输入框(详解输入框的用法)

目录 一、input介绍 1.概念 2.好处 3.用法 4.应用 二、input语法 1.文本输入框 (type"text") 2.密码输入框 (type"password") 3.数字输入框 (type"number") 4.电子邮件输入框 (type"email") 5.复选框 (type"checkbox&…

想赚钱?别只打工了!这6个副业适合普通人,轻松开启副业人生

身处这个飞速发展的时代&#xff0c;人们越来越渴望在工作之余寻找额外的收入来源。如果你也厌倦了日复一日的单调工作&#xff0c;希望在工作之余开辟一条新的财富之路&#xff0c;那么这篇文章将为你揭示几个既简单又实用的副业选择&#xff0c;让你的钱包鼓起来&#xff0c;…

匠心精神与创新力量:构筑网络安全的新防线

一、匠心精神在网络安全中的重要性 匠心精神代表着对工作的专注和对质量的极致追求。在网络安全领域&#xff0c;这意味着对每一个安全漏洞的深入挖掘&#xff0c;对每一项安全技术的精心打磨。亿林网络李璐昆的提名&#xff0c;正是对其在网络安全领域匠心精神的认可。 二、…

软工导论第五章 总体设计

总体设计过程&#xff1a;系统设计阶段确定系统的具体实现方案&#xff1b;结构设计阶段确定软件结构 文章目录 5.1 软件设计过程 5.2 设计原理 5.2.1 模块化与模块独立 5.2.3 逐步求精 5.3.4 信息隐藏 5.3.5 局部化 5.4 度量模块独立性的标准&#xff08;低耦合&#x…

基于STM32的最小系统电路设计(STM32F103C8T6为例)

前言&#xff1a;本篇博客为嵌入式硬件领域的文章&#xff0c;对 STM32 的最小系统电路设计进行教学。本篇博客以嘉立创 EDA&#xff08;标准版&#xff09;进行绘制 STM32F103C8T6 的最小系统电路 PCB 板&#xff0c;STM32 的最小系统通常包括&#xff1a;微控制器、时钟电路、…

下载Node.js及其他环境推荐nvm

文章目录 项目场景&#xff1a;下载Node.js环境配置配置环境变量 安装脚手架安装依赖安装淘宝镜像安装 cnpm&#xff08;我需要安装&#xff09;nvm 安装 Node.js &#xff08;推荐&#xff09; 项目场景&#xff1a; 提示&#xff1a;这里简述项目相关背景&#xff1a; 项目…