蓝桥杯---子串分值和（数学）

本文主要是介绍蓝桥杯---子串分值和（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

试题历届试题子串分值和

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
对于一个字符串S ，我们定义 S 的分值 f(S) 为S 中出现的不同的字符个数。例如 f(“aba”)=2，f(“abc”)=3, f(“aaa”)=1。

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

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

输出格式
输出一个整数表示答案。

样例输入

ababc

样例输出

样例说明
子串 f值

a     1
ab    2
aba   2
abab  2
ababc 3b    1ba   2bab  2babc 3a   1ab  2abc 3b  1bc 2c 1

评测用例规模与约定(n为正整数)
对于 20% 的评测用例：
n<=10
对于 40%的评测用例：
n<=100
对于 60%的评测用例：
n<=1000
对于 80%的评测用例：
n<=10000
对于所有评测用例：
n<=100000
思路1：
求每个子串的字符个数，用集合处理，集合大小就是不重复字符数目；
由于至多有26中字母，所以，很长的字符串一但到达了最多字符数1，后面的就不用再一一求解了，可以减少循环次数；
code1：（80%）

#include<iostream>
#include<cstring>
#include<set>using namespace std;int main()
{long long int ans=0;char s[100005];int vis[26]={0};scanf("%s",s);int len=strlen(s);for(int i=0;i<len;i++){vis[s[i]-'a']=1;}int num=0;//num为出现的字符个数(1<=n<=26)for(int i=0;i<26;i++){if(vis[i]==1)num++;}for(int i=0;i<len;i++){set<char> e;for(int j=i;j<len;j++){e.insert(s[j]);int size=e.size();ans+=size;if(size==num){//如果当前字符全部出现了，则后面的就不用再算了ans+=(len-1-j)*size;break;}}}printf("%lld",ans);return 0;
}

思路2：
看的别人的，，，原理也没有弄懂 (^ _ ^;)
有点类似于 <蓝桥杯—子串分值>中的思想，pre存储数组中每个字符前一个相同字符出现的下标
最后求（pre[i]+1）*(len-i)的和—>sub；
然后sum =（len * （len+1） * （len+2））/ 6

对于这个sum公式，是假设len个字符各不相同的情况：
即（n+n-1+n-2+…+1）+(n-1+n-2+…+1)+…+(1)=n*(n+1)/2+n*(n-1)/2+…+1=
n*(n+1)*(n+2)/6;
(上式子可以由数学归纳法得到，属于算法数论中常用的结论吧)
最终sum - sub即为答案；
code2：

#include<iostream>
#include<cstring>
#include<set>using namespace std;int main()
{long long int ans=0;char s[100005];scanf("%s",s);long long int len=strlen(s);int now[len];int pre[len];memset(now,-1,sizeof(now));for(int i=0;i<len;i++){int index=s[i]-'a'+1;pre[i]=now[index];now[index]=i;}long long int sum=(len*(len+1)*(len+2))/6;long long int sub=0;for(int i=0;i<len;i++){sub+=(pre[i]+1)*(len-i);}ans=sum-sub;printf("%lld",ans);return 0;
}