蓝桥杯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 
#include 
#include 
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