【牛客】Tokitsukaze and Average of Substring

原题链接:登录—专业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.rhkb.cn/news/323216.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【使用ChatGPT的API之前】OpenAI API提供的可用模型

文章目录 一. ChatGPT基本概念二. OpenAI API提供的可用模型1. InstructGPT2. ChatGPT3. GPT-4 三. 在OpenAI Playground中使用GPT模型-ing 在使用GPT-4和ChatGPT的API集成到Python应用程序之前&#xff0c;我们先了解ChatGPT的基本概念&#xff0c;与OpenAI API提供的可用模型…

云原生Kubernetes: K8S 1.29版本 部署Harbor

目录 一、实验 1.环境 2.Linux 部署docker compose 3.证书秘钥配置 4.K8S 1.29版本 部署Harbor 5.K8S 1.29版本 使用Harbor 二、问题 1.docker 登录harbor失败 一、实验 1.环境 &#xff08;1&#xff09;主机 表1 主机 主机架构版本IP备注masterK8S master节点1.2…

java报错:使用mybatis plus查询一个只返回一条数据的sql,却报错返回了1000多条

今天遇到一个问题 系统线上问题&#xff0c;经常出现这样的问题&#xff0c;刚重启系统时不报错了&#xff0c;可是运行一段时间又会出现。sql已经写了limit 1&#xff0c;mybatis的debug日志也返回total为1&#xff0c;可是却报错返回了1805条数据 乍一看&#xff0c;感觉太不…

基于Spring Boot的公司OA系统设计与实现

基于Spring Boot的银行OA系统设计与实现 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea 系统部分展示 用户登录界面&#xff0c;在银行OA系统运行后&#x…

基于springboot+jsp+Mysql的商务安全邮箱邮件收发

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

STM32单片机实战开发笔记-PWM波输出频率及占空比配置【wulianjishu666】

单片机物联网开发资料&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1XzodQuML7CqZ4ZKinDGKkg?pwdbgep 提取码&#xff1a;bgep PWM模块测试 功能描述 脉冲宽度调制模式&#xff1a; PWM边沿对齐模式&#xff1a; 向上计数配置 当TIMX_CR1寄存器中的DIR为低的时…

基于Python的LSTM网络实现单特征预测回归任务(TensorFlow)

单特征&#xff1a;数据集中只包含2列&#xff0c;时间列价格列&#xff0c;仅利用价格来预测价格 目录 一、数据集 二、任务目标 三、代码实现 1、从本地路径中读取数据文件 2、数据归一化 3、创建配置类&#xff0c;将LSTM的各个超参数声明为变量&#xff0c;便于后续…

php开发-个人博客项目文件操作类编辑器上传下载删除读写

特地整了个软件 这就舒服了 文件操作类的开发 文件的任意上传&#xff0c;下载&#xff0c;读取&#xff0c;删除操作等 1.文件上传类-任意文件上传 分为三类 1&#xff0c;代码自主编写的 先写一个html的上传表单&#xff0c;这个网上搜索就有 标题看着不够明确啊&#…

【牛客】【模板】差分

原题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 差分模板。 b[0]a[0]; b[1]a[1]-a[0]; b[2]a[2]-a[1]; ...... b[n-1]a[n-1]-a[n-2]; b[n]a[n]-a[n-1]; 差分标记&#xff1a;b[l]k,b…

计算机网络chapter1——家庭作业

文章目录 复习题1.1节&#xff08;1&#xff09; “主机”和“端系统”之间有何不同&#xff1f;列举几种不同类型的端系统。web服务器是一种端系统吗&#xff1f;&#xff08;2&#xff09;协议一词常用来用来描述外交关系&#xff0c;维基百科是如何描述外交关系的&#xff1…

基于Springboot的校园悬赏任务平台(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的校园悬赏任务平台&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…

Codigger:Web应用让开发者拥有更高效的开发之旅

在当今软件开发领域&#xff0c;Web应用以其跨平台、易访问和实时更新的特性&#xff0c;逐渐成为了主流的开发方向。从开发者的视角来看&#xff0c;Codigger借助B/S&#xff08;浏览器/服务器&#xff09;架构和云计算技术&#xff0c;为开发者带来了诸多便利和优势。这些优势…

【负载均衡式在线OJ项目day1】项目结构

一.功能 查看题目列表&#xff0c;在线编程&#xff0c;判题功能&#xff0c;即leetcode的部分功能 二.宏观结构 整个项目是BS模式&#xff0c;客户端是浏览器&#xff0c;和用户交互并向服务器发起请求。 服务端从功能上来说分为两个模块&#xff0c;第一个是OJServer&…

C++ 多态(一)

一、多态定义 同一种操作作用于不同的对象时&#xff0c;可以产生不同的行为。在面向对象编程中&#xff0c;多态性是指通过继承和重写实现的&#xff0c;同一个方法在不同的子类中可以表现出不同的行为。多态性可以提高代码的灵活性和可扩展性&#xff0c;使得程序更易于维护…

盘点企业信息防泄密软件对比|揭秘企业信息防泄密软件好用榜

在当今信息化社会&#xff0c;企业信息防泄密软件的需求日益凸显。这些软件不仅关乎企业的核心竞争力&#xff0c;更直接关系到企业的生死存亡。本文将对市面上几款主流的企业信息防泄密软件进行深入对比分析&#xff0c;以期为企业提供有益的参考。 一、企业信息防泄密软件好…

987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果

解法&#xff1a; 一棵二叉树是完全二叉树的条件是&#xff1a; 对于任意一个结点&#xff0c;如果它有右子树而没有左子树&#xff0c;则这棵树不是完全二叉树。 如果一个结点有左子树但是没有右子树&#xff0c;则这个结点之后的所有结点都必须是叶子结点。 如果满足以上条…

docker学习笔记(三)搭建NFS服务实验

目录 什么是NFS 简单架构​编辑 一.搭建nfs服务器 二.新建共享目录和网页文件 三.设置共享目录 四&#xff1a;创建使用nfs共享目录的卷 五&#xff1a;创建容器使用nfs-web-1卷 六&#xff1a;测试访问 七&#xff1a;是否同步测试 什么是NFS NFS 服务器&#xff1a;ne…

webpack如何自定义一个loader

我们在使用脚手架的搭建项目的时候往往都会帮我们配置好所需的loader&#xff0c;接下来讲一下我们要如何自己写一个loader应用到项目中&#xff08;完整代码在最后&#xff09; 1. 首先搭建一个项目并找到webpack配置文件&#xff08;webpack.config.js&#xff09; 在modul…

95、动态规划-编辑距离

递归暴力解法 递归方法的基本思想是考虑最后一个字符的操作&#xff0c;然后根据这些操作递归处理子问题。 递归函数定义&#xff1a;定义一个递归函数 minDistance(i, j)&#xff0c;表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。 递归终止条件…

无人直播需要什么软件系统?最新AI实景自动无人直播软件:智能化引领直播拓客新时代

随着互联网的快速发展&#xff08;无人直播招商加盟&#xff1a;hzzxar&#xff09;直播行业已经成为商家品牌推广和商品销售的热门方式。近年来&#xff0c;人工智能技术的飞速发展&#xff0c;催生了一款令人惊叹的AI实景自动无人直播软件&#xff0c;为商家提供了全新的直播…