[NOIP2008-提高] 笨小猴

题目描述

给定一个只含小写字母、长度小于 $100$ 的单词，设 maxn 为出现次数最多的字母的出现次数，minn 为出现次数最少的字母的出现次数（都只在出现过的字母中比较）。输入一行一个单词；若 maxn - minn 是质数，输出两行 Lucky Word 与 maxn - minn，否则输出 No Answer 与 0。

样例 1：error → Lucky Word / 2；样例 2：olympic → No Answer / 0。

思路

统计每个出现过的字母的出现次数，取最大值与最小值之差 diff，再用试除法判断 diff 是否为质数即可，注意 $0$ 和 $1$ 都不是质数。单词长度不足 $100$ ，怎么写都能通过。

参考代码

Python 版：

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
25
26
27
28
29
30
31#!/usr/bin/env python3
# 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-10-02 08:01
# update_at: 2026-10-04 12:51

import sys
from collections import Counter


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    word = next(data)  # 题面只给一个单词，取第一个 token

    cnt = Counter(word)  # 每个小写字母在单词里出现的次数
    diff = max(cnt.values()) - min(cnt.values())  # maxn - minn

    # 试除判断质数：diff 为 0 或 1 时直接判否，枚举到 sqrt(diff) 为止
    is_prime = diff >= 2 and all(diff % i for i in range(2, int(diff**0.5) + 1))

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


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * 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-10-06 14:04
 * update_at: 2026-10-06 14:04
 */
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

int cnt[26]; // cnt[i] 表示字母 ('a' + i) 在单词中出现的次数

// 判断 x 是否为质数，x 为 0 或 1 时直接返回 false
bool is_prime(ll x) {
    if (x < 2) {
        return false;
    }
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    string word;
    cin >> word;

    // 统计每个字母出现的次数
    ll len = word.size();
    for (ll i = 0; i < len; i++) {
        cnt[word[i] - 'a']++;
    }

    // maxn 与 minn 都只在出现过的字母之间比较
    ll maxn = 0;
    ll minn = -1;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > 0) {
            if (cnt[i] > maxn) {
                maxn = cnt[i];
            }
            if (minn == -1 || cnt[i] < minn) {
                minn = cnt[i];
            }
        }
    }

    ll diff = maxn - minn;
    if (is_prime(diff)) {
        cout << "Lucky Word" << "\n";
        cout << diff << "\n";
    } else {
        cout << "No Answer" << "\n";
        cout << 0 << "\n";
    }

    return 0;
}

[NOIP2008-提高] 笨小猴

目录

题目描述

思路

参考代码