Luogu-P1036 选数

川长思鸟来 2022-11-03 00:43 138阅读 0赞

# P1036 选数 #

--------------------

## [原题题意][Link 1] ##

--------------------

### 题解 ###

因为需要从n个数中取出m个进行相加，所以需要求出组合C(n,m)的个数，再对产生的和进行素数的判断。

我的解法：利用DFS来从n个数中取出m个数来(PS: 在这里误求成了全排列，导致错误一直灭找到QAQ)，要求C(n,m),那么选取的规则可以是这样的：每次选择的数的序号都不会比当前的大，例如，1，2，3中选出2个，那么选了1，就只能选2或3；选了2，就只能选3，而不能选1；同样，选了3，就不能选1和2。所以我在solve中加了一个变量l，来代表序号。

*  solve函数中m代表已经选了的个数，如果m>k，那么便已经选完了，这时便可进行素数的判断。
 *  solve函数中r代表的是所选数的和，当m满足条件时，就需要判断r是否是素数。如果是ans++。
 *  solve函数中l变量上面提到，就是代表当前选择的数的序号，确保下面的for循环是从l开始往后找的。

--------------------

### 代码 ###

#include <bits/stdc++.h>
    #define ll long long
    #define MAX_INT 2147483647
    using namespace std;
    
    int n,k,ans[10000],cnt=0,test=0,ans1=0;
    int t[30];
    int a[30],f[30];
    
    int isPrime(int num){
        for(int i=2; i<=(int)sqrt(num); i++){
            if(num % i == 0){
                return 0;
            }
        }
        return 1;
    }
    //实现组合(https://baike.baidu.com/item/%E7%BB%84%E5%90%88/12004197) 
    void solve(int m,int l,int r){
        if(m > k){
            //cout << "OK! " << test++ << endl;
            if(isPrime(r)){
                ans1++;
            }
            return;
        }
        for(int i=l; i<n; i++){
            if(f[i] == 0){
                r+=a[i];
                f[i] = 1;
                //cout << "test2: " << i << endl;
                solve(m+1,i,r);
                r-=a[i];
                f[i]=0;
            }
        }
    }
    
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        
        cin >> n >> k;
        for(int i=0; i<n; i++){
            cin >> a[i];
            f[i] = 0;
        }
        solve(1,0,0);
        //cout << "Answer: " << ans1 << endl;
        cout << ans1 << endl;
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1036