十一届蓝桥杯省赛 C/C++ 子串分值和（一看就会）

子串分值和

对于一个字符串 S，我们定义 S 的分值 f(S)为 S 中出现的不同的字符个数。

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

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

输入格式

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

输出格式

输出一个整数表示答案。

数据范围

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

输入样例：

ababc

输出样例：

28

解题思路

分析

该题如果暴力枚举则是一个$O(n^2)$的复杂度
很显然当n到10000时测评就很难通过
那么我们就要考虑一下有什么方法可以优化到$O(nlogn)$,$O(n)$以内

举例

按样例的列举如下图划分，我们就可以将本题转换成一个计算每个字符贡献的情况
①先举一个没有重复的例子，他的每个字母出现的次数
s[i]:a　b　c　d　e
f[i]:5　8　9　8　5
有没有看出什么，没有？那我们再细分
　1*5 2*4 3*3 4*2 5*1
是不是看出了些什么(#^.#)

②再来看一个有重复了例子
s[i]:a　b　a　b　c
f[i]:5　8　6　4　5
如下图所示第3个位置a出现了三段，与一段与第1个位置a发生了重复(舍去[ f[i] * 1/3 ])
如下图所示第4个位置a出现了三段，与两段与第2个位置a发生了重复(舍去[ f[i] * 2/4 ])

那么我么只需开一个数组last[]记录上一个字母s[i]出现的最后位置即可知道多少位置发生重复
重复a　　3:(9-91/3)
重复b　　　4:(8-82/4)

推公式

重复s[i]： f[i] - f[i] / i*last[s[i]]

样例解释

子串 f值
a     1
ab    2
aba   2
abab  2
ababc 3

 b    1
 ba   2
 bab  2
 babc 3
 
  a   1
  ab  2
  abc 3
  
   b  1
   bc 2
   
    c 1

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
char s[N];
ll f[N];    //预处理会爆int
int last[30];
int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    ll ans = 0;
    //预处理没有任何重复的情况；
    for(int i=1;i<=n-i+1;i++)f[i] = f[n-i+1] = (n-i+1)*(ll)i; //注意乘的时候一定要转long long
    //统计总贡献，并去重
    for(int i = 1;i<=n;i++){
        int t = s[i]-'a';
        if(!last[t]){    //判断有无重复部分
            ans += f[i];
        }else{
            ans += f[i] - f[i]/i*last[t]; //减去重复部分；
        }
        last[t] = i; //记录当前字母最后出现位置
    }
    printf("%lld",ans);
    return 0;
}