Tokitsukaze and Average of Substring

第一行包含一个整数 $T$ ( $1 \leq T \leq 5000$ ) --- 测试数据的组数。

对于每组测试数据：

第一行包含一个整数 $n$ ( $1 \leq n \leq 5000$ ) --- 字符串 $s$ 的长度。

第二行包含一个只含小写字母的字符串 $s$ 。

数据保证 $\sum n \leq 5000$

C++(clang++ 11.0.1) 解法, 执行用时: 38ms, 内存消耗: 536K, 提交时间: 2023-03-11 10:59:52

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	cin>>T;
	while(T--){
	int n;cin>>n;
	char s[5005];
	cin>>s+1; 
	float sum=0,ff=0;
	for(int i=1;i<=n;i++)
	{
		int x[27]={0};
		sum=0;
		for(int j=i;j<=n;j++)
		{
			int b=s[j]-'a';
			x[b]++;
			
			sum=sum+x[b]-1;
			
			ff=max(ff,sum/(j-i+1));
		
		}
		
	}
	printf("%.5f\n",ff);
}
}

C++(g++ 7.5.0) 解法, 执行用时: 48ms, 内存消耗: 496K, 提交时间: 2023-03-11 17:54:11

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	cin>>T;
	while(T--){
	int n;cin>>n;
	char s[5005];
	cin>>s+1; 
	float sum=0,ff=0;
	for(int i=1;i<=n;i++)
	{
		int x[27]={0};
		sum=0;
		for(int j=i;j<=n;j++)
		{
			int b=s[j]-'a';
			x[b]++;
			sum=sum+x[b]-1;
			ff=max(ff,sum/(j-i+1));
        }
	}
	printf("%.6f\n",ff);
}
}

pypy3 解法, 执行用时: 220ms, 内存消耗: 23224K, 提交时间: 2023-03-10 21:35:34

for i in range(int(input())):
    n = int(input())
    ans = 0
    s = [ord(c)-ord("a") for c in input()]
    for j in range(n):
        count = [0]*26
        c = 0
        for k in range(j,n):
            c += count[s[k]]
            count[s[k]] += 1
            ans = max(ans,c/(k-j+1))
    print(ans)

详情