洛谷 选数
内容纲要

[NOIP2002 普及组] 选数

题目描述

已知 n 个整数 x1,x2,...,xn,以及 1 个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

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

例如上例,只有一种的和为素数:3+7+19=29。

输入格式

第一行两个空格隔开的整数 n,k(1 <= n <= 20,k<n)。

第二行 n 个整数,分别为 x1,x2,...,xn(1 <= xi <= 5 * 10^6)。

输出格式

输出一个整数,表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

暴力递归:

#include <bits/stdc++.h>
using namespace std;

//创建二维数组是为了方便记录每个数是否被选中
vector<vector<int>> num(20, vector<int>(2, 1));
int n, k;//n个数,选k个数
int he = 0;//记录和
int counts = 0;//记录素数的个数

//判断是否是素数
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
//递归函数
void DFS(int x, int y)
{
    //递归结束条件
    if(x == k)//选到了k个数,开始判断和是否是素数
    {
        if(isPrime(he))
            counts++;
        return;
    }
    //从y~n循环是为了避免重复的出现,例如1234中,选3个,已经选过123与124时
    //准备为13选下一个数,此时若从1~n循环,则程序会先循环到2,又2此时为true,所以程序又会选2,123又再一次出现了,与先前所选出的123相重复
        for (int i = y; i < n; i++)
        {
            if (num[i][1])
            {
                num[i][1] = 0;
                he += num[i][0];
                DFS(x + 1, i + 1);
                he -= num[i][0];//回溯
                num[i][1] = 1;//回溯
            }
        }
    }

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> num[i][0];
    DFS(0, 0);
    cout << counts << endl;

    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