题解 P1125 【笨小猴】

· · 题解

题目描述

笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！

这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。

分析:

其实前人介绍了做法,只是没有见到用筛法做此题的,所以来介绍一下线性素数筛 (尝试水一篇题解

提供板子位置--> 线性筛素数

我们可以用数组prime[]来存储素数,对于一些素数的倍数,它一定不是素数,所以我们可以利用这一性质去筛除一些素数的倍数。

因此很容易码出普通筛法

IL void getprime()
{
    vis[1]=true;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime[++tot]=i;
        for(RI j=1;j<=tot;i*prime[j]<=n;j++)
            vis[i*prime[j]]=1;
    }
    //tot用来记录素数个数
    //vis数组为辅助数组判断合数。
    //vis[i]为true则i为合数 否则为素数。 
}

但是这样的话考虑 6既可以被2筛去,也可以被3筛去 同样的数还有很多,即我们重复地筛去了这些合数, 而这里就是我们时间浪费的地方

因此我们可以用一些数的最小质因子将其筛去,所以改变后的代码如下

IL void getprime()
{
    vis[1]=true;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime[++tot]=i;
        for(int j=1;j<=tot;i*prime[j]<=n;j++)   
        { 
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;//只是增加了这一句
        } 
    }
    //tot用来记录素数个数
    //vis数组为辅助数组判断合数。
    //vis[i]为true则i为合数 否则为素数。 
}

什么?两层for不是线性的？

具体我也不会证明 百度见贾志鹏线性筛

此题代码↓

#include<bits/stdc++.h>
#define IL inline
#define RI register int
using namespace std;
int prime[105],tot,tong[27],mxx,mnn=2147483647;
bool vis[105];
string s;
IL void p()
{
    vis[0]=vis[1]=1;
    for(RI i=2;i<=105;i++)
    {
        if(!vis[i])prime[++tot]=i;
        for(RI j=1;j<=tot&&i*prime[j]<=105;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    p();
    cin>>s;
    for(RI i=0;i<s.length();i++)
    tong[s[i]-'a'+1]++;
    for(RI i=1;i<=26;i++)
    {
        mxx=max(mxx,tong[i]);
        if(tong[i]!=0)mnn=min(mnn,tong[i]);
    }
    if(!vis[mxx-mnn])printf("Lucky Word\n"),print(mxx-mnn);
    else printf("No Answer\n"),print(0);
}