子串分值-超详细版——最后的编程挑战

H.子串分值 困难- 细心可以做出一半 不细心可以做出一点点

看了一些博客，终于是搞懂了这道题；

很多博客都说了“贡献”

我认为“贡献”是一个数x对于结果ans是有用的，并且我们可以求出有用的程度。

我们把所有对ans有用的x求出来之后，ans自然也知道了。

题解：

假如有一个字符串：ooa1ooooa2oooa3oo注：o是任意字符， a1,a2,a3是一种字符

a1能够提供贡献的字符串最长是：ooa1oooo 即：(ooa1oooo)a2oooa3oo

如果字符串中同时有a1,a2,那么a对于字符串的贡献就是0，即没有贡献

所以我们的任务是求出a1能为多少个字符串做出贡献

即多少个字符串包含a1但不能包含a2

也就是ooa1oooo 有多少个包含a1的子串？

可以用乘法算出来：$len(ooa1)\times len(a1oooo)=3\ast 5=15$

这样就转换了问题：将所有的相同的字符 在串中的位置找到， 然后遍历一遍所有存在的字符，用上面的公式求！

但是有三个情况需要特殊处理一下：

1. 字符只出现一次
2. 第一次出现
3. 最后一次出现

#include <iostream>
#include <vector>
using namespace std;
const int n = 100010;
typedef long long ll;
vector<int> v[n];
int main()
{
    string s;
    ll ans = 0, slen, l, r;
    cin >> s;
    slen = s.size();
    // 找到所有字符 在串中的位置
    // 用s[i]-'a' 目的是方便处理，没什么特殊意义
    for (int i = 0; i < slen; i++)
        v[s[i] - 'a'].push_back(i);
    // 遍历所有可能存在的字符 'a'-'z' 
    // 因为已经转换了 所以是：0-25
    for (int i = 0; i < 26; i++)
    {
        // 空的不用管
        if (v[i].empty())
            continue;
        if (v[i].size() == 1)
        {
            l = v[i].front() + 1;
            r = slen - v[i].front();
            ans += l * r;
            continue;
        }
        int n = v[i].size();

        // 至于下面为什么+1,为什么不加1 自己在纸上模仿几次就很清楚了
        // 处理端点：
        // 起点
        l = v[i].front() + 1;
        r = v[i][1] - v[i].front();
        ans += l * r;
        // 终点
        l = v[i].back() - v[i][n - 2];
        r = slen - v[i].back();
        ans += l * r;
        // 处理中间节点
        for (int j = 1; j < n - 1; j++)
        {
            l = v[i][j] - v[i][j - 1];
            r = v[i][j + 1] - v[i][j];
            ans += l * r;
        }
    }
    cout << ans;

    return 0;
}