第十一届蓝桥杯 省赛 试题 H: 子串分值和

问题描述：
对于一个字符串 S，我们定义 S 的分值 f(S ) 为 S 中出现的不同的字符个 数。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。 现在给定一个字符串 S [0…n − 1]（长度为 n），请你计算对于所有 S 的非空 子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是多少。

【输入格式】

输入一行包含一个由小写字母组成的字符串 S。

【输出格式】

输出一个整数表示答案。

【样例输入】

ababc

【样例输出】

28

【样例说明】

子串 f值

a 1

ab 2

aba 2

abab 2

ababc 3

b 1

ba 2

bab 2

babc 3

a 1

ab 2

abc 3

b 1

bc 2

c 1

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 10； 对于 40% 的评测用例，1 ≤ n ≤ 100； 对于 50% 的评测用例，1 ≤ n ≤ 1000； 对于 60% 的评测用例，1 ≤ n ≤ 10000； 对于所有评测用例，1 ≤ n ≤ 100000。

代码：

#include 
using namespace std;
const int N = 1e5 + 10;
char s[N];
int a[30];
long long int ans=0;
int main()
{int i,j,n;scanf("%s",s+1);n=strlen(s+1);for(i=1;i<=n;i++){ans+=(i-a[s[i]-'a'])*(n-i+1);a[s[i]-'a']=i;}cout<<ans;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！