子串分值 【蓝桥杯---子串分值（数学）】题目描述
对于一个字符串 SS，我们定义 SS 的分值 f(S)f(S) 为 SS 中恰好出现一次的字符个数。例如 f(“aba”) = 1，f(“abc”) = 3, f(“aaa”) = 0f(“aba”)=1，f(“abc”)=3,f(“aaa”)=0。
现在给定一个字符串 S0?n?1，（长度为 n，1≤n≤10^5
），请你计算对于所有 SS 的非空子串 Si…j(0 ≤ i ≤ j < n)(0≤i≤j
输入一行包含一个由小写字母组成的字符串 SS。
输出描述
输出一个整数表示答案。
输入
ababc
输出
21
运行限制
最大运行时间：1s
最大运行内存: 256M
思路1：
文章图片
所以外层循环i为起始位置控制；
内层j从i到n，且没有重复的score++，且ans+=score；
有一个重复的（即vis[j]==1时）score–，且ans+=score；
code:（60%）
#include
#include
#includeusing namespace std;
char s[100003];
int vis[27];
int main()
{
scanf("%s",s);
int len=strlen(s);
int sum=0;
for(int i=0;
i=1&&vis[s[j]-'a']==1){
vis[s[j]-'a']++;
score--;
}
sum+=score;
}
}
}
printf("%d",sum);
return 0;
}
思路2：
对于每一个字符求其对sum的贡献值；
仔细观察会发现：每个字符的贡献值=（当前下边index-前一个相同字符下标）*（下一个相同字符下标-当前下标index）
如果前面没有相同的字符，就默认前一个相同字符下标为0；
如果后面没有相同的字符，就默认后一个相同字符下标为s_length;
把所有的字符贡献值累加在一起即可！
accept code：
#include
#include
#includeusing namespace std;
#defineMAX100003
int main()
{
string s;
int pre[MAX],next[MAX],a[27];
cin>>s;
s="0"+s;
int len=s.length();
for(int i=0;
i<27;
i++){
a[i]=0;
}for(int i=1;
i=1;
i--){
int index=s[i]-'a';
next[i]=a[index];
a[index]=i;
}
long long int ans=0;
for(int i=1;
i 推荐阅读
- 蓝桥杯|ACwing789. 数的范围 （二分法典型例题）
- 每日刷题———蓝桥杯真题|蓝桥杯2020第十一届C语言B组省赛习题题解——习题A.门牌制作
- 蓝桥杯|2018年第九届C/C++ A组蓝桥杯省赛真题部分题解（C语言/C++）
- #|＜＜算法很美＞＞——(七)——DFS典题(二):数独游戏
- 蓝桥杯真题|蓝桥真题练习——ASC
- 数据结构|劈叉都会还不会下腰吗（（二叉树经典面试题详解））
- 蓝桥杯|蓝桥杯单片机最全备考资料（真题、代码、原理图、指导手册、资源包）
- 蓝桥杯|01蓝桥杯特训课程第一次总结
- 蓝桥杯|蓝桥杯单片机省赛国赛资料（2020年前的检索）