蓝桥杯历届试题|第十一届蓝桥杯 ——子串分值和蓝桥杯历届试题|数学

题目描述
对于一个字符串S S S，我们定义S S S 的分值f ( S ) f(S) f(S) 为S S S 中出现的不同的字符个数。
例如f ( “ a b a ” ) = 2 f(“aba”)=2 f(“aba”)=2， f ( “ a b c ” ) = 3 f(“abc”)=3 f(“abc”)=3， f ( “ a a a ” ) = 1 f(“aaa”)=1 f(“aaa”)=1。
现在给定一个字符串S [ 0.. n ? 1 ] S[0..n?1] S[0..n?1]，请你计算对于所有S S S 的非空子串S [ i . . j ] S[i..j] S[i..j] ， f ( S [ i . . j ] ) f(S[i..j]) f(S[i..j]) 的和是多少。
输入格式
输入一行包含一个由小写字母组成的字符串 S。
输出格式
输出一个整数表示答案。
输入样例
ababc
输出样例
28
样例解释

子串 f值 a1 ab2 aba2 abab2 ababc 3 b1 ba2 bab2 babc 3 a1 ab2 abc 3 b1 bc 2 c 1

数据范围
对于 20% 的评测用例， 1 ≤ n ≤ 10 1 ≤ n ≤ 10 1≤n≤10；
对于 40% 的评测用例， 1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100；
对于 50% 的评测用例， 1 ≤ n ≤ 1000 1 ≤ n ≤ 1000 1≤n≤1000；
对于 60% 的评测用例， 1 ≤ n ≤ 10000 1 ≤ n ≤ 10000 1≤n≤10000；
对于所有评测用例， 1 ≤ n ≤ 100000 1 ≤ n ≤ 100000 1≤n≤100000。
题解一（超时）
暴力枚举O ( N 3 ) O(N^3) O(N3)：可得 40% ~ 50% 的分数
解题思路：

枚举区间左端点；
枚举区间右端点；
遍历当前所枚举的区间，累加不同字母的个数；

unordered_set：自动删去重复元素，使得集合内的元素各不相同；

size：返回集合内的元素数量；
insert：向集合中插入某个元素；

#include #include using namespace std; int main() { string s; cin >> s; int ans = 0; for (int l = 0; l < s.size(); l ++) for (int r = l; r < s.size(); r ++) { unordered_set S; for (int k = l; k <= r; k ++) S.insert(s[k]); ans += S.size(); }cout << ans << endl; return 0; }

题解二（超时）
稍加优化O ( N 2 ) O(N^2) O(N2)：可得 50% ~ 60% 的分数

#include #include using namespace std; int main() { string s; cin >> s; int ans = 0; for (int l = 0; l < s.size(); l ++) { unordered_set S; for (int r = l; r < s.size(); r ++) { S.insert(s[r]); ans += S.size(); } }cout << ans << endl; return 0; }

题解三
乘法原理O ( N ) O(N) O(N)：
解题思路：

每个字母只有在第一次出现时才有贡献度，因此可以统计每个字母在第一次出现的情况下，能被多少子串所包含；
用 last[s[i]] 记录字母 s[i] 上一次出现的位置；
那么往左最多能延伸到 last[s[i]] + 1，其到第 i 个字母一共有 i - last[s[i]] 个字母；
同理往右最多能延伸到 n，其到第 i 个字母一共有 n - i + 1 个字母；
二者相乘，就是该字母被不同子串所包含的总次数；

#include using namespace std; typedef long long LL; int last[200]; int main() { string s; cin >> s; int n = s.size(); s = ' ' + s; LL ans = 0; for (int i = 1; i <= n; i ++) { ans += (LL)(i - last[s[i]]) * (n - i + 1); last[s[i]] = i; }cout << ans << endl; return 0; }

【蓝桥杯历届试题|第十一届蓝桥杯 ——子串分值和】ps：原来样例解释的排列就是这个思路，5 + 8 + 6 + 4 + 5 = 28，然而就是看不出来