POJ - 3842 An Industrial Spy dfs(水)

題意:給你一串數字，最少一個，最多七個，問用這里面的數字能組成多少素數，不重復。

思路：之前還遍歷10000000的每一個素數，結果超時，后來發現直接dfs就可以了，只是標記一下做過的數。

 1 #pragma comment(linker, "/STACK:1000000000")
 2 #include <bits/stdc++.h>
 3 #define LL long long
 4 #define INF 0x3f3f3f3f
 5 #define IN freopen("in.txt","r",stdin)
 6 #define OUT freopen("out.txt", "w", stdout)
 7 #define MAXN 10000005
 8 using namespace std;
 9 bool vis[MAXN], done[MAXN], has[10];
10 int p[1000005];
11 char s[10];
12 int cnt[15], a[15];
13 int n, ans;
14 void dfs(int m, int res){
15     if(done[res]) return;
16     if(!vis[res]){
17         ans++;
18     }
19     done[res] = true;
20     if(m > n) return;
21     for(int i = 1; i <= n; i++){
22         if(has[i]) continue;
23         has[i] = true;
24         dfs(m + 1, res * 10 + (s[i] - '0'));
25         dfs(m + 1, res);
26         has[i] = false;
27     }
28 }
29 int main()
30 {
31     //IN;
32     //OUT;
33     int T;
34     memset(vis, 0, sizeof(vis));
35     int o = 0;
36     vis[0] = vis[1] = true;
37     for(int i = 2; i <= 3200; i++){
38         if(!vis[i]){
39             p[o++] = i;
40         }
41         for(int j = 2 * i; j <= 10000000; j += i){
42             vis[j] = true;
43         }
44     }
45     scanf("%d", &T);
46     while(T--){
47         //memset(cnt, 0, sizeof(cnt));
48         ans = 0;
49         memset(has, 0, sizeof(has));
50         memset(done, 0, sizeof(done));
51         scanf("%s", s + 1);
52         n = strlen(s + 1);
53         dfs(1, 0);
54         printf("%d\n", ans);
55     }
56     return 0;
57 }

轉載于:https://www.cnblogs.com/macinchang/p/4747861.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/397643.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/397643.shtml
英文地址，請注明出處：http://en.pswp.cn/news/397643.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！