NOIP2008提高組 笨小猴 word 解題報告

【問題描述】

笨小猴的詞彙量很小，所以每次做英語選擇題的時候都很頭痛。但是他找到了一種方法，經實驗證明，用這種方法去選擇選項的時候選對的機率非常大!

這種方法的具體描述如下：假設maxn單詞中出現次數最多的字母的出現次數，minn是單詞中出現次數最少的字母的出現次數，如果maxn-minn是一個質數，那麼笨小猴就認爲這是個Lucky Word，這樣的單詞很可能就是正確的答案。

【輸入】

輸入文件word.in只有一行，是一個單詞，其中只可能出現小寫字母，並且長度小於100。

【輸出】

輸出文件word.out共兩行，第一行是一個字符串，假如輸入的單詞是Lucky Word，那麼輸出“Lucky Word”，否則輸出“No Answer”；

第二行是一個整數，如果輸入單詞是Lucky Word，輸出maxn—minn的值，否則輸出0。

【輸入輸出樣例1】

word.in

error

word.out

Lucky Word 2

【輸入輸出樣例1解釋】

單詞error中出現最多的字母r出現了3次，出現次數最少的字母出現了1次，3-1=2，2是質數。

【輸入輸出樣例2】

word.in

olymipic

word.out

No Answer 

0

【輸入輸出樣例2解釋】

單詞olymipic中出現最多的字母i出現了2次，出現次數最少的字母出現了1次，2-1=1,l不是質數。

【分析】
質數判斷+字符串處理，由於數據太弱，無論怎麼判斷素數都不會超時，我當時做這題時怎麼會想到了打質數表～
注意：
0 不是質數
1 不是質數
2 是質數

【我的代碼】
（由於對質數打了表，所以僅供參考）
#include <fstream>
#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int danci[100];
int zhishu[101];

void fuzhi()
{
zhishu[0]=0;
zhishu[1]=0;
zhishu[2]=1;
zhishu[3]=1;
zhishu[4]=0;
zhishu[5]=1;
zhishu[6]=0;
zhishu[7]=1;
zhishu[8]=0;
zhishu[9]=0;
zhishu[10]=0;
zhishu[11]=1;
zhishu[12]=0;
zhishu[13]=1;
zhishu[14]=0;
zhishu[15]=0;
zhishu[16]=0;
zhishu[17]=1;
zhishu[18]=0;
zhishu[19]=1;
zhishu[20]=0;
zhishu[21]=0;
zhishu[22]=0;
zhishu[23]=1;
zhishu[24]=0;
zhishu[25]=0;
zhishu[26]=0;
zhishu[27]=0;
zhishu[28]=0;
zhishu[29]=1;
zhishu[30]=0;
zhishu[31]=1;
zhishu[32]=0;
zhishu[33]=0;
zhishu[34]=0;
zhishu[35]=0;
zhishu[36]=0;
zhishu[37]=1;
zhishu[38]=0;
zhishu[39]=0;
zhishu[40]=0;
zhishu[41]=1;
zhishu[42]=0;
zhishu[43]=1;
zhishu[44]=0;
zhishu[45]=0;
zhishu[46]=0;
zhishu[47]=1;
zhishu[48]=0;
zhishu[49]=0;
zhishu[50]=0;
zhishu[51]=0;
zhishu[52]=0;
zhishu[53]=1;
zhishu[54]=0;
zhishu[55]=0;
zhishu[56]=0;
zhishu[57]=0;
zhishu[58]=0;
zhishu[59]=1;
zhishu[60]=0;
zhishu[61]=1;
zhishu[62]=0;
zhishu[63]=0;
zhishu[64]=0;
zhishu[65]=0;
zhishu[66]=0;
zhishu[67]=1;
zhishu[68]=0;
zhishu[69]=0;
zhishu[70]=0;
zhishu[71]=1;
zhishu[72]=0;
zhishu[73]=1;
zhishu[74]=0;
zhishu[75]=0;
zhishu[76]=0;
zhishu[77]=0;
zhishu[78]=0;
zhishu[79]=1;
zhishu[80]=0;
zhishu[81]=0;
zhishu[82]=0;
zhishu[83]=1;
zhishu[84]=0;
zhishu[85]=0;
zhishu[86]=0;
zhishu[87]=0;
zhishu[88]=0;
zhishu[89]=1;
zhishu[90]=0;
zhishu[91]=0;
zhishu[92]=0;
zhishu[93]=0;
zhishu[94]=0;
zhishu[95]=0;
zhishu[96]=0;
zhishu[97]=1;
zhishu[98]=0;
zhishu[99]=0;
zhishu[100]=0;
return ;
}

int main()
{
    char words[105];
    fuzhi();
    ifstream fin("word.in");
    ofstream fout("word.out");
    fin>>words;
    memset(danci,0,30);
    for (int i=0;words[i]!='\0';i++)
        danci[words[i]-'a']++;//统计各个字母出现的个数
   
    int maxn=0,minn=100;//最大次数和最小次数

    for (int i=0;i<100;i++)
    {
        if(danci[i]>0)
        {
            maxn=max(maxn,danci[i]);
            minn=min(minn,danci[i]);
        }
    }
    int delta=maxn-minn;
    if (zhishu[delta]) fout<<"Lucky Word"<<endl<<delta;
    else fout<<"No Answer"<<endl<<0;
    fin.close();
    fout.close();
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.028 s	273 KB	0
2	正确	10	0.001 s	273 KB	0
3	正确	10	0.001 s	273 KB	0
4	正确	10	0.001 s	273 KB	0
5	正确	10	0.001 s	273 KB	0
6	正确	10	0.001 s	273 KB	0
7	正确	10	0.001 s	273 KB	0
8	正确	10	0.001 s	273 KB	0
9	正确	10	0.001 s	273 KB	0
10	正确	10	0.001 s	273 KB	0

运行完成
运行时间 0.034 s
平均内存使用 273 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!