社区讨论
c++卑微请求大佬好爸爸好妈妈看看我的dfs哪里出问题了,能编译但样例不过
P1036[NOIP 2002 普及组] 选数参与者 2已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lo31lj7d
- 此快照首次捕获于
- 2023/10/23 23:18 2 年前
- 此快照最后确认于
- 2023/10/23 23:18 2 年前
C
#include<bits/stdc++.h>
using namespace std;
vector<int>book;
int t,z,x;
bool su(int a){
int i;
for( i=2;i<a;i++){
if(a%i==0)
return 0;
}
if(i==a)
return 1;
}//判断和是否为素数,是素数则返回1
void dfs(int cur,int k,int a[]){//cur为当前相加数字个数,k为要求k个数字相加,a[]为输入数字组成的数组
if(cur==k){//达到k个数相加,调用素数判断函数
if(su(z)){
t++;//是素数则t计数器+1
}
z-=x;//减去上次加入的数字重置z
return;//退出递归,返回上一步
}
for(int i=0;i<sizeof(a);i++){//从a数组第一个位置开始遍历到最后一个
if(book[a[i]==0]){//若a[i]未被访问过
z+=a[i];//计入和
x=a[i];//记录此时加入的数字
book[a[i]]=1;//标记a[i]已访问
dfs(cur+1,k,a);//进入dfs递归
book[a[i]]=0;//标记a[i]未访问
}
}
}
int main(){
int n,k;
cin>>n>>k;//输入n个数字,要求选k个数字相加
t=0;//初始计数器为0
z=0;//初始和为0
book.assign(10086,0);//设置标记数字,元素皆为0
int a[n];//创建n个元素的a数组
for(int i=0;i<n;i++){
cin>>a[i];
}//输入n个数字
dfs(0,k,a);//调用dfs函数
cout<<t;//输出计数器的累计个数
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...