AcWing 2868. 子串分值（贡献法）

本文主要是介绍AcWing 2868. 子串分值（贡献法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AcWing 2868. 子串分值

原题链接：https://www.acwing.com/problem/content/2871/

具体分析过程如下图：

直接遍历的话太麻烦，且时间复杂度太高，所以另寻他路
字符串中只有小写字母26个，所以可以从此着手， 考虑每个字母对答案的贡献度
那么枚举仅包含一个i的区间的左右端点

代码如下：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
char s[N];
//p[t]代表t字符当前所指向的位置 t -> [0, 25]
int l[N], r[N], p[26];  //l[]i, r[i]代表位置i的字符的前后一次出现的位置
int main() {scanf("%s", s + 1); //[1, n]int n = strlen(s + 1);//给左区间赋值for(int i = 0; i < 26; i++ )   p[i] = 0;      //将第0个位置设为i字符左极值for(int i = 1; i <= n; i++ ) {l[i] = p[s[i] - 'a'];   //i位置的t字符上次出现位置给l[i]p[s[i] - 'a'] = i;  //存下t字符此次出现的位置i，以方便下次赋值给l[]}  //给右区间赋值for(int i = 0; i < 26; i++ )    p[i] = n + 1;  //当前指向n+1位置，也就是在n+1位置设置哨兵for(int i = n; i >= 1; i--) {r[i] = p[s[i] - 'a'];p[s[i] - 'a'] = i;  //存下t字符此次出现的位置i，以方便赋值给r[]}LL res = 0;for(int i = 1; i <= n; i++) {res += (LL)(i - l[i]) * (r[i] - i);}cout << res;return 0;
}

这篇关于AcWing 2868. 子串分值（贡献法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---