社区讨论
求助,过不了第一个样例,其他都行求助求助
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 条回复,欢迎继续交流。
正在加载回复...