2008年NOIP笨小猴（洛谷P1125）解题报告：质数判断与字母统计优化解析

一、题目解读

2008年NOIP“笨小猴”题目（洛谷P1125）要求判断输入单词中字母出现次数的最大值与最小值之差是否为质数。若是，输出“Lucky Word”及差值；否则输出“No Answer”和0。题目核心在于字符统计与质数判断的巧妙结合。

二、解题思路

1. 字符统计：遍历输入字符串，用数组记录26个字母的出现次数，并更新最大/最小值。

2. 质数判断优化：自定义isPrime函数，利用质数特性（仅需检查至√n的奇数），排除偶数后加速判断。

3. 差值计算：通过maxn - minn得到差值，结合质数结果输出对应答案。

三、解题步骤

1. 输入单词，初始化计数数组与极值变量。

2. 循环遍历字符，将对应字母次数累加。

3. 扫描计数数组，更新最大/最小值。

4. 计算差值并调用isPrime判断，输出结果。

四、代码与注释

#include <iostream>  
#include <string>  
#include <cmath>  
#include <algorithm>  
using namespace std;  

// 判断是否为质数（优化：仅检查奇数至√n）  
bool isPrime(int n) {  
    if (n <= 1) return false;  
    if (n == 2) return true;  
    if (n % 2 == 0) return false;  
    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}; // 字母计数数组  
    // 统计每个字母出现次数  
    for (char c : word) count[c - 'a']++;  
    // 寻找最大/最小值  
    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 << diff;  
    } else {  
        cout << "No Answer" << endl << 0;  
    }  
    return 0;  
}

五、总结

本题关键在于高效的字符统计与优化的质数判断。通过预处理排除偶数、缩小检查范围，降低了时间复杂度。代码简洁实用，体现了基础算法与数学思维的融合，适合作为编程入门训练题。