题解：P1036 [NOIP 2002 普及组] 选数

Chengqijun2012 · 2025-02-26 23:33:31 · 题解

一道很好的组合题，做这题之前建议先去做P1706 全排列问题。

组合就是在全排列的基础上增加了一个新构造的组合在排序后必须与之前的所有已确定的组合不重复的条件。

也正是因为这一点，所有被确定的组合都必须保持升序。如果不是升序，那么在ta之前就一定有一个已确定的组合与之重复。

AC Code：

#include <iostream>
using namespace std;
int n, m;
int a[25];
long long ans;

bool prime(int x){      //判断素数不必多说
    if(x == 1 || x != 2 && x % 2 == 0) return 0;
    for(int i = 3; i * i <= x; i++) if(x % i == 0) return 0;
    return 1;
}

void DFS(int k, int s, int x){      //k表示当前已选的数的个数，s表示这几个数的和，x表示上一个选择的数的下一位
    if(k == m){
        if(prime(s)) ans++;
        return;
    }
    for(int i = x; i < n; i++) DFS(k + 1, s + a[i], i + 1);      //从x开始选，保证是升序
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    DFS(0, 0, 0);
    cout << ans << "\n";
    return 0;
}

本蒟蒻的第一篇题解，望管理员大大通过qwq。