一道竞赛题，想了两天无果，虽然考试结束，我还是希望得到指点

小山童鞋

人造人 发表于 2016-12-17 12:47
你指的是？

你这个只判断了能不能在这个字符串里找到一个素数，而不是能不能划分成几个素数。你的代码只要再改一改也可以的。

人造人

小山童鞋 发表于 2016-12-17 18:50
你这个只判断了能不能在这个字符串里找到一个素数，而不是能不能划分成几个素数。你的代码只要再改一改也 ...

谢谢，我完全理解错题了

小山童鞋

人造人 发表于 2016-12-17 20:23
谢谢，我完全理解错题了

也是碰巧最近在练习这种搜索的题

honhon

小山童鞋 发表于 2016-12-17 18:39
我也是ACM的，大一的，创个帐号应该能提交的。。。。

下面的代码如果提交不能AC那我再改改。。

好厉害，同样大一，差别怎么这么大。。。。你高中就玩编程了码

小山童鞋

honhon 发表于 2016-12-17 22:48
好厉害，同样大一，差别怎么这么大。。。。你高中就玩编程了码

hhhh,只是最近刚弄懂这种搜索题的套路。。

小山童鞋

honhon 发表于 2016-12-17 22:48
好厉害，同样大一，差别怎么这么大。。。。你高中就玩编程了码

话说，能AC吗？不能的话我再改改。

honhon

小山童鞋 发表于 2016-12-17 23:43
话说，能AC吗？不能的话我再改改。

不行，报超时了，我用100009试要1+秒

honhon

honhon 发表于 2016-12-17 23:52
不行，报超时了，我用100009试要1+秒

应该是如果素数是六位数就会超时

honhon

小山童鞋 发表于 2016-12-17 18:39
我也是ACM的，大一的，创个帐号应该能提交的。。。。

下面的代码如果提交不能AC那我再改改。。

学校oj账号是学校给的学号，没办法自己创建。。

小山童鞋

honhon 发表于 2016-12-17 23:52
不行，报超时了，我用100009试要1+秒

没问题啊秒出结果啊…………………………

honhon

小山童鞋 发表于 2016-12-18 21:17
没问题啊秒出结果啊…………………………

/*有可能这样一种情况：很多次的调用字符转换成数字的函数，不然我也不知道了，参考你的素数表的方法，我也写了一个，AC了*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1000001

char s[50];
char a[MAX];
int maxlen;
void deal()
{
    int i,j;
    a[0] = a[1] = '0';
    for (i = 2; i <= MAX-1; i++) a[i] = '1';
    for (i = 2; i <= MAX-1; i++)
      if (a[i] == '1')
        for (j = 2; i*j <= MAX-1; j++)
          a[i*j] = '0';
}

void work(int head, int len, int tot)
{
    int num = 0, i;
    num = tot*10;
    num += s[head+len-1]-48;
    if (head == 0 && len == 6 && a[num] == '0') {printf("NO"); exit(0);}
    if (head + len == maxlen && a[num] == '1') {printf("YES"); exit(0);}
    if (a[num] == '1') work(head+len, 1, 0);
    if (head+len != maxlen && head+len+1 <= maxlen && len+1 <= 6)
      work(head, len+1, num);

    return;
}

int main()
{
    deal();
    gets(s);
    maxlen = strlen(s);
    work(0, 1, 0);
    printf("NO\n");

    return 0;
}

小山童鞋

honhon 发表于 2016-12-18 21:27
/*有可能这样一种情况：很多次的调用字符转换成数字的函数，不然我也不知道了，参考你的素数表的方法，我 ...

看不太懂你的代码。。。。

honhon

小山童鞋 发表于 2016-12-19 10:19
看不太懂你的代码。。。。

写得太乱，具体思路是递归递归，中途满足条件就中断