题目传送门
题目描述
托米有一个字符串，他经常拿出来玩。这天在英语课上，他学习了元音字母 a , e , i , o , u {a,e,i,o,u} a,e,i,o,u 以及半元音 y {y} y 。“这些字母是非常重要的！”，托米这样想着，“那么我如果随机取一个子串，里面元音占比期望会有多大呢？”
于是，请你求出对于托米的字符串，随机取一个子串，元音 ( a , e , i , o , u , y ) (a,e,i,o,u,y) (a,e,i,o,u,y)字母占子串长度比的期望是多少。
输入描述:
读入一个长度不超过 1 0 6 10^6 106 的只包含小写字母的字符串，即托米的字符串。
输出描述:
输出所求的期望值，要求相对(绝对)误差不超过 1 0 ? 6 10^{-6} 10?6 。
输入
legilimens
输出
0.446746032
题意
- 统计所有子串元音字母占比的平均值
题解
-
令 sum [ i ] \ \text{sum}[\ i\ ] sum[ i ] 表示前 i i i 个字母中元音字母个数
-
令长度为 i i i 的子串中元音字母出现的个数之和为 f [ i ] f[\ i\ ] f[ i ]，
-
f [ 1 ] = sum [ n ] f [ 2 ] = f [ 1 ] + sum [ n ? 1 ] ? sum [ 1 ] f [ 3 ] = f [ 2 ] + sum [ n ? 2 ] ? sum [ 2 ] ? ? \begin{aligned} &f[\ 1\ ]=\text{sum}[\ n\ ]\\ &f[\ 2\ ]=f[\ 1\ ]+\text{sum}[n-1]-\text{sum}[\ 1\ ]\\ &f[\ 3\ ]=f[\ 2\ ]+\text{sum}[n-2]-\text{sum}[\ 2\ ]\\ &\cdots\cdots \end{aligned} ?f[ 1 ]=sum[ n ]f[ 2 ]=f[ 1 ]+sum[n?1]?sum[ 1 ]f[ 3 ]=f[ 2 ]+sum[n?2]?sum[ 2 ]???
-
最后答案是 ( ∑ f [ i ] ) / i n ( n + 1 ) / 2 \displaystyle\frac{\left(\sum f[\ i\ ]\right)/i}{n(n+1)/2} n(n+1)/2(∑f[ i ])/i?
AC-Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;string str;
ll sum[maxn];
ll f[maxn];
int main(){
while(cin >> str){
int n = str.length();double ans = 0;for(int i = 0; i < n; ++i){
if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u' || str[i] == 'y')sum[i+1] = sum[i] + 1;elsesum[i+1] = sum[i];}ans = f[1] = sum[n];for(int i = 1; i < n; ++i){
f[i+1] = f[i] + sum[n-i] - sum[i];ans += 1.0*f[i+1]/(i+1);}ans = ans / (n*(n+1LL)/2.0);printf("%.9f\n", ans);}return 0;
}