洛谷p1036 选数
只a了一个点，找了好久，结果改了之后总是全错。#include<bits/stdc++.h>
using namespace std;
int k,n,ans;
int a,b;
bool pr;
void pro(){
for(int i=2;i<177;i++){
if(i%2==1||i==2){
for(int j=i*i;j<=312500;j+=2){
if((j%i==0||pr)){
pr=true;
}
}
}
else{
for(int j=i*i+1;j<=312500;j+=2){
if(j%i==0||pr){
pr=true;
}
}
}
}
}
// int cc(int ns){
// for(int i=0;i<ans;i++){
// if(ns==b){
// return 0;
// }
// }
// b=ns;
// return 1;
// }
void z(int i,int an,int step){
if(step==k){
//cout<<an+a<<endl;
if(!pr]){
//ans+=cc(an+a);
cout<<an+a<<endl;
ans++;
}
}
else{
for(int l=i;l<=n;l++){
z(l+1,an+a,step++);
}
}
}
int main(){
pro();
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a;
}
int o=0;
for(int i=0;i<n-k;i++){
z(i,0,1);
}
cout<<ans;
return 0;
}
我不知道对不对，你可以试试这个方法：#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int num) {
if (num < 2)return false;
else if (num == 2)return true;
for (int n = 2; n < pow(num, .5) + .5; ++n) {
if (not (num % n)) {
return false;
}
}
return true;
}
// Depth-first search 深度优先搜索
// arr: 数组, k: 相加的整数个数, num: 已相加多少个数？ i: 当前数组位置, sum: 相加结果, res: 为素数个数
unsigned DFS(const vector<int>& arr, int k, int num = 0, int i = 1, int sum = 0, int res = 0) {
if (num == k){
if (isPrime(sum)) return 1;
return 0;
}
for (int j = i; j < arr.size(); ++j) {
res += DFS(arr, k, num + 1, j + 1, sum + arr);
}
return res;
}
int main()
{
int n, k;
vector<int> arr;
arr.push_back(0);
cin >> n >> k;
for (int i = 1, num; i <= n; i++) {
cin >> num;
arr.push_back(num);
}
cout << DFS(arr, k);
return 0;
} 这题我也有点蒙 , 感觉我的代码是可以过的 , 为什么过不去#include <bits/stdc++.h>
using namespace std;
int nums, n, k, ans = 0; // 存数字
bool vis; // 看是否用过
bool check(int n){ // 看是否是素数
int l = sqrt((float)n);
for(int i = 2; i <= l; i++){
if(n % i == 0) return 0;
}
return 1;
}
void dfs(int dep/*看用了几个数*/, int sum/*加起来的数*/){
if(dep == k){ // 用了 k 个数之后
if(check(sum)) ans++; // 符合条件就加上一种可能
return;
}
else{
for(int i = 0; i < n; i++){ // 遍历整个数组
if(!vis){
vis = 1; // vis 代表是否用过 i , 这里如果没用过就用
dfs(dep + 1, sum + nums); // 取的数 +1 , 加起来的数 +nums
vis = 0; // 回溯 , 等他回来就恢复现场让它继续选
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> nums;
}
dfs(0, 0);
cout << ans << endl;
return 0;
} 傻眼貓咪 发表于 2022-7-9 19:36
我不知道对不对，你可以试试这个方法：
{:10_266:}
vis 数组为啥不行 柿子饼同学 发表于 2022-7-9 19:57
vis 数组为啥不行
会不会是全局变量有影响？你的代码递归前后都改变 vis 值，可能在其中搜索树根改变了它的值，让答案越变越多。而我的代码完全没有用全局{:5_105:}，因为虽然全局变量可行，但递归 + 全局的变数太多，我懒的想，所以不用。 本帖最后由 jhq999 于 2022-7-12 11:46 编辑
应该先把奇偶分类
然后奇数选择奇数个，偶数=k-选择奇数的个数
然后再判断和是否为素数（判断时枚举的因子应该都是奇数）
typedef struct GETSUSU
{
int *num,*jisu,*ousu,*numk;
int ncount,jisucount,ousucount,k;
int jisuseek,oususeek,jisuselect,tongjicount;
}GSS,*pGSS;
int ousu(pGSS pgss,int n)
{
if(0==n)
{
for(int i=0;i<pgss->k;i++)
{
printf("%4d",pgss->numk);
}
printf("\n");
pgss->tongjicount+=1;
return 1;
}
for(int i=pgss->oususeek;i<=pgss->ousucount-n;i++)
{
pgss->numk=pgss->ousu;
pgss->oususeek=i+1;
ousu(pgss,n-1);
pgss->oususeek=i;
}
return 0;
}
int jisu(pGSS pgss,int n)
{
if(0==n)
{
pgss->oususeek=0;
ousu(pgss,pgss->k-pgss->jisuselect);
return 1;
}
for(int i=pgss->jisuseek;i<=pgss->jisucount-n;i++)
{
pgss->numk=pgss->jisu;
pgss->jisuseek=i+1;
jisu(pgss,n-1);
pgss->jisuseek=i;
}
return 0;
}
int combination(int a,int b)
{
int sum1=1,sum2=1;
for(int i=a;i>a-b;i--)sum1*=i;
for(int i=1;i<=b;i++)sum2*=i;
return sum1/sum2;
}
int main()
{
GSS gss;
int n=0,k=0,i=0,j=0,t=0;
scanf("%d%d",&n,&k);
gss.k=k;
gss.ncount=n;
gss.num=(int*)calloc(n,sizeof(int));
gss.numk=(int*)calloc(k,sizeof(int));
gss.jisuseek=gss.oususeek=0;
for(i=0,j=n-1;i<j+1;)
{
scanf("%d",&t);
if(t%2)gss.num=t;
else
gss.num=t;
}
gss.jisucount=i,gss.ousucount=n-i;
gss.jisu=gss.num,gss.ousu=gss.num+i;
for(i=0;i<n;i++)printf("%4d",gss.num);
printf("\n");
gss.tongjicount=0;
int sum=0;
for(i=1;i<=gss.jisucount;i+=2)
{
sum+=combination(gss.jisucount,i)*combination(gss.ousucount,k-i);
gss.jisuseek=gss.oususeek=0;
gss.jisuselect=i;
jisu(&gss,i);
}
printf("\n%d",gss.tongjicount);
printf("\n%d",sum);
free(gss.numk);
free(gss.num);
return 0;
}
页:
[1]