以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 人评分
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:552 |
A+B for Input-Output Practice (II) (C语言代码)浏览:999 |
C语言训练-求函数值 (C语言代码)浏览:580 |
求组合数 (C语言代码)浏览:1159 |
IP判断 (C语言描述,蓝桥杯)浏览:1095 |
幸运数 (C++代码)浏览:1264 |
1113题解浏览:789 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:569 |
蚂蚁感冒 (C语言代码)浏览:1333 |
Tom数 (C语言代码)浏览:725 |