P1125 笨小猴题解

· · 题解

首先我们要知道的是，以后可以学学笨小猴的做法来做选择题（雾）

由于输入的全是小写字母，那么第一种思路就是枚举a~z这26个字母，判断这个字母有没有出现过，然后比较每个出现过字母的出现次数的大小，求出max和min即可。

1：首先是读入

将每个出现的字母都打上标记，记录字母的出现次数

    for(int i=0;i<n;i++)
        {
            b[s[i]-'a']++;
            vis[s[i]-'a'] =false;
        }

2：接下来就是枚举 a 到 z 这 26 个字母是否出现过，并且通过打擂台求出出现次数的最大值和最小值

    for(int i=0;i<26;i++)
    {
        if(b[i]>max&&vis[i]==false) max=b[i];
        if(b[i]<min&&vis[i]==false) min=b[i];
    }

3：当求出最大值和最小值以后，就需要判断是否为素数了

由于数据比较水，直接枚举1到sqrt（x）就好了QWQ

bool sushu(int x)
{
    if(x==0||x==1) return false;
    if(x==2) return true;
    for(int j=2;j*j<=x;j++)
    {
        if(x%j==0) return false;
    }
    return true;
}

然后就可以开心地AC了(●ˇ∀ˇ●)

完整代码（参照某位萌新的写法）

我知道你们只看这个
#include <iostream>
#include<string>
#include<cstring>
using namespace std;
string s;
int b[30];
bool vis[30];
bool sushu(int x)
{
    if(x==0||x==1) return false;
    if(x==2) return true;
    for(int j=2;j*j<=x;j++)
    {
        if(x%j==0) return false;
    }
    return true;
}
int main()
{
    int max=0,min=999;
    cin>>s;
    memset(vis,true,sizeof(vis));
    int n=s.size();
    for(int i=0;i<n;i++)
        {
            b[s[i]-'a']++;
            vis[s[i]-'a'] =false;
        }
    for(int i=0;i<26;i++)
    {
        if(b[i]>max&&vis[i]==false) max=b[i];
        if(b[i]<min&&vis[i]==false) min=b[i];
    }
    if(sushu(max-min)==false)
    {
        cout<<"No Answer"<<endl;
        cout<<"0"<<endl;
    }
    else
    {
        cout<<"Lucky Word"<<endl;
        cout<<max-min<<endl;
    }

    return 0;

}

下面介绍另一种写法（STL快排QWQ）

首先我们知道#include <algorithm>中有一个自带排序的函数 sort

那么我们就有一种想法：将所有字母出现的个数记录下来，排一个序，直接将最大和最小求出来QWQ

所以就是在输入的时候记录一下，排好序

即

for(int i=0;i<=s.size()-1;i++)
    {
        a[i]=s[i]-'a';
    }
    sort(a,a+s.size(),cmp);
    for(int i=0;i<s.size();i++)//注意从0开始，s[0]才是记录的s中第一个字母
    {
        if(a[i+1]==a[i]) sum[cnt]++;  //记录每个字母出现的次数
         else  cnt++;  //记录总共有多少个字母出现
    }

然后再将记录好的sum数组排一个序

sort(sum,sum+cnt,cmp);

那么数组的头和尾就是记录的最小值和最大值了！QWQ

即

    sum2=sum[cnt-1];
    sum1=sum[0];

那么接下来就是和原先一样判断素数，输出答案，愉快地ＡＣ了ＱＷＱ。

代码（我知道你们只看这个）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 100010
using namespace std;
string s;
int sum1,sum2;
int a[maxn];
int sum[maxn];//记录每个字母出现的次数
int cnt;//字符串中总共字母的种类个数
bool cmp(int a,int b)
{
    return a<b;
}
bool pd(int x)
{
    if(x==0||x==1) return false;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0) return false;
    }
     return true;
}
int main()
{
    cin>>s;
    for(int i=0;i<=s.size()-1;i++)
    {
        a[i]=s[i]-48;
    }
    sort(a,a+s.size(),cmp);
    for(int i=0;i<s.size();i++)
    {
        if(a[i+1]==a[i]) sum[cnt]++;
         else  cnt++;
    }
    sort(sum,sum+cnt,cmp);
    sum2=sum[cnt-1];
    sum1=sum[0];
    if(pd(sum2-sum1))
    {
        cout<<"Lucky Word"<<endl;
        cout<<sum2-sum1;
    }
    else 
    {
        cout<<"No Answer"<<endl;
        cout<<0<<endl;
        return 0;
    }
}

记得来我的博客玩啊