【NOIP】2008真题解析 luogu-P1125 笨小猴 (适合GESP3级以上练习)

NOIP 2008 提高组真题，考察字母频次统计（桶计数思想）与质数判定。解题的核心是利用长度为 26 的计数数组统计每个字母的出现次数，进而求出最大与最小频次之差，并判断该差值是否为质数。适合GESP三级以上考生练习。题目难度⭐⭐，洛谷难度等级入门。

luogu-P1125 [NOIP 2008 提高组] 笨小猴

题目要求

题目描述

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

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

输入格式

一个单词，其中只可能出现小写字母，并且长度小于 。

输出格式

共两行，第一行是一个字符串，假设输入的单词是 Lucky Word，那么输出 Lucky Word，否则输出 No Answer；

第二行是一个整数，如果输入的单词是 Lucky Word，输出  的值，否则输出 。

输入输出样例 #1

输入 #1

error

输出 #1

Lucky Word2

输入输出样例 #2

输入 #2

olympic

输出 #2

No Answer0

说明/提示

【输入输出样例 1 解释】

单词 error 中出现最多的字母  出现了  次，出现次数最少的字母出现了  次，， 是质数。

【输入输出样例 2 解释】

单词 olympic 中出现最多的字母  出现了  次，出现次数最少的字母出现了  次，， 不是质数。

【题目来源】

NOIP 2008 提高组第一题

题目分析

这道题是一道经典的字符串处理与数学判断相结合的入门题。可以拆分为三个步骤来解决：

1. 字母频次统计——桶计数

输入的单词只包含小写字母 a-z，因此我们可以开一个长度为 26 的计数数组 counts，利用 counts[c - 'a']++ 来统计每个字母出现的次数。这就是经典的桶计数思想：以字母的编号作为"桶"的索引，每遇到一个字母就往对应的桶里加一。

2. 求出现次数的最大值与最小值

遍历计数数组 counts，分别求出最大值 maxn 和最小值 minn。

这里有一个关键的易错点：**minn 只能在出现过的字母中取最小值**。

如果不加判断地直接遍历整个 counts 数组取最小值，那些单词中根本没有出现过的字母（次数为 0）就会"干扰"结果，导致 minn 恒为 0，所有差值都等于 maxn，答案就完全错了。因此，在比较时必须加上 counts[i] > 0 的前提条件，只有出现过的字母才参与最小值的比较。

3. 质数（素数）判定

得到差值 diff = maxn - minn 后，需要判断它是否为质数。

质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。

需要特别注意：

• 0 和 1 都不是质数，这两个值必须特判返回 false。
• 判定方法：从  遍历到 ，如果存在某个数能整除 diff，则 diff 不是质数；否则是质数。本题中单词长度不超过 100，差值 diff 最大也只可能是 99，所以判定的计算量微乎其微。

4. 核心要点总结

• 桶计数思想：一个长度为 26 的数组就能完成所有字母的频次统计，时间复杂度 ， 为单词长度。
• 最小值排除零值：只统计出现过的字母的频次，counts[i] > 0 是必要的过滤条件。
• 质数判定的边界：0 和 1 不是质数，这是本题最常见的出错点之一。

示例代码

#include<algorithm>#include<iostream>#include<string>// 质数判定函数boolis_prime(int n){    if (n < 2) {        return false; // 0 和 1 不是质数，直接返回    }    for (int i = 2; i * i <= n; ++i) {        if (n % i == 0) {            return false; // 能被整除则不是质数        }    }    return true;}intmain(){    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    std::string s;    std::cin >> s;    int counts[26] = {0}; // 长度为 26 的计数数组（桶），初始化为 0    for (char c : s) {        counts[c - 'a']++; // 统计每个字母的出现次数    }    int maxn = 0;   // 出现次数的最大值    int minn = 105; // 出现次数的最小值（初值设为大于单词最大长度 100）    for (int i = 0; i < 26; ++i) {        if (counts[i] > 0) { // 只考虑出现过的字母            maxn = std::max(maxn, counts[i]);            minn = std::min(minn, counts[i]);        }    }    int diff = maxn - minn;    // 根据质数判定结果，输出对应内容    if (is_prime(diff)) {        std::cout << "Lucky Word" << "\n" << diff << "\n";    } else {        std::cout << "No Answer" << "\n" << 0 << "\n";    }    return 0;}