【牛客】Tokitsukaze and Average of Substring

server/2024/9/19 14:00:11/ 标签: 前缀和, 模拟, 字符串, 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/38543.html

相关文章

docker 部署并运行一个微服务

要将微服务部署并运行在Docker容器中&#xff0c;你需要按照以下步骤操作&#xff1a; 编写Dockerfile&#xff1a;在项目根目录下创建一个名为Dockerfile的文件&#xff0c;并添加以下内容&#xff1a; # 使用一个基础的Docker镜像 FROM docker-image# 将项目文件复制到容器…

【YOLOv8改进[Backbone]】使用SCINet改进YOLOv8在黑暗环境的目标检测效果

目录 一 SCINet 1 本文方法 ① 权重共享的照明学习 ② 自校准模块 ③ 无监督训练损失 二 使用SCINet助力YOLOv8在黑暗环境的目标检测效果 1 整体修改 2 配置文件 3 训练 其他 一 SCINet 官方论文地址&#xff1a;https://arxiv.org/pdf/2204.10137 官方代码地址&…

matlab二次插值函数 interp2

在MATLAB中&#xff0c;interp2函数用于执行二维插值操作。该函数可以接受多种不同的插值方法&#xff0c;其中包括linear&#xff08;线性插值&#xff09;和nearest&#xff08;最临近插值&#xff09;。这两种插值方法的插值结果存在明显的差异。 linear&#xff08;线性插值…

大数据Spark教程从入门到精通第四篇:Spark快速上手

一&#xff1a;Spark快速上手 1&#xff1a;创建Maven项目 idea安装scala_idea scala插件-CSDN博客 代表了我们安装scala的maven环境已经准备好了&#xff0c;代码可以正常跑了

初探MFC程序混合使用QT

一、背景 随着操作系统国产化替代的趋势越发明显&#xff0c;软件支持国际化、跨平台&#xff0c;已然是必须做的一件事情。原有的软件UI层用的是MFC&#xff0c;将其换成QT&#xff0c;想必是一种较好的方案。对于大型软件&#xff0c;特别是已发布&#xff0c;但还处于不断迭…

mysql IF语句,模糊检索

使用MySQL IF语句完成条件检索 IF(expr1,expr2,expr3)&#xff0c;expr1如果满足条件就用expr2&#xff0c;否则用expr3 SELECTa.*,count(*) AS stdSum FROMidb_std_power_engin_v1 a WHERE1 1 AND (IF( KV IS NOT NULL, a.NAME REGEXP KV, 1 1 ) ORIF( KV IS NOT NULL, …

Vue从入门到实战Day01

一、Vue快速上手 1. vue概念 概念&#xff1a;Vue是一个用于 构建用户界面的 渐进式 框架 构建用户界面&#xff1a;基于数据动态渲染页面渐进式&#xff1a;循序渐进的学习框架&#xff1a;一套完整的项目解决方案&#xff0c;提升开发效率 优点&#xff1a;大大提升开发效…

二维泊松方程(Neumann+Direchliet边界条件)有限元Matlab编程求解|程序源码+说明文本

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…

mybatis:Spring junit 测试报错:Failed to load ApplicationContext

Spring junit 测试报错&#xff1a;Failed to load ApplicationContext 解决方法&#xff0c;修改mybatis版本&#xff0c;版本过高导致无法加载依赖

Wireshark Lua插件开发实战:应对TCP粘包问题

0. 概述 Wireshark提供了tcp_dissect_pdus()函数&#xff0c;可以帮助用户处理TCP粘包问题 1. 粘包问题的基本原理 TCP粘包问题本质上是数据包拼接和拆分的问题。当多个应用层数据包被封装成同一个TCP段时&#xff0c;就发生了粘包现象。在解析时&#xff0c;我们需要将粘在…

ubuntu_Docker安装配置

什么是docker? Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中&#xff0c;然后发布到任何流行的 Linux或Windows操作系统的机器上&#xff0c;也可以实现虚拟化。容器是完全使用沙箱机制&#xff0c;相互之间不会有…

【使用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提供的可用模型…

Docker 容器中 PHP 使用 Curl 访问本地服务异常

在 Docker 环境中&#xff0c;将应用程序和服务容器化是常见的做法&#xff0c;但是有时会遇到一些网络通信方面的问题。其中一个常见的问题是 PHP 容器无法使用 Curl 访问本地服务&#xff0c;这可能导致开发和调试过程中的困扰。 问题描述 通常情况下&#xff0c;我们会将 …

VBA修改跨工作薄替换修改Excel工作表单元格数据

Excel工作表数据快完成时,工作表模版修改了,VBA快速修改之修改替换单元格数据。https://mp.weixin.qq.com/s?__biz=MzkwMzY1OTIzOA==&mid=2247483778&idx=1&sn=bad7568d925f27e2063c619945e7b429&chksm=c093aa0bf7e4231db3c0c9d5bdeb493bb082b2ca272c05ad28…

实战Java虚拟机-基础篇

JVM的组成 一、自动垃圾回收 1.Java的内存管理 Java中为了简化对象的释放&#xff0c;引入了自动的垃圾回收&#xff08;Garbage Collection简称GC&#xff09;机制。通过垃圾回收器来对不再使用的对象完成自动的回收&#xff0c;垃圾回收器主要负责对堆上的内存进行回收。其…

【代码】matlab调用COM端口获取传感器数据

参考链接 原始代码 clc clear close all fclose(instrfind)%先关闭所有串口 % scom serial(COM7); %建立串口对象函数&#xff08;需要手动和自己电脑的端口匹配&#xff09; fclose(scom); %关闭串口设备对象 scom.InputBufferSize 512;%输入缓冲区 scom.O…

Baidu Comate智能编码助手 -----AI编程帮你解放双手

目录 Baidu Comate是什么&#xff1f; Baidu Comate如何安装&#xff1f; 在VSCode上安装Baidu Comate插件 Baidu Comate如何使用&#xff0c;有哪些功能&#xff1f; 1.代码解释 2.代码注释 使用感受 如何体验 Baidu Comate是什么&#xff1f; Baidu Comate智能编码助手…

ABC猜想:数论中的未解之谜

ABC猜想&#xff1a;数论中的未解之谜 引言 ABC猜想是数论领域中一个著名的未解问题&#xff0c;它由法国数学家约瑟夫奥斯特莱&#xff08;Joseph Oesterl&#xff09;和大卫马瑟&#xff08;David Masser&#xff09;在1985年提出。ABC猜想涉及整数加法和乘法之间的深刻联系…

C++向函数传递对象

C语言中&#xff0c;对象作为函数的参数和返回值的传递方式有 3 种&#xff1a;值传递、指针传递和引用传递。 1. 对象作为函数参数 把实参对象的值复制给形参对象&#xff0c;这种传递是单向的&#xff0c;只从实参到形参。因此&#xff0c;函数对形参值做的改变不会影响到实…

PostgreSQL(十二)报错:Tried to send an out-of-range integer as a 2-byte value: 51000

目录 一、报错场景二、源码分析三、实际原因&#xff08;更加复杂&#xff09;四、解决思路 一、报错场景 今天写了一个历史数据处理程序&#xff0c;在开发环境、测试环境都可以正常执行&#xff0c;但是放到生产环境上就不行&#xff0c;报了一个这样的错误&#xff1a; or…