【基础练习】【搜索】codevs1008 选数题解

柔情只为你懂 2022-08-09 06:53 100阅读 0赞

题目描述 Description

已知 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）。

输入描述 Input Description

键盘输入，格式为：  
　　n , k （1<=n<=20，k＜n）  
　　x1,x2，…,xn （1<=xi<=5000000）

输出描述 Output Description

屏幕输出，格式为：  
　　一个整数（满足条件的种数）。

样例输入 Sample Input

4 3  
3 7 12 19

样例输出 Sample Output

数据范围及提示 Data Size & Hint

（1<=n<=20，k＜n）  
（1<=xi<=5000000）

一道很简单的搜索题，然而我却WA了5次···

不要判重！不要判重！不要判重！

//codevs1008 Ñ¡Êý ËÑË÷
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
        
          #include using namespace std; const int maxn=20+10; int a[maxn]; bool used[maxn]; int ans=0; int n,k; int e; bool prime(int x) { for (int i=2;i<=trunc(sqrt(x));i++) if (x%i==0) return false; return true; } void search(int depth,int now,int last) { if (depth==k) { if (prime(now)) ans++; //printf("%d\n",now); return; } for (int i=last;i<=n;i++) { if (!used[i]) { depth++; now+=a[i]; used[i]=true; search(depth,now,i+1); now-=a[i]; depth--; used[i]=false; } } } int main() { freopen("1.txt","r",stdin); freopen("2.txt","w",stdout); scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); } search(0,0,1); printf("%d",ans); return 0; }

——寂寞天宝后，园庐但蒿藜