[NOIP 2008 提高组] 笨小猴

题意

给定一个只含小写字母的单词。统计每个出现过的字母次数，令 maxn 是最大次数，minn 是最小次数。如果 maxn - minn 是质数，输出 Lucky Word 和这个差值；否则输出 No Answer 和 0。

思路

先统计每个字母的出现次数，再从这些次数里取最大值和最小值。注意 minn 只在出现过的字母中取最小值，没出现的字母不参与统计。

质数判断只需要试除到平方根：

text

1
2如果 x < 2，不是质数。
否则检查 2, 3, ..., floor(sqrt(x)) 是否能整除 x。

这题数据很小，直接计数和试除即可，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：Counter(word) 可以直接统计字符频率。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 input().strip() 读取单词。
counter.values() 得到所有出现过字符的次数。
while divisor * divisor <= x 避免额外导入平方根函数。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25from collections import Counter


def is_prime(x):
    if x < 2:
        return False
    divisor = 2
    while divisor * divisor <= x:
        if x % divisor == 0:
            return False
        divisor += 1
    return True


word = input().strip()
counter = Counter(word)
counts = counter.values()
difference = max(counts) - min(counts)

if is_prime(difference):
    print("Lucky Word")
    print(difference)
else:
    print("No Answer")
    print(0)

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

char s[105];   // 单词
int cnt[26];   // cnt[i] 记录字母 'a'+i 出现的次数

// 判断一个数是否为质数
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int main() {
    cin >> s;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        cnt[s[i] - 'a']++;
    }
    // 找最大和最小出现次数（只考虑出现过的字母）
    int maxn = 0, minn = 100;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > 0) {
            if (cnt[i] > maxn) maxn = cnt[i];
            if (cnt[i] < minn) minn = cnt[i];
        }
    }
    int diff = maxn - minn;
    if (is_prime(diff)) {
        cout << "Lucky Word\n" << diff;
    } else {
        cout << "No Answer\n0";
    }
    return 0;
}

Pythonic 写法

Counter 统计频次，all 判断质数：

python

1
2
3
4
5
6
7
8
9
10from collections import Counter


def is_prime(x: int) -> bool:
    return x >= 2 and all(x % d for d in range(2, int(x**0.5) + 1))


counts = Counter(input().strip()).values()
difference = max(counts) - min(counts)
print("Lucky Word\n" + str(difference) if is_prime(difference) else "No Answer\n0", end="")

复杂度

设单词长度为 n，计数时间复杂度是 $O(n)$ 。差值最多不超过 n，试除复杂度是 $O(\sqrt n)$ 。空间复杂度是 $O(1)$ ，因为小写字母最多 26 种。

总结

频率题先用 Counter 把出现次数拿出来，再在次数集合上做数学判断。

[NOIP 2008 提高组] 笨小猴

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结