首页 > 其他 > 详细

NOIP2002普及组复赛B 选数

时间:2019-04-22 21:43:02      阅读:251      评论:0      收藏:0      [点我收藏+]

题目链接:https://ac.nowcoder.com/acm/contest/230/B

题目大意:

  略

分析:

  DFS模板题。

代码如下:

技术分享图片
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define rep(i,n) for (int i = 0; i < (n); ++i)
 5 #define For(i,s,t) for (int i = (s); i <= (t); ++i)
 6 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
 7 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
 8 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
 9  
10 #define pr(x) cout << #x << " = " << x << "  "
11 #define prln(x) cout << #x << " = " << x << endl
12  
13 #define ALL(x) x.begin(),x.end()
14 #define INS(x) inserter(x,x.begin())
15  
16 #define ms0(a) memset(a,0,sizeof(a))
17 #define msI(a) memset(a,inf,sizeof(a))
18  
19 #define pii pair<int,int>
20 #define piii pair<pair<int,int>,int>
21 #define mp make_pair
22 #define pb push_back
23 #define fi first
24 #define se second
25  
26 inline int gc(){
27     static const int BUF = 1e7;
28     static char buf[BUF], *bg = buf + BUF, *ed = bg;
29      
30     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
31     return *bg++;
32 }
33  
34 inline int ri(){
35     int x = 0, f = 1, c = gc();
36     for(; c<48||c>57; f = c==-?-1:f, c=gc());
37     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
38     return x*f;
39 }
40  
41 typedef long long LL;
42 const int maxN = 1e5 + 7;
43  
44 int n, k, ans;
45 int x[21];
46  
47 bool isPrime(int x) {
48     assert(x > 1);
49     For(i, 2, (int)(sqrt(x) + 1e-6)){
50         if(x % i == 0) return false;
51     }
52     return true;
53 }
54  
55 void dfs(int a, int cnt, int sum) {
56     if(cnt == k) {
57         if(isPrime(sum)) ++ans;
58         return;
59     }
60     if(a > n) return;
61      
62     dfs(a+1, cnt+1, sum+x[a]);
63     dfs(a+1, cnt, sum);
64 }
65  
66 int main(){
67     scanf("%d%d", &n, &k);
68     For(i, 1, n) x[i] = ri();
69      
70     dfs(1, 0, 0);
71      
72     printf("%d\n", ans);
73     return 0;
74 }
View Code

 

NOIP2002普及组复赛B 选数

原文:https://www.cnblogs.com/zaq19970105/p/10753047.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!