前言
实际上这是蓝桥真题，和子串分值和一样
子串分值和
题目描述
对于一个字符串S ，我们定义S {S}S的分值f ( S ) 为S 中出现的不同的字符个数。例如f ( " a b c " ) = 3 , f ( " a b a " ) = 2 , f ( " a a a " ) = 1
现在给定一个字符串S ，请你计算所有S {S}S的非空子串S [ i . . . j ] ( 0 ≤ i ≤ j ＜ n ) ，f ( S [ i . . . j ] ) 的和是多少。
输入描述
输入一行包含一个由小写字母组成的字符串S。
其中，1 ≤ n ≤ 1 0 5
输出描述
输出一个整数表示答案。
样例
输入#1
ababc
输出#1
28
输入#2
code
输出#2
20
思路
在此，我们定义贡献wi为：包含当前字符且当前字符之前不在含有该字符的所有字符串的个数。
这是我自己给的定义，应该很抽象。
以样例一举例说明：a b a b c ，第二个a 对答案的贡献是多少？
可以算得结果是 6 ：
ba
bab
babc
a
ab
abc
为什么这样是对的？（也就是左边有限制（到左边过去第一个同字符），右边无限制（一直到字符串末尾））
不会证明，但是如果前面还含有该字符，当前字符是不在产生贡献的。（因为在计算之前那个字符的时候，已经包含了当前字符的情况）。而且这样不重不漏的包含了所有情况数。
题解
法一：计算贡献
我们用a数组来记录字符最后出现的位置。
下标从0开始，所以对于字符第一次出现，左侧应该是 i + 1 个字符，那么初始化 a数组为−1就很好的解决了。
class Solution { public: long long appealSum(string s) { int n = s.size(); int a[26]; memset(a, -1, sizeof a); long long res = 0; for (int i = 0; i < n; i++) { int x = s[i] - 'a'; res += (i - a[x]) * (n - i); a[x] = i; } return res; } };
法二：动态规划
class Solution { public: long long appealSum(string s) { int n = s.size(); vector<int> a(26, -1); vector<int> f(n, 0); f[0] = 1; a[s[0] - 'a'] = 0; for (int i = 1; i < n; i++) { int x = s[i] - 'a'; f[i] = f[i - 1] + i - a[x]; a[x] = i; } long long res = 0; for (int i = 0; i < n; i++) res += f[i]; return res; } };
优化掉一维数组：
class Solution { public: long long appealSum(string s) { vector<int> a(26, -1); long long num = 0, res = 0; for (int i = 0; i < s.size(); i++) { int x = s[i] - 'a'; num += i - a[x]; res += num; a[x] = i; } return res; } };
子串分值
题目描述
输入描述
输入一行包含一个由小写字母组成的字符串 S {S}S。
输出描述
输出一个整数表示答案。
样例
输入#1
ababc
输出#1
21
思路
题解
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int n = s.size(); vector<int> a[26]; s = '@' + s; for (int i = 1; i <= n; i++) { int x = s[i] - 'a'; if (a[x].size() == 0) a[x].push_back(0); a[x].push_back(i); } for (int i = 0; i < 26; i++) { if (a[i].size()) a[i].push_back(n + 1); } int res = 0; for (int i = 0; i < 26; i++) { auto& v = a[i]; if (!v.size()) continue; for (int j = 1; j < v.size() - 1; j++) res += (v[j] - v[j - 1]) * (v[j + 1] - v[j]); } cout << res << endl; return 0; }
