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

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

题目要求

题目描述

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

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

输入格式

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

输出格式

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

第二行是一个整数，如果输入的单词是 Lucky Word，输出 $\text{maxn}-\text{minn}$ 的值，否则输出 $0$。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

【输入输出样例 1 解释】

单词 error 中出现最多的字母 $\texttt r$ 出现了 $3$ 次，出现次数最少的字母出现了 $1$ 次，$3-1=2$，$2$ 是质数。

【输入输出样例 2 解释】

单词 olympic 中出现最多的字母 $\texttt i$ 出现了 $1$ 次，出现次数最少的字母出现了 $1$ 次，$1-1=0$，$0$ 不是质数。

【题目来源】

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。
• 判定方法：从 $2$ 遍历到 $\sqrt{\text{diff}}$，如果存在某个数能整除 diff，则 diff 不是质数；否则是质数。本题中单词长度不超过 100，差值 diff 最大也只可能是 99，所以判定的计算量微乎其微。

4. 核心要点总结

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

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <algorithm>
#include <iostream>
#include <string>

// 质数判定函数
bool is_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;
}

int main() {
    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;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助