简单贪心——P6832 题解
或许更好的阅读体验
这道题比赛的时候不小心漏了标签……导致很多人都知道了贪心做法。
第一眼望过去，以为这道题是 DP。DP 没想出来只好暴力枚举子串 KMP。后来看到标签突然灵光一闪，可以按照如下思路贪心：
- 首先考虑子串长度为
1 的情况。这类子串就是\texttt{a-z} 的字符。那么出现次数最多的子串就是出现次数最多的字符，简单桶排解决。 -
接下来考虑子串长度为
2 的情况。这类子串一定由某一个第一类子串加一个新字符组成。这意味着出现次数最多的这类子串出现次数一定不会比出现次数最多的一类字串多。 可以理解为一个这类子串的第一个字符出现次数不少于这个子串的出现次数。例如：字符串
abababab中，ab是一个这类子串。而a出现的次数一定不会比ab出现次数少。 - 以此类推，长度为
k 的子串出现次数一定不比其第一个字符出现次数多。
由此我们就得到了我们的贪心策略：单个字符的子串中出现次数最多的一定是所有子串中出现次数最多的。
具体实现很简单，桶排即可。代码如下：
#include <bits/stdc++.h>
using namespace std;
char s[10000005];
int cnt[27];
int mx;
int main(void) {
scanf("%s",s);
int slen=strlen(s);
for(int i=0;i<slen;i++) cnt[s[i]-'a']++;
for(int i=0;i<26;i++) if(cnt[i]>mx) mx=cnt[i];
printf("%d",mx);
return 0;
}当然你也可以边 getchar 边判断。