CF1073A Diverse Substring(暴力），cf1073adiverse

CF1073A Diverse Substring(暴力），cf1073adiverse

题目链接

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;
}