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

小山童鞋

人造人 发表于 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了*/

1. #include<stdio.h>
   
2. #include<string.h>
   
3. #include<stdlib.h>
   
4. #define MAX 1000001
   
5. 
   
6. char s[50];
   
7. char a[MAX];
   
8. int maxlen;
   
9. void deal()
   
10. {
    
11.     int i,j;
    
12.     a[0] = a[1] = '0';
    
13.     for (i = 2; i <= MAX-1; i++) a[i] = '1';
    
14.     for (i = 2; i <= MAX-1; i++)
    
15.       if (a[i] == '1')
    
16.         for (j = 2; i*j <= MAX-1; j++)
    
17.           a[i*j] = '0';
    
18. }
    
19. 
    
20. void work(int head, int len, int tot)
    
21. {
    
22.     int num = 0, i;
    
23.     num = tot*10;
    
24.     num += s[head+len-1]-48;
    
25.     if (head == 0 && len == 6 && a[num] == '0') {printf("NO"); exit(0);}
    
26.     if (head + len == maxlen && a[num] == '1') {printf("YES"); exit(0);}
    
27.     if (a[num] == '1') work(head+len, 1, 0);
    
28.     if (head+len != maxlen && head+len+1 <= maxlen && len+1 <= 6)
    
29.       work(head, len+1, num);
    
30. 
    
31.     return;
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.     deal();
    
37.     gets(s);
    
38.     maxlen = strlen(s);
    
39.     work(0, 1, 0);
    
40.     printf("NO\n");
    
41. 
    
42.     return 0;
    
43. }

复制代码

小山童鞋

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

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

honhon

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

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