AcWing 2868. 子串分值
原题链接
中等
作者:
炽热的
,
2022-02-24 11:11:03
,
所有人可见
,
阅读 469
我写的好复杂, 纯粹打个卡
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 30;
int n;
vector<int> q[M];
char s[N];
int main()
{
cin >> s + 1;
n = strlen(s + 1);
for (int i = 1; i <= n; i ++ ) q[s[i] - 'a'].push_back(i);
long long res = 0;
for (int i = 0; i < 26; i ++ )
for (int j = 0; j < q[i].size(); j ++ )
{
if (q[i].size() == 1)
{
res += q[i][j] * 1ll * (n - q[i][j] + 1);
continue;
}
if (!j) res += q[i][j] * 1ll * (q[i][j + 1] - q[i][j]);
else if (j == q[i].size() - 1) res += (q[i][j] - q[i][j - 1]) * 1ll * (n - q[i][j] + 1);
else res += (q[i][j] - q[i][j - 1]) * 1ll * (q[i][j + 1] - q[i][j]);
}
cout << res << endl;
return 0;
}