[已解决]洛谷p1036 选数

zzzyf

只a了一个点，找了好久，结果改了之后总是全错。

#include<bits/stdc++.h>
using namespace std;
int k,n,ans;
int a[20],b[100];
bool pr[312501];
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[j])){
                    pr[j]=true;
                }
            }
        }
        else{
            for(int j=i*i+1;j<=312500;j+=2){
                if(j%i==0||pr[j]){
                    pr[j]=true;
                }
            }
        }
        
    }
}
// int cc(int ns){
//     for(int i=0;i<ans;i++){
//         if(ns==b[i]){
//             return 0;
//         }
//     }
//     b[ans]=ns;
//     return 1;
// }
void z(int i,int an,int step){
    if(step==k){
        //cout<<an+a[i]<<endl;
        if(!pr[an+a[i]]){
            //ans+=cc(an+a[i]);
            cout<<an+a[i]<<endl;
            ans++;
        }
    }
    else{
        for(int l=i;l<=n;l++){
            z(l+1,an+a[i],step++);
        }
    }
}
int main(){
    pro();
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int o=0;
    for(int i=0;i<n-k;i++){
        z(i,0,1);
    }
    cout<<ans;

    return 0;
} 

最佳答案

月排行榜 / 总排行榜

jhq999

2022-7-11 09:57:32

应该先把奇偶分类
然后奇数选择奇数个，偶数=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[i]);
        }
        printf("\n");
        pgss->tongjicount+=1;
        return 1;
    }
    for(int i=pgss->oususeek;i<=pgss->ousucount-n;i++)
    {
        pgss->numk[pgss->jisuselect+n-1]=pgss->ousu[i];
        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[n-1]=pgss->jisu[i];
        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[i++]=t;
        else
            gss.num[j--]=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[i]);
    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;
}

跳转到最佳答案楼层

傻眼貓咪

我不知道对不对，你可以试试这个方法：

#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[j]);
    }
    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[21], n, k, ans = 0; // 存数字
bool vis[21]; // 看是否用过

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[i]){
                vis[i] = 1; // vis[i] 代表是否用过 i , 这里如果没用过就用
                dfs(dep + 1, sum + nums[i]); // 取的数 +1 , 加起来的数 +nums[i]
                vis[i] = 0; // 回溯 , 等他回来就恢复现场让它继续选
            }     
        }
    }
}

int main(){
    ios::sync_with_stdio(0);

    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}

柿子饼同学

傻眼貓咪 发表于 2022-7-9 19:36
我不知道对不对，你可以试试这个方法：

vis 数组为啥不行

傻眼貓咪

柿子饼同学 发表于 2022-7-9 19:57
vis 数组为啥不行

会不会是全局变量有影响？你的代码递归前后都改变 vis 值，可能在其中搜索树根改变了它的值，让答案越变越多。而我的代码完全没有用全局，因为虽然全局变量可行，但递归 + 全局的变数太多，我懒的想，所以不用。

jhq999

应该先把奇偶分类
然后奇数选择奇数个，偶数=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[i]);
        }
        printf("\n");
        pgss->tongjicount+=1;
        return 1;
    }
    for(int i=pgss->oususeek;i<=pgss->ousucount-n;i++)
    {
        pgss->numk[pgss->jisuselect+n-1]=pgss->ousu[i];
        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[n-1]=pgss->jisu[i];
        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[i++]=t;
        else
            gss.num[j--]=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[i]);
    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;
}