16 条题解

  • 55
    @ 2023-7-22 18:45:36

    P1014 选数

    题目描述

    已知 n 个整数 ,x1,x2,​⋯​,xn，以及 1 个整数 ​k​（​k​<​n​）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。

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

    思路

    n个里面选K个，数据不大，可以使用​子集枚举​。

    bool func(int x){
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}

    ①定义函数

    int n, m, s, a[25]; ②定义变量

    int i=1;
    cin >> n >> m;
    for(;i<=n;i++)cin>>a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i)!=m)
            continue;
        int sum=0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum+=a[j];
        if(func(sum))s++;
    }cout<<s;
    return 0;

    ③输入+输出+子集枚举 but image 别忘了j是从0开始的 所以：

        int i=1;
    cin >> n >> m;
    for(;i<=n;i++)cin>>a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i)!=m)
            continue;
        int sum=0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum+=a[j+1];
        if(func(sum))s++;
    }cout<<s;
    return 0;

    所以 答案是这样的：

    #include <bits/stdc++.h>
using namespace std;
bool func(int x){
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}int n, m, s, a[25];
int main()
{
    int i=1;
    cin >> n >> m;
    for(;i<=n;i++)cin>>a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i)!=m)//判断是否符合数量
            continue;
        int sum=0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum+=a[j+1];
        if(func(sum))s++;
    }cout<<s;
    return 0;
}

    温馨提示：k就是这里面的m

    制作不易，点赞带走

  • 17
    @ 2023-4-2 10:53:34

    P1014 选数

    题目描述

    已知 n 个整数 ,x1,x2,⋯,xn，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。

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

    思路

    n个里面选K个，数据不大，可以使用子集枚举。

    不过，可先编写一个素数函数

    int check(int f)
{
    for(int i = 2;i < f;i++)
    {
        if(f % i == 0)
        {
            return false;
        }
    }
    return true;
}

    挨个数原理。

    限定元素个数可以使用 __builtin_popcount(i)函数，让他等于题目要求的k。

    if (__builtin_popcount(i) != k)
        {
            continue;
        }

    在加上一些基础的子集枚举代码即可。

    参考代码

    #include <iostream>//hetao3097453
using namespace std;
int a[21],num,sum,n,k;
int check(int f)
{
    for(int i = 2;i < f;i++)
    {
        if(f % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i < (1 << n);i++)
    {
        if (__builtin_popcount(i) != k)
        {
            continue;
        }
        sum = 0;
        for (int j = 0;j < n;j++)
        {
            if (i & (1 << j))
            {
                sum += a[j + 1];
            }
        }
        if(check(sum))
        {
            num++;
        }    
    }
    cout << num;
    return 0;
}

    hetao3097453

    2023年4月2日

  • 7
    @ 2023-4-5 14:09:50

    P1014号题解已送达 滴~已查收

    #include <iostream>
using namespace std;
int n, k, a[21], ans;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i) != k)
            continue;
        int sum = 0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum += a[j + 1];
        bool ok = true;
        for (int j = 2; j * j <= sum; j++)
        {
            if (sum % j == 0)
            {
                ok = false;
                break;
            }
        }
        if (ok)
            ans++;
    }
    cout << ans;
    return 0;
}

    以上来自@ 非原创

    • 7
      @ 2023-2-28 14:38:03

      题目要求n个里面选k个，可以使用自己枚举，用__builtin_popcount函数限定元素个数等于k。

      对每种情况，求出选出的数的总和sum，并判断总和sum是不是质数：可以让j从2到根号sum，判断j是否是sum的因数。如果是因数，把表示sum是不是质数的变量ok赋值为false。ok的初始值是true，如果最终ok是true，就把ans加1。

      最终输出ans即可。

      代码 
      #include <iostream>
using namespace std;
int n, k, a[21], ans;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i) != k)
            continue;
        int sum = 0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum += a[j + 1];
        bool ok = true;
        for (int j = 2; j * j <= sum; j++)
        {
            if (sum % j == 0)
            {
                ok = false;
                break;
            }
        }
        if (ok)
            ans++;
    }
    cout << ans;
    return 0;
}


      • 6
        @ 2023-7-27 16:48:11

        P1014

        -题目回顾-

        已知 n 个整数 ,x1,x2,⋯,xn，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。

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

        -分析-

        用子集枚举呗，还能怎样？代码可以参考L9-5练习7

        -代码-

        #include <bits/stdc++.h>// by AGOMG
