题目：Tokitsukaze and Average of Substring (nowcoder.com)

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define endl '\n'
#define ll long long

using namespace std;
const int N=1e5+10,M=5010,mod=998244353,INF=0x3f3f3f;

//pre表示存储相同字母的个数和 
int pre[M][M];

void solve()
{
	int n;cin>>n;
	string s;
	cin>>s;
	for(int i=1;i<=n;i++)
	{
		//字符串中的字母在字母表上的序号（转换成数字 ），加1是为了跟数组下标对应 
		int cnt=s[i-1]-'a'+1;
		for(int j=1;j<=26;j++) 
		{
			if(cnt==j) 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];
				if(tmp>=1)
				//计数相同字母组成的对数 
				cnt+=tmp*(tmp-1)/2;
			}
			double res=(double)cnt/(double)(r-l+1);
			ans=max(ans,res);
		}
	}
	printf("%.6f\n",ans);
	//重置数组的目的是为了清空上一个测试用例的计算结果
	//以便进行下一个测试用例的计算。
	//可直接用  memset(pre,0,sizeof pre);  
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=26;j++)
		{
			pre[i][j]=0;
		}
	}
}

signed main()
{
	int t;cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

从这道题学到的：

• 前缀和的深刻理解和应用
• 怎样求特定区间的前缀和
• 浮点型运算的转换
• 前缀数组的重置