[蓝桥杯 2020 省 AB2] 子串分值

题目描述

对于一个字符串 $S$, 我们定义 $S$ 的分值 $f(S)$ 为 $S$ 中恰好出现一次的字符个数。例如 $f\left({}^{\prime \prime }\mathrm{aba}{}^{\prime \prime }\right)=1$，$f\left({}^{\prime \prime }\mathrm{abc}{}^{\prime \prime }\right)=3$，$f\left({}^{\prime \prime }\mathrm{aaa}{\mathrm{a}}^{\prime \prime }\right)=0$ 。

现在给定一个字符串 $S[\mathrm{0..}n-1]$（长度为 $n$），请你计算对于所有 $S$ 的非空 子串 $S[i..j](0\le i\le j<n)$，$f(S[i..j])$ 的和是多少。

输入格式

输入一行包含一个由小写字母组成的字符串 $S$。

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

ababc

样例输出 #1

21

提示

对于 $20\%$ 的评测用例, $1\le n\le 10$;

对于 $40\%$ 的评测用例, $1\le n\le 100$;

对于 $50\%$ 的评测用例, $1\le n\le 1000$;

对于 $60\%$ 的评测用例, $1\le n\le 10000$;

对于所有评测用例, $1\le n\le 100000$。

蓝桥杯 2020 第二轮省赛 A 组 H 题（B 组 H 题）。

---

思路

首先获取字符串长度，并在字符串前面加上一个空格。

然后定义两个数组pre和nex，以及一个临时数组tmp。pre数组用于存储每个字符在字符串中上一次出现的位置，nex数组用于存储每个字符在字符串中下一次出现的位置，tmp数组用于在遍历过程中记录每个字符最新的位置。

接着，对字符串进行两次遍历。第一次遍历从前往后，用于填充pre数组和更新tmp数组。第二次遍历从后往前，用于填充nex数组和更新tmp数组。

每个字符在子串中可以作为一个分界点，将子串分为两部分。在前一个相同字符（不含）到当前字符之间，可以选择一个位置作为子串的左端点。同理，在当前字符（含）到后一个相同字符（不含）之间，可以选择一个位置作为子串的右端点。这样，每一对左右端点的选择，就对应了一个以当前字符为唯一重复字符的子串。

乘法原理：如果有两种选择，一种有$m$种可能，另一种有$n$种可能，那么这两种选择的所有可能的组合数就是$m\ast n$。

根据乘法原理，这个字符对应的子串分值，就等于左端点的选择数乘以右端点的选择数。如果一个字符的位置是$i$，前一个相同字符的位置是pre[i]，后一个相同字符的位置是nex[i]，那么该字符对应的子串分值就是$(i-pre[i])\ast (nex[i]-i)$。

最后遍历字符串，计算每个字符对应的子串分值，累加得到总分值。

---

AC代码

#include <algorithm>
#include <cmath>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
string s;
int pre[N], nex[N];
int tmp[30];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> s;n = s.length();s = " " + s;for (int i = 1; i <= n; i++) {int t = s[i] - 'a';pre[i] = tmp[t];tmp[t] = i;}for (int i = 0; i < 26; i++) {tmp[i] = n + 1;}for (int i = n; i >= 1; i--) {int t = s[i] - 'a';nex[i] = tmp[t];tmp[t] = i;}ll ans = 0;for (int i = 1; i <= n; i++) {ans += 1LL * (i - pre[i]) * (nex[i] - i);}cout << ans << "\n";return 0;
}

---