using namespace std;
int n, m, a[25], num;
bool cheek(int x)//质数检查
{
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0)
            return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i) != m)
            continue;
        int sum = 0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum += a[j + 1];
        if(cheek(sum))
            num++;
    }
    cout << num;
    return 0;
}
      • 4
        @ 2023-11-12 21:23:15

        要判断素数，所以先编写一个判断素数的函数

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

        然后用子集枚举

        #include <bits/stdc++.h>
using namespace std;
int n, k, a[25], num = 0;


```int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < (1 << n); i++)
    {
        int sum = 0;
        for (int j = 0; j < n; j++)
        {
            if (__builtin_popcount(i) != k)
                continue;
            if (i & (1 << j))
                sum += a[j];
        }
        if (s(sum) && sum != 0)
            num++;
    }
    cout << num;
    return 0;
}

        合起来：

        #include <bits/stdc++.h>
using namespace std;
int n, k, a[25], num = 0;
bool s(int x)
{
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0)
            return false;
    return true;
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < (1 << n); i++)
    {
        int sum = 0;
        for (int j = 0; j < n; j++)
        {
            if (__builtin_popcount(i) != k)
                continue;
            if (i & (1 << j))
                sum += a[j];
        }
        if (s(sum) && sum != 0)
            num++;
    }
    cout << num;
    return 0;
}

        编写不易，点赞拿走．😄 ．
        • 1
          @ 2024-3-22 20:30:24 
          #include <iostream>//hetao819473
using namespace std;
int a[21],num,sum,n,k;
int check(int f)
{
    for(int i = 2;i < f;i++)
    {
        if(f % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i < (1 << n);i++)
    {
        if (__builtin_popcount(i) != k)
        {
            continue;
        }
        sum = 0;
        for (int j = 0;j < n;j++)
        {
            if (i & (1 << j))
            {
                sum += a[j + 1];
            }
        }
        if(check(sum))
        {
            num++;
        }    
    }
    cout << num;
    return 0;
}
          • 1
            @ 2024-1-25 18:34:39

            凭借着我对讲义的熟悉程度，我的手控制我写出了这段AC代码：

            #include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,k,x[25],ans;
bool prime(ll a)
{
    for (int i=2;i<sqrt(a);i++)
        if (a%i==0)
            return 0;
    return 1;
}
int main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>x[i];
    for (int i=1;i<(1<<n);i++)
    {
        ll sum=0;
        if (__builtin_popcount(i)!=k)
            continue;
        for (int j=0;j<n;j++)
            if (i&(1<<j))
                sum+=x[j+1];
        if (prime(sum))
            ans++;
    }
    cout<<ans;
    return 0;
}//麻雀虽小，五脏俱全
            • 1
              @ 2024-1-6 17:34:02 
              #include <bits/stdc++.h>
using namespace std;
bool func(int x){
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}int n, m, s, a[25];
int main()
{
    int i=1;
    cin >> n >> m;
    for(;i<=n;i++)cin>>a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i)!=m)
            continue;
        int sum=0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum+=a[j+1];
        if(func(sum))s++;
    }cout<<s;
    return 0;
}
              • 1
                @ 2023-11-5 20:39:55

                伪代码↓

                #include<bits/stdc++.h>
using namespace std;
定义 n,k,x[21],sum,ans;
int main()
{
    输入 n,k,x[i];
    遍历子串
        如果子串长度不等于k
            continue;
        sum=子串所有元素之和;
        如果sum是质数
            ans加一;
    输出ans;
    return 0;
}//hetao6109326

                AC代码↓

                #include<bits/stdc++.h>
using namespace std;
int n,k,x[21],sum,ans;
bool prime(int a)
{
    for(int i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>x[i];
    for(int i=1;i<(1<<n);i++)
    {
        if(__builtin_popcount(i)!=k)
            continue;
        sum=0;
        for(int j=0;j<n;j++)
            if(i&(1<<j))
                sum+=x[j];
        if(prime(sum))
            ans++;
    }
    cout<<ans;
    return 0;
}//hetao6109326
                • 1
                  @ 2023-10-12 20:05:10 
                  #include <iostream>//hetao3097453
using namespace std;
int a[21],num,sum,n,k;
int check(int f)
{
    for(int i = 2;i < f;i++)
    {
        if(f % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i < (1 << n);i++)
    {
        if (__builtin_popcount(i) != k)
        {
            continue;
        }
        sum = 0;
        for (int j = 0;j < n;j++)
        {
            if (i & (1 << j))
            {
                sum += a[j + 1];
            }
        }
        if(check(sum))
        {
            num++;
        }    
    }
    cout << num;
    return 0;
}
                  • 1
                    @ 2023-8-9 16:38:25 
                    #include <bits/stdc++.h>
using namespace std;
int n,x[25],k,sum,ans;
bool prime(int w)//判断质数
{
    if (w == 1)
    {
        return 0;
    }
    for (int i = 2;i * i < w;i++)
    {
        if (w % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    cin >> n >> k;
    for (int i = 0;i < n;i++)
    {
        cin >> x[i];
    }
    for (int i = 1;i < (1 << n);i++)//子集枚举
    {
        if (__builtin_popcount(i) != k)//过数量这关
        {
            continue;
        }
        sum = 0;//初始化
        for (int j = 0;j < n;j++)
        {
            if (i & (1 << j))
            {
                sum += x[j];//此组合中有此数，总和累加
            }
        }
        if (prime(sum))//判断总和
        {
            ans++;//答案加一
        }
    }
    cout << ans;//输出
    return 0;
}//已AC，请放心使用
//认准本人有限公司（呵呵）MJKLIUJYTGRSGJKJHTGFDVMJGGFDVBVHFDSGJRTGJU&%RFJU……Y%TRFGJKRGFJGHN本日第2篇题解出品了
                    • 1
                      @ 2023-8-8 21:23:28 
                      #include <bits/stdc++.h>
using namespace std;
bool prime(int x){
    if(x<2)return false;
    for(int i=2;i*i<=x;i++)if(x%i==0)return false;
    return true;
}
int main(){
    int n,k,a[25],sum=0,cnt=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<(1<<n);i++){
        if(__builtin_popcount(i)!=k)continue;
        sum=0;
        for(int j=0;j<n;j++)if(i&(1<<j))sum+=a[j+1];
        if(prime(sum))cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

                      这里要注意的是prime函数要优化，不能列举2~x-1了；其次是要用__builtin_popcount函数，最后j别忘+1

                      • -1
                        @ 2024-4-13 16:25:32 
                        #include <bits/stdc++.h>
using namespace std;
bool func(int x){
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}int n, m, s, a[25];
int main()
{
    int i=1;
    cin >> n >> m;
    for(;i<=n;i++)cin>>a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        if (__builtin_popcount(i)!=m)//判断是否符合数量
            continue;
        int sum=0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum+=a[j+1];
        if(func(sum))s++;
    }cout<<s;
    return 0;
}
                        • -7
                          @ 2023-12-11 18:18:21 
                          a
                          • -10
                            @ 2023-10-12 20:04:26

                            #include <iostream> using namespace std; int a[21],num,sum,n,k; int check(int f) { for(int i = 2;i < f;i++) { if(f % i == 0) { return false; } } return true; } int main() { cin >> n >> k; for (int i = 1;i <= n;i++) { cin >> a[i]; } for (int i = 1;i < (1 << n);i++) { if (__builtin_popcount(i) != k) { continue; } sum = 0; for (int j = 0;j < n;j++) { if (i & (1 << j)) { sum += a[j + 1]; } } if(check(sum)) { num++; } } cout << num; return 0; }
                            • 1

                            选数

                            信息

                            ID
                            52
                            时间
                            1000ms
                            内存
                            256MiB
                            难度
                            4
                            标签
                            递交数
                            2404
                            已通过
                            1190
                            上传者
                            1. 关于
                            2. 联系我们
                            3. 隐私
                            4. 服务条款
                            5. 版权申诉
                            6. Language
                            7. 兼容模式
                            8. 主题
                            3. Worker 0, 28ms
                            4. Powered by Hydro v4.9.24 Community, Modified by hetao