洛谷P1036 [NOIP2002 普及组] 选数【回溯搜索+素数】

P1036 [NOIP2002 普及组] 选数

前言
题目
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 题目分析
- 注意事项
代码
后话
- 王婆卖瓜
题目来源

前言

期中考+逆天大作业，都快没时间写了。不过还是得抽空写一下题目，今天还是做搜索的题单，一题NOIP普及组的题目，还是比较简单的。不过也代表着最基础的回溯和搜索的思想。

题目

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$ ，以及 $1$ 个整数 $k$ （ $k < n$ ）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n = 4$ ， $k = 3$ ， $4$ 个整数分别为 $3, 7, 12, 19$ 时，可得全部的组合与它们的和为：

$3 + 7 + 12 = 22$

$3 + 7 + 19 = 29$

$7 + 12 + 19 = 38$

$3 + 12 + 19 = 34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数： $3 + 7 + 19 = 29$ 。

输入格式

第一行两个空格隔开的整数 $n, k$ （ $\le n \le 20$ ， $k < n$ ）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots,x_n$ （ $\le x_i \le 5\times 10^6$ ）。

输出格式

输出一个整数，表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

题目分析

这题没有什么特殊的技巧就是暴力递归回溯搜索。到达层数后就判断是否为素数然后退出；每层递归进行都进行一次循环，默认所有的在a[start]后的a[i]都会尝试一遍

			sum+=a[i];
			dfs(index+1,i+1);
			sum-=a[i];

dfs前面的尝试和后面的恢复现场确保了每一种可能性都会被遍历，而每次dfs将i+1变成start则保证了不会重复，就是如果从0开始将会修改前面数值可能会出现重复情况。
恢复现场是回溯中基础但是重要的步骤之一。

注意事项

1.记得恢复现场
2.需要将i+1传参start才能保证循环不会重复，就是如果从0开始将会修改前面数值可能会出现重复情况。
3.素数判断使用sqrt(n)比n/2更好一些

代码

好耶！一遍过

#include<iostream>
#include<algorithm>
#include<cmath>
 
using namespace std;

int n,k,total=0,sum;
int a[25]={0},b[25]={0};
bool isPrime(int n) //判断素数 
{
	if(n==2||n==3||n==5||n==7)
		return true;
	if(n==1)
		return false;
	for(int i = 2 ; i <= sqrt(n); i++) {
		if(n%i==0)
			return false;
	}
	return true; 

}
void dfs(int index,int start){
	if(index==k+1){
		if(isPrime(sum)){
			total++;
		}
		return;
	}
	for(int i=start;i<=n;i++){
			sum+=a[i];
			dfs(index+1,i+1);
			sum-=a[i];
	}	
}
int main(){
	cin>>n>>k;
	for(int i = 1 ; i <=n;i++){
		cin>>a[i];
	}
	sum=0; 
	dfs(1,1);
	cout<<total;
	return 0;
}