笨小猴

洛谷·深入浅出 · 代码 · cpp · 难度 2/5 · 共 895 字

统计字母出现最多次与最少次之差，若为质数则 Lucky Word

洛谷
例题

正文

// 原题：https://oj.yecheng.tv/p/1416
// 题意：输入一个单词（全小写）。maxn 为出现最多的字母次数，minn 为出现最少的字母次数。
//       若 maxn-minn 是质数输出 Lucky Word 及其差，否则输出 No Answer 和 0。
// 思路：桶统计 26 个字母频次，取最大值与最小值；再用试除法判质数（注意 0/1 不是质数）。
// 复杂度：O(n + sqrt(n))。
// 易错点：minn 只统计“出现过”的字母，没出现的不能算 0 次；2 是质数但 0、1 不是。
#include <iostream>
#include <string>
using namespace std;
bool isprime(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(){
    string s;
    cin >> s;
    int cnt[26] = {0};
    for(char c : s) cnt[c - 'a']++;
    int mx = 0, mn = 100;
    for(int i = 0; i < 26; i++){
        if(cnt[i] > 0){
            if(cnt[i] > mx) mx = cnt[i];
            if(cnt[i] < mn) mn = cnt[i];
        }
    }
    int d = mx - mn;
    if(isprime(d)) cout << "Lucky Word" << endl << d << endl;
    else cout << "No Answer" << endl << 0 << endl;
    return 0;
}

笨小猴

正文

洛谷·深入浅出的其它内容