小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!
这种方法的具体描述如下:假设 \text{maxn}maxn 是单词中出现次数最多的字母的出现次数,\text{minn}minn 是单词中出现次数最少的字母的出现次数,如果 \text{maxn}-\text{minn}maxn−minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。
输入格式
一个单词,其中只可能出现小写字母,并且长度小于 100100。
输出格式
共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出 Lucky Word,否则输出 No Answer;
第二行是一个整数,如果输入单词是 Lucky Word,输出 \text{maxn}-\text{minn}maxn−minn 的值,否则输出 00。
(为什么我有两个测试点过不了)
#include
#include
#include
int min(int count[],int len);
int max(int count[],int len);
int main()
{
char a[100000];
int count[100000];
gets(a);
int len = strlen(a);
for (int i = 0; i < len; i++)
{
for (int j = 1; j < len - i; j++)
{
if (a[i] == a[i + j])
{
count[i]++;
}
}
}
for (int i = 0; i < len; i++)
{
for (int j = 1; j < len - i; j++)
{
if (a[i] == a[i + j])
{
count[i+j]= min(count, len);
}
}
}
int s = min(count,len);
int t = max(count, len);
int su = t - s;
int count1 = 0;
if (su == 1)
{
printf("No Answer\n");
printf("0");
}
else if (su == 0)
{
printf("No Answer\n");
printf("0");
}
else if (su ==2||su==3)
{
printf("Lucky Word\n");
printf("%d", su);
}
else {
for (int i = 2; i <= sqrt(su); i++)
{
if (su % i == 0)
{
count1++;
break;
}
}
if (count1 == 0)
{
printf("Lucky Word\n");
printf("%d", su);
}
else
{
printf("No Answer\n");
printf("0");
}
}
return 0;
}
int min(int count[],int len)
{
int m = count[0];
for (int i = 0; i < len; i++)
{
if (count[i] < m)
{
m = count[i];
}
}
return m;
}
int max(int count[], int len)
{
int m = count[0];
for (int i = 0; i < len; i++)
{
if (count[i] > m)
{
m = count[i];
}
}
return m;
}
两个数组的大小:
char a[100000]; 修改为:char a[100101];
int count[100000];修改为:int count[100101];
题主的写法优化下,供参考:
#include <stdio.h>
#include <string.h>
int main()
{
char a[100101] = {0};
int count[26] = { 0 }, maxn, minn, flg = 0;
gets(a);
int len = strlen(a);
for (int i = 0; i < len; i++)
if (a[i] >= 'a' && a[i] <= 'z')
count[a[i] - 'a']++;
for (int i = 0; i < 26; i++)
{
if (count[i] != 0)
{
if (flg == 0) {
maxn = count[i];
minn = count[i];
flg = 1;
}
else {
if (maxn < count[i])
maxn = count[i];
if (minn > count[i])
minn = count[i];
}
}
}
int su = maxn - minn;
if (su <= 1)
{
printf("No Answer\n");
printf("00");
}
else {
flg = 1;
for (int i = 2; i * i <= su; i++)
{
if (su % i == 0)
{
flg = 0;
break;
}
}
if (flg)
{
printf("Lucky Word\n");
printf("%d", su);
}
else
{
printf("No Answer\n");
printf("00");
}
}
return 0;
}