华师一附中OI组

标题: P1036 选数 [打印本页]
作者: admin    时间: 2018-5-11 10:49
标题: P1036 选数
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

作者: 吴语林    时间: 2018-5-12 11:37
  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. }  
复制代码
作者: 黄煦喆    时间: 2018-5-13 21:05
  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    时间: 2018-5-13 22:06
  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)    时间: 2018-5-13 22:37
  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. }

  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.         }

  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();

  60.         printf("%lld\n",dfs(0,0));
  61.         return 0;
  62. }
复制代码
作者: admin    时间: 2018-5-13 22:49
都做得不错！但是怎么感觉大家的都好复杂的样子？看我的：
  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    时间: 2018-5-13 22:52
  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. }
复制代码
作者: 冯文韬    时间: 2018-5-13 23:12
  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. }

  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. }

  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. }
复制代码
作者: 张笑宇    时间: 2018-5-15 22:39
  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. }

复制代码
作者: liubo    时间: 2018-5-21 23:17
  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. }
复制代码
作者: Scorpio    时间: 2018-6-28 21:35
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. long long a[24],ia[24];
  5. long long i,n,k,p;
  6. void hhh(int i)
  7. {
  8.     int j,kk,b=0,s=0;
  9.     if(i>=k+1)
  10.     {
  11.         for(j=1;j<=i;j++)
  12.             s=s+a[ia[j]];
  13.         for(j=2;j<=sqrt(s);j++)
  14.             if(s%j==0)
  15.                 b=1;
  16.         if(b==0)
  17.             p++;
  18.         s=0;
  19.     }
  20.     else for(kk=ia[i-1]+1;kk<=n;kk++)
  21.     {
  22.         ia[i]=kk;
  23.         hhh(i+1);
  24.     }
  25. }
  26. int main()
  27. {
  28.     cin>>n>>k;
  29.     for(i=1;i<=n;i++)
  30.         cin>>a[i];
  31.     hhh(1);
  32.     cout<<p;
  33.     return 0;
  34. }
复制代码
作者: diggersun    时间: 2018-9-14 19:22
  1. #include <iostream>
  2. using namespace std;
  3. const int mm=22;
  4. int a[mm],aa[mm];
  5. int n,k,s,ss;
  6. int p[10000];
  7. int bb[10000];
  8. void getp()
  9. {
  10.     int i,j;
  11.     for ( i=2; i<=9999; i++)
  12.         for ( j=i; i*j<=9999; j++) bb[i*j]=1;
  13.     j=1;
  14.     for (int i=2; i<=9999; i++) if (!bb[i]) p[j++]=i;
  15.     ///for (i=1;i<=j;i++) cout<<p[i]<<' ';
  16. }
  17. bool isprime(int x)
  18. {
  19.     int i=1;
  20.     bool b=1;
  21.     if (x<=1) b=0;
  22.     else while (p[i]*p[i]<=x && b)
  23.             if (x%p[i]==0) b=0;
  24.             else i++;
  25.     return b;

  27. }
  28. void cmn(int i)
  29. {
  30.     int j,t;
  31.     if (i>k)
  32.     {
  33.         for (s=0,j=1; j<=k; j++)  s+=aa[a[j]];
  34.         if (isprime(s)) ss++;
  35.     }
  36.     else for (t=a[i-1]+1; t<=n; t++)
  37.         {
  38.             a[i]=t;
  39.             cmn(i+1);
  40.         }
  41. }
  42. int main()
  43. {
  44.     getp();
  45.     cin>>n>>k;
  46.     for (int i=1; i<=n; i++) cin>>aa[i];
  47.     cmn(1);
  48.     cout<<ss;
  49.     return 0;
  50. }
复制代码
作者: universehyf    时间: 2018-9-16 13:42
  1. 刚才发错了[code]#include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. int n,k,ii,s;
  5. long long c;
  6. int a[25]={};
  7. bool b[25];
  8. bool sushu(int x)
  9. {
  10.         int y=sqrt(x);
  11.         for(int z=2;z<=y;z++)
  12.                 if(x%z==0)
  13.                         return false;
  14.         return true;
  15. }
  16. void mysearch(int i)
  17. {
  18.     int j;
  19.     if (i==k) {if(sushu(s))c++;}
  20.     else
  21.         for (j=0; j<=n-1; j++)
  22.         {
  23.             if (b[j])
  24.             {
  25.                 s+=a[j];
  26.                 b[j]=false;
  27.                 mysearch(i+1);
  28.                 b[j]=true;
  29.                 s-=a[j];
  30.             }
  31.         }
  32. }
  33. int main()
  34. {
  35.     cin>>n>>k;
  36.     for(ii=0;ii<=n-1;ii++) {cin>>a[ii];b[ii]=true;}
  37.     mysearch(0);
  38.     cout<<c;
  39.     return 0;
  40. }
复制代码
[/code]
作者: admin    时间: 2018-9-16 19:20
何宇峰你的bool sushu(int x)有重大隐患，x=1不能判断
作者: 朱品屹    时间: 2020-8-5 11:13
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[25],aa[25],n,k,x=0,num=0;
  4. bool b[25];
  5. bool isprime(int x)
  6. {
  7.         for(int i=2;i<=sqrt(x);i++)
  8.                 if(x%i==0)
  9.                         return 0;
  10.         return 1;
  11. }
  12. void dfs(int i)
  13. {
  14.         if(i>k)
  15.         {
  16.                 x=0;
  17.                 for(int i=1;i<=k;i++)
  18.                         x+=a[aa[i]];
  19.                 if(isprime(x))
  20.                         num++;
  21.                 //cout<<a[aa[1]]<<' '<<a[aa[2]]<<' '<<a[aa[3]]<<' '<<x<<' '<<num<<endl;
  22.         }
  23.         else
  24.         {
  25.                 for(int j=aa[i-1]+1;j<=n;j++)
  26.                 {
  27.                         if(b[j]==1)
  28.                         {
  29.                                 aa[i]=j;
  30.                                 b[j]=0;
  31.                                 dfs(i+1);
  32.                                 b[j]=1;
  33.                         }
  34.                 }
  35.         }
  36. }
  37. int main()
  38. {
  39.         cin>>n>>k;
  40.         for(int i=1;i<=n;i++)
  41.         {
  42.                 cin>>a[i];
  43.                 b[i]=1;
  44.         }
  45.         dfs(1);
  46.         cout<<num<<endl;
  47.         return 0;
  48. }
复制代码
作者: 弑魔者魔眼    时间: 2020-8-12 11:56
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[30];
  4. bool check(int x)
  5. {
  6.         for(int i=2;i*i<=x;i++)
  7.         if(x%i==0) return 0;
  8.         return 1;
  9. }

  11. int main()
  12. {
  13.         int n,k,ans=0;
  14.         cin>>n>>k;
  15.         for(int i=0;i<n;i++) cin>>a[i];
  16.         int U=1<<n;
  17.         for(int S=0;S<U;S++)
  18.         if(__builtin_popcount(S)==k)
  19.         {
  20.                 int sum=0;
  21.                 for(int i=0;i<n;i++)
  22.                 if(S&(1<<i)) sum+=a[i];
  23.                 if(check(sum)) ans++;
  24.         }
  25.         cout<<ans;
  26.         return 0;
  27. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2