P1036 选数

admin

https://www.luogu.org/problemnew/show/P1036
题目描述
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：

3＋7＋12=22

3＋7＋19＝29

7＋12＋19＝38

3＋12＋19＝34。

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3＋7＋19＝29）。

输入输出格式
输入格式：
键盘输入，格式为：

n , k （1<=n<=20，k＜n）

x1,x2，…,xn （1<=xi<=5000000）

输出格式：
屏幕输出，格式为：

一个整数（满足条件的种数）。

输入输出样例
输入样例#1：
4 3
3 7 12 19
输出样例#1：
1

吴语林

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <algorithm>
   
4. #include <iostream>  
   
5. #include <cmath>  
   
6. #include <cstring>  
   
7. #include <set>  
   
8. using namespace std;
   
9. bool ku[100000001]={0},book[30]={0};
   
10. int num=0,n,k,a[30];
    
11. void dfs(int t,int s,int l)
    
12. {
    
13.     int i;
    
14.         if(t==k)
    
15.         {
    
16.                 if(!ku[s])
    
17.                         num++;
    
18.         }
    
19.         else
    
20.                 for(i=l+1;i<=n;i++)
    
21.                 {
    
22.                         if(!book[i])
    
23.                         {
    
24.                                 book[i]=1;
    
25.                                 dfs(t+1,s+a[i],i);
    
26.                                 book[i]=0;
    
27.                         }
    
28.                 }
    
29. }
    
30. int main()  
    
31. {
    
32.         long long all=0;
    
33.         scanf("%d %d",&n,&k);
    
34.         for(int i=1;i<=n;i++)
    
35.         {
    
36.                 scanf("%d",&a[i]);
    
37.                 all+=a[i];
    
38.         }
    
39.         for(long long i=2;i<=all;i++)
    
40.         {
    
41.                 for(long long j=2;j<=all;j++)
    
42.                 {
    
43.                         if(i*j<=100000000&&!ku[i*j])
    
44.                                 ku[i*j]=1;
    
45.                 }
    
46.         }
    
47.         for(int i=1;i<=n;i++)
    
48.         {
    
49.                 book[i]=1;
    
50.                 dfs(1,a[i],i);
    
51.         }
    
52.         printf("%d",num);
    
53.         return 0;  
    
54. }  

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int n,k,a[21],s,t;
   
5. bool f[21];
   
6. bool ss(int p)
   
7. {
   
8.     int i=2;
   
9.     while(i<=sqrt(p))
   
10.     {
    
11.         if(p%i==0)return 0;
    
12.         i++;
    
13.     }
    
14.     return 1;
    
15. }
    
16. int xs(int num,int i)
    
17. {
    
18.     for(int j=i; j<=n; j++)
    
19.         if(f[j])
    
20.         {
    
21.             f[j]=0;
    
22.             s+=a[j];
    
23.             if(num==k)
    
24.             {
    
25.                 if(ss(s))t++;
    
26.             }
    
27.             else xs(num+1,j+1);
    
28.             s-=a[j];
    
29.             f[j]=1;
    
30.         }
    
31. }
    
32. int main()
    
