Codeforces 509E Pretty Song (思维)
E. Pretty Song
When Sasha was studying in the seventh grade, he started listening to music a lot. In order to evaluate which songs he likes more, he introduced the notion of the song's prettiness. The title of the song is a word consisting of uppercase Latin letters. The prettiness of the song is the prettiness of its title.
Let's define the simple prettiness of a word as the ratio of the number of vowels in the word to the number of all letters in the word.
Let's define the prettiness of a word as the sum of simple prettiness of all the substrings of the word.
More formally, let's define the function vowel(c) which is equal to 1, if c is a vowel, and to 0 otherwise. Let si be the i-th character of string s, and si..j be the substring of word s, staring at the i-th character and ending at the j-th character (sisi + 1... sj, i ≤ j).
Then the simple prettiness of s is defined by the formula:
The prettiness of s equals
Find the prettiness of the given song title.
We assume that the vowels are I, E, A, O, U, Y.
The input contains a single string s (1 ≤ |s| ≤ 5·105) — the title of the song.
Print the prettiness of the song with the absolute or relative error of at most 10 - 6.
IEAIAIO
28.0000000
BYOB
5.8333333
YISVOWEL
17.0500000
In the first sample all letters are vowels. The simple prettiness of each substring is 1. The word of length 7 has 28 substrings. So, the prettiness of the song equals to 28.
一开始完全没有思路……但是后来想着想着就出来一个O(N)的。要用到预处理。(假设字符串长度为N) 首先把那些元音字母的位置筛出来。
我的代码中的ai表示(1/1+1/N) + (2/2+2/(N-1)) + ... + (i/i+i/(N-i+1)) bi表示1/1+1/2+1/3+...+1/i (之后我会解释为什么要这样预处理)
每次对于一个元音字母的位置x,无论他在该字符串的前一半还是字符串的后一半,都把他调到前一半的对称位置。(比如说输入的字符串长度为6,我现在要处理的元音字母的位置为5,那么就可以等效成2),然后利用等效之后的这个x生成一个序列,这个序列是分数,长度为N,其中分母为1,2,3,4,...,N,分子为1,2,3,....,x-1,x,x,x,x-1,...,3,2,1(对就是这样的一个序列现在我们要计算这个序列的和),就利用之前预处理出来的a数组和b数组,在O(1)内就可以实现,然后把每次得到的这个和累加起来,结果就是答案。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i(0); i < (n); ++i)
#define rep(i,a,b) for(int i(a); i <= (b); ++i)
#define dec(i,a,b) for(int i(a); i >= (b); --i)
#define for_edge(i,x) for(int i = H[x]; i; i = X[i]) const int N = + ;
const int M = + ;
const int Q = + ;
const int A = + ; char s[N];
int len, cnt;
int c[N];
double a[N], b[N];
int l, r;
double ans;
int x; int main(){ scanf("%s", s + );
len = strlen(s + ); cnt = ; l = ; r = len + ;
a[] = b[] = ;
rep(i, , len) b[i] = b[i - ] + (double) / (double)i; if (len & ){
rep(i, , len >> ){
++l, --r;
a[i] = a[i - ] + i / (double)l + i / (double)r;
}
a[len / + ] = a[len / ] + (++l) / (len / + );
}
else{
rep(i, , len >> ){
++l, --r;
a[i] = a[i - ] + i / (double)l + i / (double)r;
}
} rep(i, , len){
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U' || s[i] == 'Y'){
c[++cnt] = i;
}
} ans = ;
rep(i, , cnt){
x = c[i];
if (x > len / ) x = len - x + ;
if (x <= len / ) ans += a[x] + (b[len - x] - b[x]) * x;
else ans += a[x];
} printf("%.7f\n", ans); return ; }
最新文章
- 利用django创建一个投票网站(一)
- CodeFirst时使用T4模板(你肯定没用过的笨方法,还望园友指教)
- javascript高级程序设计第5章,引用类型
- centos 如何清理/dev/vda1系统盘
- 用Unity开发HTC VIVE——移动漫游篇
- 如何获取checkboxlist的多个选中项
- 茴香豆的第五种写法---设置ExpandableListView系统自带图标按下效果
- ISupportInitialize的用处
- python制作wifi破解(跑字典(单线程))
- (MariaDB/MySQL)之DML(1):数据插入
- java中的out of memory
- 关于EF的三种分类----CodeFirst
- 决策树ID3算法的java实现(基本适用所有的ID3)
- JAVA中byte为负数处理
- Keepalived+Nginx+tomcat实现系统的高可用
- linux命令(53):用户和用户组
- windows7 桌面突然卡住了,点击右键点不了,点击桌面软件点不了,怎么办?
- JavaMail之-通过邮件激活账号
- jquery -- checkbox选中无选中状态
- Android orm 框架xUtils简介
热门文章
- 12、python中的函数(高阶函数)
- Java并发——synchronized和ReentrantLock的联系与区别
- UVa 1455 Kingdom 线段树 并查集
- vijos1083:小白逛公园
- c++ primer plus 第6版 部分一 1-4章
- 13 Java内存模型
- 为 rails 本地项目搭建 elasticsearch 服务
- [python][django学习篇][11]后台admin用户登录博客,添加文章---这一章和博客首页设计没有关系
- cookie和session机制区别
- JavaWeb开发小结