【贡献法】第十一届蓝桥杯省赛第二场C++ A组《子串分值》（c++）

1.题目说明

对于一个字符串 S，我们定义 S 的分值 f(S）为 S 中恰好出现一次的字符个数。

例如 f(“aba”)=1，f(“abc”)=3,  f(“aaa”)=0。

现在给定一个字符串 S[0…n−1]（长度为 n），请你计算对于所有 S的非空子串 S[i…j](0≤i≤j<n)，f(S[i…j]) 的和是多少。

2.输入格式

输入一行包含一个由小写字母组成的字符串 S。

3.输出格式

输出一个整数表示答案。

4.数据范围

对于 20% 的评测用例，1≤n≤10；
对于 40% 的评测用例，1≤n≤100；
对于 50% 的评测用例，1≤n≤1000；
对于 60% 的评测用例，1≤n≤10000；
对于所有评测用例，1≤n≤100000。

5.输入样例

ababc

6.输出样例

21

7.思路

把一个字符串中同一个字母的出现理解为该字母对所有字串的贡献值，只需要找到该字母的左右两侧又出现的位置，这个字母的贡献值即为右侧出现的位置减去该字母出现的位置 + 该字母的位置减去左侧出现的位置。即(i - l[i]) * (r[i] - i) 。当该字母两侧并未再次出现时，可以把位置为0和位置为n+1的位置当作该字母出现了。

8.代码

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
const int N = 100010;
 
int n;
char str[N];
int l[N], r[N], p[26];
 
int main()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    //如果左边界没有出现，可以默认在0位置出现
    for (int i = 1; i <= n; i ++ )
    {
        int t = str[i] - 'a';
        l[i] = p[t];
        p[t] = i;
    }
    //如果右边界没有出现，可以默认在n+1位置出现
    for (int i = 0; i < 26; i ++ ) p[i] = n + 1;
    for (int i = n; i; i -- )
    {
        int t = str[i] - 'a';
        r[i] = p[t];
        p[t] = i;
    }
    
    LL res = 0;
    for (int i = 1; i <= n; i ++ )
        res += (LL)(i - l[i]) * (r[i] - i);
 
    printf("%lld\n", res);
    return 0;
}