河北建设厅网站,网站开发 定制 合同 模板,福建省建设工程信息网,营销型网站建设指导原则问题描述
对于一个字符串 s#xff0c;我们定义 s 的分值 f(s) 为 s 中恰好出现一次的字符个数。例如 f(aba)1#xff0c;f(abc)3, f(aaa)0。
现在给定一个字符串 s[0..n−1]#xff08;长度为 n#xff09;#xff0c;请你计算对于…问题描述
对于一个字符串 s我们定义 s 的分值 f(s) 为 s 中恰好出现一次的字符个数。例如 f(aba)1f(abc)3, f(aaa)0。
现在给定一个字符串 s[0..n−1]长度为 n请你计算对于所有 s 的非空子串 s[i..j](0≤i≤jn)f(s[i..j])的和是多少。
输入格式
输入一行包含一个由小写字母组成的字符串 s。
输出格式
输出一个整数表示答案。
样例输入
ababc
样例输出
21
样例说明
子串 f值
a 1
ab 2
aba 1
abab 0
ababc 1b 1ba 2bab 1babc 2a 1ab 2abc 3b 1bc 2c 1
评测用例规模与约定
对于 20% 的评测用例1≤n≤10
对于 40% 的评测用例1≤n≤100
对于 50% 的评测用例1≤n≤1000
对于 60% 的评测用例1≤n≤10000
对于所有评测用例1≤n≤100000。 题解 通俗地说题目的要求就是给定一个字符串要求求出这个字符串所有子串的分值而对于一个字符串来说它的分值就等于自身包含的所有字符中出现且仅出现了一次的字符个数。 顺着题意来的话多数人应该会想要把给定字符串的子串全部枚举出来然后再数每个子串中只出现了一次的字符的个数这样做需要枚举所有的左右边界计算的时间复杂度为O(n^2)必然会超时。 下面介绍的是O(n)的做法 题目要求的分值是所有子串分值的总和并且对于相同的字母a如果它在不同的位置它也算是不同的字母比如给定字符串“aba”他有子串‘a和‘a’两个‘a’在不同的位置。所以我们不需要计算所有子串的分值只需要计算每一个字母作为只出现一次的字符时包含了该字母的子串的个数假如说现在给定一个字符串“abcadcada”现在讨论字母a的分值则可以把该字符串看成“a..bc..a..dc..a..d..a”则对于第二个字母a它的有效子串的个数9分别为bcacaabcadcadadbcadccadcadc其实同样也是枚举左右边界左边界有三种选择b、c、a右边界有三种选择a、d、c两两组合组合数为3*39。对于其它字母也是同样的计算有效子串的个数最终求解它们的和。 用一个数组pre[]预处理位于i左侧的和第i个字母相同的最近的一个字母的位置“a..bc..a..dc..a..d..a”对于第二个a来说它是第四个字符所以pre[4]1用一个数组next[]预处理位于i右侧的和第i个字母相同的最近的一个字母的位置对于第二个a来说next[4]7. 所以左边界的选择数其实就等于“a..bc..a..dc..a..d..a”中bca的长度右边界的选择数就等于“a..bc..a..dc..a..d..a”中adc的长度转化为代码就是i - pre[i]和next[i] - i将两者相乘得到第二个子串的有效子串数。 在预处理pre和next数组时会借助一个idx数组由于题中给出的字符串都由小写字母组成我们可以把每个字母都通过ascii码相减转化为数字也就是x-a例如‘b’-‘a’1。所以idx[1]就表示上一个b出现的位置。 结合代码
#include iostream
#include string
using namespace std;
typedef long long ll;
const int N 1e5 10, M 50;
int pre[N], nex[N], idx[M];int main()
{string s; cin s;int len s.size();s s;//计算pre[i]for (int i 1; i len; i) {pre[i] idx[s[i] - a];idx[s[i] - a] i;}//初始化右超界为n1for (int i 0; i 26; i) {idx[i] len 1;}//计算next[i]for (int i len; i 0; i--) {nex[i] idx[s[i] - a];idx[s[i] - a] i;}ll ans 0;for (int i 1; i len; i) {ans (i - pre[i]) * (nex[i] - i);}cout ans;return 0;
}
