以cabcdec为例
讨论中间的c的贡献值
含中间c的子串有
abc
abcd
abcde
bc
bcd
bcde
c
cd
cde
假设前面的c为l,中间的c为p,后面的c为r,中间的c的贡献值就为 (p-l)*(r-p)
为了方便计算,对于每位字母,0位我们认为是最小的l,n+1位是最大的r
参考代码:
#include<bits/stdc++.h>
using namespace std;
string s;
pair<int,int> a[30];
int n;
long long sum;
int main() {
cin >> s;
s = '0' + s;
n = s.size() - 1;
for (int i = 1; i <= n; i++) {
auto find=a[s[i] - 'a'];
int l=find.first,p=find.second;
sum +=(p-l)*(i-p);
a[s[i] - 'a']={p,i};
}
for (int i = 0; i < 26; i++) {
int l=a[i].first,p=a[i].second,r=n+1;
if (p!=0) sum += (p-l)*(r-p);
}
cout << sum;
return 0;
}
0.0分
1 人评分
printf基础练习2 (C++代码)(受教了,,%#o和%#x的用途)三人行,必有我师,,多看题解会有收获浏览:1873 |
上车人数 (C语言代码)浏览:1178 |
C二级辅导-等差数列 (C语言代码)浏览:588 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1053 |
C语言训练-排序问题<1> (C++代码)浏览:596 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:509 |
求圆的面积 (C语言代码)浏览:1270 |
C语言程序设计教程(第三版)课后习题6.3 (C++代码)浏览:954 |
哥德巴赫曾猜测 (C语言代码)浏览:2332 |
【计算直线的交点数】 (C语言代码)浏览:1449 |