社区讨论

求助,过不了第一个样例,其他都行求助求助

P1036[NOIP 2002 普及组] 选数参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo1bq4oa
此快照首次捕获于
2023/10/22 18:26
2 年前
此快照最后确认于
2023/11/02 18:48
2 年前
查看原帖
CPP
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <stack>
#include <vector>
using namespace std;

int n, k;
vector<int> a;

bool isPrime(int number)
{
    for (int i = 2; i < sqrt(number); ++i)
    {
        if (number % i == 0)
        {
            return false;
        }
    }
    return true;
}

int caculateHelper(vector<int> &arr, int index, int count, int oddNumber)
{
    if (count == k)
    {
        //如果奇数的数量位偶数,和一定为偶数,不用判断
        if (oddNumber % 2 == 0)
        {
            return 0;
        }
        int temp = 0;
        for (int i = 0; i < arr.size(); ++i)
        {
            temp += arr[i];
        }
        return isPrime(temp) ? 1 : 0;
    }
    //剪枝
    if (count + n - index < k)
    {
        return 0;
    }
    int ans = 0;

    arr.push_back(a[index]);
    ans += caculateHelper(arr, index + 1, count + 1, oddNumber + (a[index] % 2 == 1 ? 1 : 0));
    arr.pop_back();
    ans += caculateHelper(arr, index + 1, count, oddNumber);

    return ans;
}

int caculate()
{
    vector<int> arr;
    return caculateHelper(arr, 0, 0, 0);
}

int main()
{
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        int temp;
        cin >> temp;
        a.push_back(temp);
    }
    cout << caculate();
}

回复

1 条回复,欢迎继续交流。

正在加载回复...