题意及思路

  • 题意:求n个给定的数中任选k个数求和,问有多少方案的和最终为素数。输出方案数即可。
  • 思路:😁k中第一个数不妨设为n中第一个数(index = 0)。😅解释一个solve(int index)函数:如果当前选中的数已经等于需求数k,如果和为素数,ans++,函数结束。从当前index位开始往后找数,🤨为避免重复计算,我们开了一个h [N]数组。😯如果当前下标 i 上的数未被选过,就选中这个数,🙂当然临时和存放在nans中,🙃然后递归处理 i + 1位上的数。😥回溯时,将当前数从nans中去除,并且已经选中数 t--,同时还要讲当前位置上的数置为false(意味着可选)。😔我自己都觉着一头雾水,总之呢,自己要对递归、bfs、dfs这些知识补习一番才行。加油!😊代码更加清晰,试着理解一下代码。
  • 补充点:上述思路中有累赘之处,🤣就是那个h [N]数组,其实我们没有必要开,我们每次将当前数加到nans中,🙄递归调用处理的是下一个下标所对应的数据。详情见代码2。😉但是思路的总体没有错误。对了,其实我们根本不需要排序,因为我们不在意数的相对大小,我们只在意其和。😜

代码1

#include<bits/stdc++.h>

using namespace std;

const int N = 25;
int ans = 0,n,k,t = 0,nans = 0;
int q[N] = {0};
bool h[N];

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

void solve(int index){
	if(t==k){
		if(isPrime(nans)) ans++;
//		cout << " result : " << nans << endl;
		return;
	}
	for(int i=index;i<n;i++){ // 3 7 12 19 *
		if(h[i]==false){
			h[i] = true;
			nans += q[i];
			t++;
			solve(i+1);
			h[i] = false;
			nans -= q[i];
			t--;
		}
	}	
}

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h,false,sizeof(h));
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> q[i];
    sort(q,q+n);
	solve(0);
	cout << ans << endl;
	return 0;
}

代码2

#include<bits/stdc++.h>

using namespace std;

const int N = 25;
int ans = 0,n,k,t = 0,nans = 0;
int q[N] = {0};

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

void solve(int index){
	if(t==k){
		if(isPrime(nans)) ans++;
//		cout << " result : " << nans << endl;
		return;
	}
	for(int i=index;i<n;i++){ // 3 7 12 19 *
		nans += q[i];
		t++;
		solve(i+1);
		nans -= q[i];
		t--;
	}	
}

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> q[i];
    sort(q,q+n);
	solve(0);
	cout << ans << endl;
	return 0;
}