33. {
    
34.     cin>>n>>k;
    
35.     for(int i=1; i<=n; i+=1)
    
36.     {
    
37.         cin>>a[i];
    
38.         f[i]=1;
    
39.     }
    
40.     xs(1,1);
    
41.     cout<<t;
    
42.     return 0;
    
43. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. int x[20],n,k;
   
3. int judge(int n)
   
4. {
   
5.     for(int i=2;i*i<=n;i++)
   
6.         if(n%i==0)
   
7.                         return 0;
   
8.     return 1;
   
9. }
   
10. int cal(int left,int count,int begin,int end)
    
11. {
    
12.     if(left==0)
    
13.                 return judge(count);
    
14.     int sum=0;
    
15.     for(int i=begin;i<=end;i++)
    
16.         sum+=cal(left-1,count+x[i],i+1,end);
    
17.     return sum;
    
18. }
    
19. int main()
    
20. {
    
21.         scanf("%d%d",&n,&k);
    
22.         for(int i=0;i<n;i++)
    
23.                 scanf("%d",&x[i]);
    
24.         int ans=cal(k,0,0,n-1);
    
25.         printf("%d",ans);
    
26.         return 0;
    
27. }

复制代码

wzd(temp)

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <cmath>
   
4. using namespace std;
   
5. const int N=24;
   
6. struct node
   
7. {
   
8.         int v;
   
9.         bool x;
   
10. }a[N];
    
11. int n,k;
    
12. void init()
    
13. {
    
14.         scanf("%d %d",&n,&k);
    
15.         for(int i=0;i<n;i++)
    
16.         {
    
17.                 scanf("%d",&a[i].v);
    
18.                 a[i].x=true;
    
19.         }
    
20.        
    
21.         return ;
    
22. }
    
23. bool is_prime(const long long & lmd)
    
24. {
    
25.         for(int kk=2;kk<=sqrt(lmd);kk++)
    
26.                 if(lmd%kk==0)
    
27.                         return false;
    
28.         return true;
    
29. }
    
30. 
    
31. long long orz=0;
    
32. long long dfs(int i,int q)
    
33. {
    
34.         if(n-q<k-i)
    
35.                 return 0;
    
36.        
    
37.         if(i==k)
    
38.         {
    
39.                 if(is_prime(orz))
    
40.                         return 1;
    
41.                 return 0;
    
42.         }
    
43. 
    
44.         long long temp=0;
    
45.         for(int j=q;j<n;j++)
    
46.         {
    
47.                 if(a[j].x)
    
48.                 {
    
49.                         orz+=a[j].v; a[j].x=false;
    
50.                         temp+=dfs(i+1,j+1);
    
51.                         orz-=a[j].v; a[j].x=true;
    
52.                 }
    
53.         }
    
54.         return temp;
    
55. }
    
56. int main()
    
57. {
    
58.         init();
    
59. 
    
60.         printf("%lld\n",dfs(0,0));
    
61.         return 0;
    
62. }

复制代码

admin

都做得不错！但是怎么感觉大家的都好复杂的样子？看我的：

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int mn=21,mk=21;
   
5. int a[mn],aa[mn];
   
6. int n,k,s,sum;
   
7. bool isprime(int x)
   
8. {
   
9.     if (x==1 || x==0) return 0;   ///虽然此题没有必要，但是时时要小心！！！
   
10.     int i=2;
    
11.     bool b=1;
    
12.     while (i<=sqrt(x) && b)
    
13.         if (x%i==0) b=0;
    
14.         else i++;
    
15.     return b;
    
16. }
    
17. void dfs(int i,int sum)
    
18. {
    
19.     int j,kk;
    
20.     if (i>=k+1)
    
21.     {
    
22.         ///cout<<sum<<' ';
    
23.         if (isprime(sum)) s++;
    
24.     }
    
25.     else for (kk=a[i-1]+1; kk<=n; kk++)   ///不能重复选择的技巧
    
26.         {
    
27.             a[i]=kk;
    
28.             dfs(i+1,sum+aa[kk]);
    
29.         }
    
30. }
    
31. int main()
    
32. {
    
33.     cin>>n>>k;
    
34.     for (int i=1; i<=n; i++) cin>>aa[i];
    
35.     dfs(1,0);
    
36.     cout<<s;
    
37. }
    

复制代码

lyc

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cmath>
   
4. const int maxn = 25;
   
5. using namespace std;
   
6. bool isprime(int x)
   
7. {
   
8.     for(int i=2; i<=sqrt(x); i++)
   
9.         if(x%i == 0) return false;
   
10.     return true;
    
11. }
    
12. int a[maxn];
    
13. int n,k;
    
14. int ans;
    
15. void dfs(int cnt, int sum, int now)
    
16. {
    
17.     if(cnt == k || now == n+1)
    
18.     {
    
19.         if(isprime(sum) && cnt == k)
    
20.             ans++;
    
21.         return;
    
22.     }
    
23.     dfs(cnt+1, sum+a[now], now+1);
    
24.     dfs(cnt, sum, now+1);
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>n>>k;
    
29.     for(int i=1; i<=n; i++)
    
30.     {
    
31.         cin>>a[i];
    
32.     }
    
33.     dfs(0, 0, 1);
    
34.     cout<<ans;
    
35.     return 0;
    
36. }
    

复制代码

冯文韬

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int a[25];
   
5. int n,k,ans;
   
6. bool zs(int x){
   
7.         if (x<2) return false;
   
8.         for (int i=2;i<=sqrt(x);i++)
   
9.             if(x%i==0) return false;
   
10.         return true;
    
11. }
    
12. 
    
13. void search(int total,int i,int m){
    
14.         if (m==k&&zs(total)) ans++;
    
15.         if (m<k&&k-m<n-i+1) {
    
16.                 search(total+a[i],i+1,m+1);
    
17.                 search(total,i+1,m);
    
18.         }
    
19.         if (m<k&&k-m>=n-i+1) search(total+a[i],i+1,m+1);
    
20. }
    
21. 
    
22. int main(){
    
23.         cin>>n>>k;
    
24.         for (int i=1;i<=n;i++) cin>>a[i];
    
25.         search(0,1,0);
    
26.         cout<<ans<<endl;
    
27.         return 0;
    
28. }

复制代码

张笑宇

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int mx=21;
   
5. int a[mx],aa[mx];
   
6. int sum,n,k,s;
   
7. int isprime(int x)
   
8. {
   
9.     int i=2;
   
10.     bool b=true;
    
11.     if (x==0 || x==1) return 0;
    
12.     else
    
13.     {
    
14.         while (i<=sqrt(x) && b)
    
15.         {
    
16.             if (x%i==0) b=false;
    
17.             i++;
    
18.         }
    
19.     }
    
20.     return b;
    
21. }
    
22. void dfs(int i,int sum)
    
23. {
    
24.     int j,kk;
    
25.     if (i>=k+1)
    
26.     {
    
27.         if (isprime(sum)) s++;
    
28.     }
    
29.     else
    
30.     {
    
31.         for (kk=a[i-1]+1; kk<=n; kk++)
    
32.         {
    
33.             a[i]=kk;
    
34.             dfs(i+1,sum+aa[kk]);
    
35.         }
    
36.     }
    
37. }
    
38. int main()
    
39. {
    
40.     cin>>n>>k;
    
41.     for (int i=1; i<=n; i++) cin>>aa[i];
    
42.     dfs(1,0);
    
43.     cout<<s;
    
44.     return 0;
    
45. }
    
46. 
    

复制代码

liubo

1. #include<iostream>
   
2. using namespace std;
   
3. int num[25],pick[25],n,k,ans;
   
4. bool vis[25];
   
5. bool is_prime(int x){
   
6.     int i;
   
7.     for(i = 2;i * i <= x;i++)
   
8.         if(x % i == 0) return 0;
   
9.     return 1;
   
10. }
    
11. void dfs(int tar){
    
12.     if(tar > k){
    
13.         int sum = 0;
    
14.         for(int i = 1;i <= k;i++)
    
15.             sum += num[pick[i]];
    
16.         //cout << sum << " ";
    
17.         if(is_prime(sum)) ans++;
    
18.     }
    
19.     else{
    
20.         for(int i = pick[tar - 1];i <= n;i++){
    
21.             if(!vis[i]){
    
22.                 vis[i] = 1;
    
23.                 pick[tar] = i;
    
24.                 dfs(tar + 1);
    
25.                 vis[i] = 0;
    
26.             }
    
27.         }
    
28.     }
    
29. }
    
30. int main(){
    
31.     cin >> n >> k;
    
32.     for(int i = 1;i <= n;i++)
    
33.         cin >> num[i];
    
34.     pick[0] = 1;
    
35.     dfs(1);
    
36.     cout << ans;
    
37.     return 0;
    
38. }

复制代码