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

胡志明t

一、题目解析

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

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

1. #include <iostream>
   
2. #include <string>
   
3. #include <cmath>      // 用于sqrt函数
   
4. #include <algorithm>  // 用于max/min函数
   
5. using namespACe std;
   
6. 
   
7. // 判断是否为质数的函数
   
8. bool isPrime(int n) {
   
9.     if (n <= 1) return false;  // 1及以下不是质数
   
10.     if (n == 2) return true;   // 2是**偶质数
    
11.     if (n % 2 == 0) return false; // 排除其他偶数
    
12.     // 只需检查到sqrt(n)的奇数即可
    
13.     for (int i = 3; i <= sqrt(n); i += 2) {
    
14.         if (n % i == 0) return false;
    
15.     }
    
16.     return true;
    
17. }
    
18. 
    
19. int main() {
    
20.     string word;
    
21.     cin >> word;  // 输入单词
    
22.    
    
23.     int maxn = 0, minn = 100;  // 初始化**值和最小值
    
24.     int count[26] = {0};       // 26个字母的计数器
    
25.    
    
26.     // 统计每个字母出现次数
    
27.     for (char c : word) {
    
28.         count[c - 'a']++;  // 'a'对应索引0，'z'对应25
    
29.     }
    
30.    
    
31.     // 遍历找出**和最小出现次数
    
32.     for (int i = 0; i < 26; i++) {
    
33.         if (count[i] > 0) {  // 只处理出现过的字母
    
34.             maxn = max(maxn, count[i]);
    
35.             minn = min(minn, count[i]);
    
36.         }
    
37.     }
    
38.    
    
39.     int diff = maxn - minn;  // 计算差值
    
40.    
    
41.     // 判断差值是否为质数并输出结果
    
42.     if (isPrime(diff)) {
    
43.         cout << "Lucky Word" << endl;
    
44.         cout << diff << endl;
    
45.     } else {
    
46.         cout << "No Answer" << endl;
    
47.         cout << 0 << endl;
    
48.     }
    
49.    
    
50.     return 0;
    
51. }

复制代码

三、关键知识点详解1. 字母频率统计

• 使用长度为26的数组count记录每个字母出现次数
• 通过c - 'a'将字母转换为0-25的索引值
• 遍历字符串时使用范围for循环简化代码
  
  

2. 质数判断优化

• 排除所有偶数（除了2）
• 只需检查到√n的奇数因子
• 时间复杂度从O(n)优化到O(√n)
  
  

3. 极值查找技巧

• 初始化maxn=0和minn=100（假设单词长度≤100）
• 遍历时只处理出现过的字母（count>0）
  
  

四、常见问题解答

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

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

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

来源：大矩学习资料