NOIP字符串处理与质数判断实战解析

1. 题目分析与解题思路

这道题目来自NOIP 2008提高组，考察的是字符串处理和基础数学知识的综合应用。题目要求我们统计一个单词中各字母出现的次数，找出出现次数最多和最少的字母，然后计算它们的差值，判断这个差值是否为质数。

1.1 题目核心要求解析

题目有几个关键点需要注意：

1. 输入只包含小写字母，长度小于100
2. 需要统计每个字母出现的次数
3. 找出出现次数最多和最少的字母（只统计实际出现的字母）
4. 计算maxn-minn的差值
5. 判断差值是否为质数（注意0和1不是质数）

1.2 解题思路选择

对于这类题目，常见的解决思路是：

1. 使用数组统计每个字母出现的次数
2. 过滤掉未出现的字母
3. 对出现的字母次数进行排序
4. 计算最大值和最小值的差
5. 判断差值是否为质数

我选择用C++来实现这个算法，主要考虑以下几点：

• 字符串处理方便
• 有现成的排序算法可用
• 代码执行效率高

2. 代码实现详解

2.1 输入处理和初始化

cpp复制#include<bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt[26] = {0};

这里我们包含了常用的头文件<bits/stdc++.h>，它包含了大多数标准库。使用string类型来存储输入的单词，因为它比字符数组更方便。cnt数组用于统计26个字母出现的次数，初始化为0。

注意：虽然<bits/stdc++.h>在竞赛中常用，但在实际工程中更推荐包含具体的头文件，如、、等。

2.2 字母出现次数统计

cpp复制for(int i = 0; i < s.size(); i++) {
    cnt[s[i] - 'a']++;
}

这个循环遍历字符串中的每个字符，通过s[i]-'a'将字母转换为0-25的数字，对应cnt数组的索引。例如，'a'对应0，'b'对应1，依此类推。

技巧：s[i]-'a'这种转换方式在字母处理中非常常见，记住'a'的ASCII码是97，所以这种转换实际上是减去97。