help! 测试点3WA
查看原帖
help! 测试点3WA
622751
Gril楼主2022/3/26 19:03

就3没过,其他都过了,测试点3的答案是13,我的答案是12,为什么呢

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> vec;
int res = 0;
int n,k,sum = 0;
bool isPrime(int x)
{
    if(x == 1)
        return false;
    if(x == 2||x == 3)
        return true;
    if(x%6 != 1&&x%6 != 5)
        return false;
    int n = sqrt(x);
    for(int i = 5;i <= n;i+=6)
        if(x%i == 0||x%(i+2) == 0)
            return false;
    return true;
}
void dfs(int cur,int step)
{
    if(cur>vec.size()||vec[cur].second==1)return;
    if(vec[cur].second==1)return;
	if(step==k){if(isPrime(sum))res++;return;}
	for(int i = 1;i < vec.size();i++)
	{
            sum+=vec[cur].first;vec[cur].second=1;
            dfs(cur+i,step+1);
            sum-=vec[cur].first;vec[cur].second=0;
	}
}
int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
    {
        int a1;
        cin >> a1;
        vec.push_back(make_pair(a1,0));
    }
    dfs(0,0);
    cout << res;
    return 0;
}

2022/3/26 19:03
加载中...