【牛客】Tokitsukaze and Average of Substring

embedded/2024/9/22 11:00:45/

原题链接:登录—专业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/embedded/37959.html

相关文章

对C语言符号的一些冷门知识运用的剖析和总结

注释 C语言风格的注释: /* 这是注释 */C风格的注释: //这是注释 奇怪的注释 int main() { int /* */ i; //1.正确 char *s "abcdefgh //hijklmn"; //2.正确&#xff1a;//是字符串的一部分 //Is it a\ valid comment? //3.正确…

【C++】滑动窗口:最大连续1的个数

1.题目 2.算法思路 其实在做这道题的时候并不需要真的把0翻转成1&#xff0c;只需要找到最长的子数组且该子数组中0的个数不大于K&#xff0c;就可以了&#xff01; 当然我们首先想到的是暴力穷举法&#xff1a; 找到所有符合题意的子数组&#xff0c;跳出最长的那个就可以了…

RabbitMQ保证消息的可靠性

一、背景 消息丢失&#xff1a;下图是消息从生产者发送到消费者接收的关系图。通过图片可以看出&#xff0c;消息在生产者、MQ、消费者这三个环节都有可能丢失。 1.1 生产者丢失 生产者发送消息时连接MQ失败生产者发送消息到达MQ后未找到Exchange生产者发送消息到达MQ的Exc…

小麦穗检测数据集VOC+YOLO格式6508张1类别

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

点云成图原理

点成图&#xff08;Point Cloud&#xff09;是指由一组离散的点构成的图形&#xff0c;它们在空间中没有任何连接关系。点成图通常是由激光雷达、相机或其他传感器获取的三维数据&#xff0c;用于表示现实世界中的物体或场景。 三角成图&#xff08;Triangulation&#xff09;…

Android 网络请求 实现

Android 网络请求 实现 一、背景 在Android开发中,网络请求是一个非常常见的需求。应用程序可能需要与远程服务器通信来获取数据、上传文件、验证用户身份等等。背景下,Android应用通常会面临以下几个主要情况和挑战: ①数据交互: 许多应用程序需要从服务器获取数据,例…

《Fundamentals of Power Electronics》——正则电路模型

所有PWM CCM dc-dc转换器执行类似的基本功能。第一&#xff0c;它们转换电压和电流水平&#xff0c;理想状态下效率为100%。第二&#xff0c;它们包含波形的低通滤波功能。虽然有必要去除高频开关纹波&#xff0c;但这种滤波也影响低频电压和电流的变化。第三&#xff0c;转换器…

浙大×移动云,携手点亮AI新时代

近年来&#xff0c;中国移动依托强大的算网资源优势&#xff0c;围绕大模型训练、推理和应用三大场景&#xff0c;打造了一站式智算产品体系。该体系旨在为客户提供覆盖资源、平台、应用的AI全链路服务。目前&#xff0c;一站式智算产品体系已在浙江大学智算中心和许昌中原智算…