本文主要是介绍CodeForces 386C Diverse Substrings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一个字符串的价值等于它包含的不同字母的个数（abcdabcdabcd 的价值为4）
给你一个字符串 求该字符串所有子串的价值
输出最大的价值是多少 再分别输出价值为x的字符串有多少个
思路：
MAXstringlen=3*10^5 数据较大 所以我首先尝试可否从左到右扫描一遍每次添加一个字符的想法
但是最简单的加一个字符回头判断一下价值为x的字符串增加了多少个复杂度也是O(n^2)
为了降低复杂度 想到了字符只有26个这一点 这是关键！！ 用它将复杂度变成O(nm) m为出现字符个数最大26
如果此时插入一个字符'f' 那么距离该位置最近的'f'左边并不受影响 因为本来串内已经有'f'这个字符了
举例说明：
加入前字符串为 dddffccca 这时加入一个 f
加入前i位置到串末所形成的串的价值分别为 4 4 4 3 3 2 2 2 1
加入后i位置到串末所形成的串的价值分别为 4 4 4 3 3 3 3 3 2 1
根据这种特性 可以每次加一个字符 更新一次价值为x的串增加了多少个 题目就可解了
事实证明我的方法是CF上至今速度最快的 只需31ms即可完成（让我小激动一下~~~）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 300010
#define N 30__int64 ans[N];
int add[N],loc[N];
char str[M];int main()
{int i,j,k,len,flag;scanf("%s",str);memset(loc,-1,sizeof(loc));for(i=0,len=strlen(str);i<len;i++){if(loc[str[i]-'a'+1]==-1){for(j=26;j;j--) add[j]=add[j-1];add[1]++;}else{k=i-loc[str[i]-'a'+1]-1;for(flag=1;k;flag++) k-=add[flag];add[flag]+=add[flag-1];for(j=flag-1;j;j--) add[j]=add[j-1];add[1]++;}loc[str[i]-'a'+1]=i;for(j=26;j;j--) ans[j]+=add[j];}for(j=26;j;j--){if(ans[j]){printf("%d\n",j);break;}}for(i=1;i<=j;i++) printf("%I64d\n",ans[i]);return 0;
}
这篇关于CodeForces 386C Diverse Substrings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
