2008年NOIP提高组笨小猴（洛谷P1125）：从字母统计到质数判断

一、题目解析

2008年NOIP提高组的"笨小猴"题目要求我们对输入的单词进行字母频率分析，找出出现次数最多和最少的字母，然后判断两者之差是否为质数。这道题综合考察了字符串处理、数组统计和数学判断能力。

二、完整代码实现（含详细注释）

#include <iostream>
#include <string>
#include <cmath>      // 用于sqrt函数
#include <algorithm>  // 用于max/min函数
using namespace std;

// 判断是否为质数的函数
bool isPrime(int n) {
    if (n <= 1) return false;  // 1及以下不是质数
    if (n == 2) return true;   // 2是唯一偶质数
    if (n % 2 == 0) return false; // 排除其他偶数
    // 只需检查到sqrt(n)的奇数即可
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    string word;
    cin >> word;  // 输入单词
    
    int maxn = 0, minn = 100;  // 初始化最大值和最小值
    int count[26] = {0};       // 26个字母的计数器
    
    // 统计每个字母出现次数
    for (char c : word) {
        count[c - 'a']++;  // 'a'对应索引0，'z'对应25
    }
    
    // 遍历找出最大和最小出现次数
    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {  // 只处理出现过的字母
            maxn = max(maxn, count[i]);
            minn = min(minn, count[i]);
        }
    }
    
    int diff = maxn - minn;  // 计算差值
    
    // 判断差值是否为质数并输出结果
    if (isPrime(diff)) {
        cout << "Lucky Word" << endl;
        cout << diff << endl;
    } else {
        cout << "No Answer" << endl;
        cout << 0 << endl;
    }
    
    return 0;
}

三、关键知识点详解

1. 字母频率统计

• 使用长度为26的数组count记录每个字母出现次数

• 通过c - 'a'将字母转换为0-25的索引值

• 遍历字符串时使用范围for循环简化代码

2. 质数判断优化

• 排除所有偶数（除了2）

• 只需检查到√n的奇数因子

• 时间复杂度从O(n)优化到O(√n)

3. 极值查找技巧

• 初始化maxn=0和minn=100（假设单词长度≤100）

• 遍历时只处理出现过的字母（count[i]>0）

四、常见问题解答

Q: 为什么minn初始化为100？ A: 题目保证单词长度不超过100，这样可以确保第一个出现的字母次数必定小于初始minn。

Q: 如何处理大小写字母？ A: 题目默认输入是小写字母，若包含大写字母需要先转换为小写。

Q: 质数判断有哪些优化空间？ A: 可以预先生成质数表，或使用更高效的算法如Miller-Rabin测试。