解题思路:
我们可以通过求每个字符对数列的贡献度来解决问题,比如对于字符串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 人评分
C语言训练-角谷猜想 (C++代码)(3N+1问题)浏览:1750 |
【偶数求和】 (C语言代码)浏览:646 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:2080 |
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1605 |
WU-C语言程序设计教程(第三版)课后习题11.12 (C++代码)(想学链表的小伙伴可以看看)浏览:904 |
简单的a+b (C语言代码)浏览:577 |
用筛法求之N内的素数。 (C++代码)浏览:693 |
1012题解浏览:869 |
母牛的故事 (C语言代码)浏览:944 |
【亲和数】 (C语言代码)浏览:599 |