蓝桥杯2020年第十一届省赛真题-子串分值

题目

题目链接

题解

思维。

考虑每个字符对最终答案的贡献，每个字符的贡献为其左侧连续与之不相同的字符个数+1乘以其右侧与之不相同的字符个数+1。

样例：ababc

第一个字符a的贡献：
(0+1) * (1+1) = 2
a, ab

第二个字符b的贡献：
(1+1) * (1+1) = 4
ab, b, ba, aba

......

第五个字符c的贡献：
(4+1) * (0+1) = 5
ababc, babc, abc, bc, c

一开始以为滑动窗口，后来发现不行。就考虑每个字符的贡献。

代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int N = 1e5+10;

int before[N], after[N], pre[30], ans;


string s;

int main()
{
    
    cin >> s;
    
    memset (pre, -1, sizeof pre);
    for (int i = 0;i < s.size();i ++) {
        before[i] = i - pre[s[i] - 'a'];
        pre[s[i] - 'a'] = i;
    }
    
    for (int i = 0;i < 30;i ++) pre[i] = s.size();
    for (int i = s.size()-1;i >= 0;i --) {
        after[i] = pre[s[i] - 'a'] - i;
        pre[s[i] - 'a'] = i;
    }
    
    for (int i = 0;i < s.size();i ++) 
        ans += before[i] * after[i]; 
    
    cout << ans << endl;
       
    return 0;
}