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

long_long_inf · 2025-02-27 12:12:28 · 题解

思路

很明显，n 的范围非常小，于是我们就可以枚举出所有可能，然后一一判断。

枚举

对于枚举的话，用深搜比较好，全排列函数虽然码量小，但是会产生很多重复的判断，所以建议使用深搜。

判断

判断就比较简单了，先求和，然后开根判断是不是质数。

代码

#include <iostream>
using namespace std;
int n, k, a[26], w[26];
long long cnt = 0;
bool cIP()
{
    long long x = 0;
    for (int i = 1; i <= n; i++)
    {
        x += a[i] * w[i];
    }
    if (x < 2) return false;
    for (long long i = 2; i * i <= x; i++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
int sum()
{
    int sum = 0;
    for (int i = 1; i <= n; i++) sum += a[i];
    return sum;
}
void dfs(int x)
{
    if (x > n)
    {
        if (cIP() && sum() == k) cnt++;
        return;
    }
    a[x] = 0;
    dfs(x + 1);
    a[x] = 1;
    dfs(x + 1);
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];
    dfs(1);
    cout << cnt << endl;
    return 0;
}