首页 > 代码库 > Codeforces Round #289 Div2 E
Codeforces Round #289 Div2 E
Codeforces Round #289 Div2 E
Problem
给一串长度为N的字符串，对于每个字符，若字符为元音，则权值为1，否则为0。一个子串的权值定义为该串所有字符权值之和除以字符个数，一个母串的权值定义为所有子串的权值之和。求母串的权值。
Limits
Time Limit(ms): 1000
Memory Limit(MB): 256
N: [1, 5*10^5]
字符集: ‘A‘-‘Z‘
元音: I E A O U Y
Solution
考虑每个元音字符对母串的贡献，可以找出规律。
More
举“ABCDOEFGHKMN”例子。考虑所有含有‘O‘的子串S。|S|=1时有一个子串“O”，|S|=2时有两个子串"VO"、"OW"，|S|=3时有三个子串“SVO”、“VOW”、“OWE”，|S|=4时有四个子串，那么它们对母串的贡献度分别为1/1，2/2，3/3，4/4，均为1。|S|在[6，9]的S均分别含有4个，|S|=10时有三个，|S|=11时有两个，|S|=12时有一个。
Complexity
Time Complexity: O(N)
Memory Complexity: O(N)
Source
Codeforces Round #289 Div2 E
Code
Codeforces Round #289 Div2 E From My Github
Codeforces Round #289 Div2 E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。