【牛客】Tokitsukaze and Average of Substring

本文主要是介绍【牛客】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;
}

这篇关于【牛客】Tokitsukaze and Average of Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---