笨小猴

题意

若单词字符最高频与最低频的差是质数，输出 Lucky Word 和该差。

思路

Counter 统计频率，取值集合的最大最小值相减。质数需至少为 $2$ ，再试除到平方根。

代码

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/*-----------------
* author: Rainboy
* email: rainboylvx@qq.com
* time: 2019年 05月 07日 星期二 14:42:03 CST
* problem: luogu-1125
*----------------*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

char word[200];
int cnt[255] = {0};

bool isprime(int n){
    int i;
    if( n <2)
        return false;
    for(i=2;i<=sqrt(n);i++)
        if( n % i ==0)
            return false;
    return true;
}

int main(){
    scanf("%s",word);
    int _min = 0x7f7f7f7f,_max = 1;

    int len = strlen(word);
    int i;
    for (i=0;i<len;i++){
        cnt[ word[i] ]++;
    }

    for(i='a';i<='z';i++)
    {
        if( cnt[i] !=0)
            _min = min( cnt[i],_min);
        _max = max(_max,cnt[i]);
    }
    int a = _max - _min;
    if( isprime(a)){
        printf("Lucky Word\n");
        printf("%d\n",_max-_min);
    }
    else {
        printf("No Answer\n");
        printf("0");
    }

    return 0;
}

复杂度

总结

Python代码

python

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

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

is_prime = difference >= 2 and all(difference % divisor for divisor in range(2, int(difference**0.5) + 1))
print("Lucky Word" if is_prime else "No Answer")
print(difference if is_prime else 0)

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/*-----------------
* author: Rainboy
* email: rainboylvx@qq.com
* time: 2019年 05月 07日 星期二 14:42:03 CST
* problem: luogu-1125
*----------------*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

char word[200];
int cnt[255] = {0};

bool isprime(int n){
    int i;
    if( n <2)
        return false;
    for(i=2;i<=sqrt(n);i++)
        if( n % i ==0)
            return false;
    return true;
}

int main(){
    scanf("%s",word);
    int _min = 0x7f7f7f7f,_max = 1;

    int len = strlen(word);
    int i;
    for (i=0;i<len;i++){
        cnt[ word[i] ]++;
    }

    for(i='a';i<='z';i++)
    {
        if( cnt[i] !=0)
            _min = min( cnt[i],_min);
        _max = max(_max,cnt[i]);
    }
    int a = _max - _min;
    if( isprime(a)){
        printf("Lucky Word\n");
        printf("%d\n",_max-_min);
    }
    else {
        printf("No Answer\n");
        printf("0");
    }

    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，计数空间为 $O(26)$ 。

总结

频次差为 $0$ 或 $1$ 时都不是质数。

目录

题意

思路

代码

复杂度

总结

Python代码

C++代码

复杂度

总结