P1125 笨小猴 题解
P1125 in Luogu
题意简化
你需要判断一个由小写字母组成的单词是否是“Lucky Word”。
判断方法如下：
- 统计这个单词中每个字母的出现次数。
- 找出出现次数最多的字母的出现次数，记作
maxn。
- 找出出现次数最少的字母的出现次数，记作
minn。
- 计算差值：
diff = maxn - minn
- 判断这个差值
diff 是否是质数：
- 如果是质数，则输出
"Lucky Word" 和该差值；
- 如果不是质数，则输出
"No Answer" 和 0。
思路
本题为模拟题，可以直接按照题目要求写代码，分为三个函数。
maxx 函数：用于计算最多的字母的出现次数。
minn 函数：用于计算最少的字母的出现次数（注意不能是0）。
is_prime 函数：用于计算是否为素数。
maxx 函数
可以用桶的思想，每读到1个字母就把他的字母表号加入至桶中。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int maxx(string s){
int a[30];
memset(a,0,sizeof(a));
int len = s.size();
for(int i=0;i<len;i++){
a[s[i]-'a'] ++;
}
int maxa = -1e9;
for(int i=1;i<=26;i++){
maxa = max(maxa,a[i]);
}
return maxa;
}
|
minn 函数
同理，一定注意不能为0（我因此WA过）！！
1
2
3
4
5
6
7
8
9
10
11
12
13
| int minn(string s){
int a[30];
memset(a,0,sizeof(a));
int len = s.size();
for(int i=0;i<len;i++){
a[s[i]-'a'] ++;
}
int mina = 1e9;
for(int i=1;i<=26;i++){
mina = min(mina,a[i]);
}
return mina;
}
|
is_prime 函数
直接用简短的 筛法。
1
2
3
4
5
6
7
8
9
| bool is_prime(int n){
if(n < 2) return false;
for(int i=2;i<=sqrt(n);i++){
if(n % i == 0){
return false;
}
}
return true;
}
|
AC code:
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3fffffff;
int maxx(string s){
int a[30];
memset(a,0,sizeof(a));
int len = s.size();
for(int i=0;i<len;i++){
a[s[i]-'a'] ++;
}
int maxa = -1e9;
for(int i=1;i<=26;i++){
maxa = max(maxa,a[i]);
}
return maxa;
}
int minn(string s){
int a[30];
memset(a,0,sizeof(a));
int len = s.size();
for(int i=0;i<len;i++){
a[s[i]-'a'] ++;
}
int mina = 1e9;
for(int i=1;i<=26;i++){
mina = min(mina,a[i]);
}
return mina;
}
bool is_prime(int n){
if(n < 2) return false;
for(int i=2;i<=sqrt(n);i++){
if(n % i == 0){
return false;
}
}
return true;
}
int main(){
string s;
cin >> s;
int cnt = maxx(s) - minn(s);
if(is_prime(cnt)){
cout << "Lucky Word" << endl;
cout << cnt << endl;
} else{
cout << "No Answer" << endl;
cout << 0 << endl;
}
return 0;
}
|
