洛谷题解P1036 选数

红太狼 2022-02-26 06:26 254阅读 0赞

# 一、题目 #

[https://www.luogu.org/problemnew/show/P1036][https_www.luogu.org_problemnew_show_P1036]

# 二、代码 #

#include <iostream>
    using namespace std;
    
    bool isprime(int a)
    {
        for(int i=2;i*i<=a;i++)
        {
            if(a%i==0)
            {
                return false;
            }
        }
    
        return true;
    }
    
    int n,k;
    int a[25];
    bool visited[25];
    long long ans=0;
    
    // select，已选多少个数
    // sum为已选的数之和
    // start，从哪个数开始选的，最初肯定是从第0个数开始选，枚举完后要从第1个数开始选 ……
    
    void dfs(int select,int sum,int start)
    {
        if(select==k)
        {
            if(isprime(sum))
            {
                ans++;
            }
    
            return;
        }
    
        for(int i=start;i<n;i++)
        {
            if(visited[i])
            {
                continue;
            }
    
            visited[i]=true;
    
            dfs(select+1,sum+a[i],i+1);
    
            visited[i]=false;
        }
    }
    
    int main()
    {
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
    
        dfs(0,0,0);
    
        cout<<ans;
    
        return 0;
    }

> 少儿编程、信息学竞赛咨询请加微信307591841或QQ群581357582  
> ![信息学竞赛公众号.jpg][.jpg]

[https_www.luogu.org_problemnew_show_P1036]: https://www.luogu.org/problemnew/show/P1036
[.jpg]: /images/20220226/4007d949859d4eac93ade63e9f872d9d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，254人围观）

还没有评论，来说两句吧...

相关阅读

相关 Luogu-P1036 选数

P1036 选数 -------------------- [原题题意][Link 1] -------------------- 题解因为需要从n个数

川长思鸟来/ 2022年11月03日 00:43/ 0 赞/ 171 阅读

相关洛谷P1781 宇宙总统题解

[\[P1781 宇宙总统\]][P1781]题目描述地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 n 个非凡拔尖的人竞选总统，现在票数已经统计完毕

绝地灬酷狼/ 2022年10月29日 10:26/ 0 赞/ 212 阅读

相关洛谷P1036 选数

题目描述已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整

我会带着你远行/ 2022年06月01日 11:24/ 0 赞/ 247 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 349 阅读

相关洛谷题解P1028 数的计算

一、题目 [https://www.luogu.org/problemnew/show/P1028][https_www.luogu.org_problemnew_sho

傷城~/ 2022年02月28日 19:26/ 0 赞/ 230 阅读

相关洛谷题解P1036 选数

一、题目 [https://www.luogu.org/problemnew/show/P1036][https_www.luogu.org_problemnew_sho

红太狼/ 2022年02月26日 06:26/ 0 赞/ 255 阅读

相关【题解】洛谷P1657 选书

简单搜索； PS：最后一个点卡n==0 的情况，特判一下哦~ include<iostream> include<cstdio> include<c

曾经终败给现在/ 2021年12月15日 12:29/ 0 赞/ 377 阅读

相关洛谷P2258 子矩阵——题解

[题目传送][Link 1] ![1605498-20190627092835228-403173840.png][] ![1605498-2019062709285266

Bertha 。/ 2021年11月26日 07:26/ 0 赞/ 347 阅读

相关题解洛谷P2568 GCD

\\(update\\ \\ \\ 2018/11/18\\)修改了\\(Letex\\)，其他没有变中间我\\(AFO\\)了,成功从红名掉到了蓝名 \\(update

约定不等于承诺〃/ 2021年10月26日 21:20/ 0 赞/ 409 阅读

相关洛谷P3870开关题解

我们先看题面，一看是一个区间操作，再看一下数据范围，就可以很轻松地想到是用一个数据结构来加快区间查询和修改的速度，所以我们很自然的就想到了线段树。但是这个题还跟普通的线段树

「爱情、让人受尽委屈。」/ 2021年10月01日 03:52/ 0 赞/ 384 阅读