CF1073A Diverse Substring(暴力）

题目链接

http://codeforces.com/problemset/problem/1073/A

题意

给定一个字符串s，求是否存在一个子串t。满足t中每个字母出现的次数都小于等于t/2的长度。

题解

注意到n只有1000，那么O（n^2）暴力莽即可。
枚举子串区间，求出该区间字母出现最多次Max，然后与t/2比较即可。

AC代码

#include <bits/stdc++.h>
using namespace std;int sum[26];
int main()
{int n;string str;ios::sync_with_stdio(false);while(cin>>n>>str){bool ok=false;int Max;for(int i=0;i<n;i++){memset(sum,0,sizeof(sum));for(int j=i;j<n;j++){sum[str[j]-'a']++;Max=0;for(int k=0;k<26;k++){Max=max(Max,sum[k]);}if(Max<=(j-i+1)/2){ok=true;cout<<"YES"<<endl;for(int ss=i;ss<=j;ss++){cout<<str[ss];}cout<<endl;break;}}if(ok) break;}if(!ok) cout<<"NO"<<endl;}return 0;
}