E. Pretty Song
題目意思是求一個單詞串所有連續(xù)子串的元音字母比例之和，原因字母定義為：I, E, A, O, U, Y
舉例來說：
單詞：
BYOB（元音字母有：Y和O）
一個字母的子串：B,Y,O,B
sigma=0/1+1/1+1/1+0/1=2
兩個字母的子串：B,Y,O,B
sigma=0/2+2/2+2/2+0/1=2
三個字母的子串：B,Y,O,B
sigma=0/3+2/3+2/3+0/3=1.33
四個字母的子串：B,Y,O,B
sigma=0/4+1/4+1/4+0/4=0.5
總加和為5.833
通過找規(guī)律可以發(fā)現(xiàn)，一個字符串的連續(xù)子串中每一個字母在該長度所有子串中的出現(xiàn)次數(shù)是有規(guī)律的
比如一個長度為7的字符串，它的每一個字母在所有子串中的次數(shù)如以下矩陣所示：
其中行代表每種長度的子串（從1到n），列代表該字符串中每一個字母在各長度子串中的出現(xiàn)次數(shù)
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 2 3 3 3 2 1
1 2 3 4 3 2 1
1 2 3 3 3 2 1
1 2 2 2 2 2 1
1 1 1 1 1 1 1
假設(shè)該矩陣為a[][]，那么最終的答案就應(yīng)該為sigma(a[i][j]*b[j]/j)，考慮到i和j的范圍都到5*10^5，如果直接算，肯定TLE
然后觀察這個矩陣，發(fā)現(xiàn)下一行跟上一行相比，只是多增加了中間一段（比如第二行相比于第一行增加了2~n-1這n-2個位置），而且都是增加1，然后求和的時候除數(shù)不同
于是可以想到用樹狀數(shù)組/線段樹存儲1~n個元素的值，這樣每次取其中一段求和復(fù)雜度就是log級別，時限ok
實現(xiàn)的時候注意這個矩陣是對稱的，所以循環(huán)只到行數(shù)的一半，奇數(shù)行特判一下(這里寫的比較挫)
PS：直接保存累加和就行了。不用樹狀數(shù)組啥的，【腦殘。。殺雞用牛刀。。
挫代碼如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
double a[500010];
int fg[500010], n;
char s[500010];
int Lowbit(int n) {
return n & (-n);
}
void Modify(int i) {
while(i <= n) {
a[i] += 1.0;
i += Lowbit(i);
}
}
double Add(int i) {
double res = 0;
while(i != 0) {
res += a[i];
i -= Lowbit(i);
}
return res;
}
int main() {
int i;
double res = 0, pre1 = 0, pre2 = 0, tp = 0, nt = 0;
scanf("%s", s);
memset(a, 0, sizeof(a));
n = strlen(s);
for(i = 0; i < n; ++i) {
if(s[i] == 'I' || s[i] == 'E' || s[i] == 'A' || s[i] == 'O' || s[i] == 'U' || s[i] == 'Y') {
fg[i + 1] = 1;
Modify(i + 1);
}
else
fg[i] = 0;
}
for(i = 1; i <= n/2; ++i) {
res += nt / i;
res += nt / (n-i+1);
tp = Add(n-i+1) - Add(i-1);
nt += tp;
pre1 = tp / i;
pre2 = tp / (n-i+1);
res += pre1;
res += pre2;
}
if(n%2) {
res += nt / i;
tp = Add(n-i+1) - Add(i-1);
nt += tp;
pre1 = tp / i;
res += pre1;
}
printf("%.6lf\n", res);
return 0;
}