| 等 级 | |
| 排 名 | 2600 |
| 经 验 | 2231 |
| 参赛次数 | 4 |
| 文章发表 | 5 |
| 年 龄 | 0 |
| 在职情况 | 学生 |
| 学 校 | 河北农业大学 |
| 专 业 |
自我简介：
TA的其他文章
| 蓝桥杯2013年第四届真题-幸运数 浏览：381 |
| 蓝桥杯2014年第五届真题-排列序数-全排列解法 浏览：174 |
| 蓝桥杯2014年第五届真题-兰顿蚂蚁 dfs解法 浏览：164 |
解题思路:
我们可以通过求每个字符对数列的贡献度来解决问题，比如对于字符串ababc，第一个字符a的贡献度为5，因为它在五个字符串中出现了；而对于第二个a它一共在6个字符串中出现，所以它的贡献度为6.每个字符的贡献度都是等于该字符距离上一个和它一样的字符之间的个数乘以它到字符串末尾的个数。
比如第二个a的贡献度=（2-0）*3=6；
这五个字符每个字符的贡献度分别为：
a: 5//因为它是第一个所以贡献度就是字符串的长度
b: 2*4=8//因为在它之前没有b
a:（2-0）*3=6
b: (3-1)*2=4;
c: 5*1=5;
所以正好加起来等于28；
注意事项:
参考代码:
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
int main()
{
string s;
cin>>s;
ll total=0;
int a[26]; //用于存放该字符上一次在字符串中的位置
memset(a,-1,sizeof(a));
a[s[0]-'a']=0;
total+=s.size();
for(int i=1;i<s.size();i++){
total+=(i-a[s[i]-'a'])*(s.size()-i);
a[s[i]-'a']=i;
}
cout<<total;
return 0;
}0.0分
11 人评分