[NOIP2002 普及组] 选数 三种代码实现

题目描述

已知 个整数 ，以及 个整数 （）。从 个整数中任选 个整数相加，可分别得到一系列的和。例如当 ，， 个整数分别为 时，可得全部的组合与它们的和为：

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

例如上例，只有一种的和为素数：。

输入格式

第一行两个空格隔开的整数 （，）。

第二行 个整数，分别为 （）。

输出格式

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

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

提示

【题目来源】

NOIP 2002 普及组第二题

代码实现

基于树 (tree) 搜索 (search) 的实现

使用结构体 (struct) 栈实现缓存 (cache)

前置语言知识:

结构体 struct : (更多内容参见https://zh.cppreference.com/w/cpp/language/class)

struct type_name {
    member_var_type1 member_var_name1;
    member_var_type2 member_var_name2;
    etc.
    inline member_func_type1 member_func_name1(...);
    inline member_func_type2 member_func_name1(...);
} object_names;

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

int t = 0;
int x[21];

int conbination(int n, int k);

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (auto i = 1; i <= n; i++)
        scanf("%d", &x[i]);
    conbination(n, k);
    printf("%d", t);
    return 0;
}

struct stack_int_l20 {
    int data[20] = {};
    size_t p = 0;
    inline int push(int n) {
        data[p] = n;
        p++;
        return n;
    }
    inline int pop() {
        p--;
        return data[p];
    }
    inline int top() {return data[p - 1];}
    inline bool empty() {return !(bool)p;}
    inline size_t size() {return p;}
} cache;

void determine() {
    int s = 0;
    for (auto i = 0; i < (signed)cache.size(); i++)
        s += x[cache.data[i]];
    for (auto i = 2; i <= sqrt(s); i++)
        if (s % i == 0) return;
    t += 1;
}

int conbination(int n, int k) {
    if (cache.empty()) {
        cache.push(1);
        return conbination(n, k);
    }
    if ((signed)cache.size() < k) {
        for (auto i = 1; i <= n; i++)
            if (i > cache.top()) {
                cache.push(i);
                break;
            }
    }
    if ((signed)cache.size() == k) {
        determine();
        while (!cache.empty()) {
            if (cache.top() < n - k + (signed)cache.size()) {
                cache.push(cache.pop() + 1);
                return conbination(n, k);
            }
            cache.pop();
        }
        return 0;
    } else return conbination(n, k);
}

使用 C++ 标准模板库 (STL) 向量 (vector) 的栈实现缓存 (cache)

前置语言知识:

向量 vector : (更多内容参见https://zh.cppreference.com/w/cpp/container/vector)

• 声明: vector<type> name {data, ...};
• 方法:
  • 判空: bool vector::empty();
  • 追加: void vector::push_back(type n);
  • 删除: void vector::pop_back();
  • 大小: size_t vector::size();
  • 末尾: type vector::back();

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

int t = 0;
int x[21];

int conbination(int n, int k);

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (auto i = 1; i <= n; i++)
        scanf("%d", &x[i]);
    conbination(n, k);
    printf("%d", t);
    return 0;
}

vector<int> cache{};

void determine() {
    int s = 0;
    for (auto i = 0; i < (signed)cache.size(); i++)
        s += x[cache[i]];
    for (auto i = 2; i <= sqrt(s); i++)
        if (s % i == 0) return;
    t += 1;
}

int conbination(int n, int k) {
    if (cache.empty()) {
        cache.push_back(1);
        return conbination(n, k);
    }
    if ((signed)cache.size() < k) {
        for (auto i = 1; i <= n; i++)
            if (i > cache.back()) {
                cache.push_back(i);
                break;
            }
    }
    if ((signed)cache.size() == k) {
        determine();
        while (!cache.empty()) {
            if (cache.back() < n - k + (signed)cache.size()) {
                cache[cache.size() - 1] += 1;
                return conbination(n, k);
            }
            cache.pop_back();
        }
        return 0;
    } else return conbination(n, k);
}

基于集合 (set) 的暴力枚举算法 (Brute force enumeration algorithm) 实现

前置语言知识:

__builtin_popcount 函数:

int __builtin_popcount(unsigned int number);

<b style="color:red;">! 警告: 该函数不在 C/C++ 标准中，仅在 GCC 中可以使用，该函数底层调用 x86 汇编的 popcnt 指令</b>

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

int a[30];

bool check(int x);

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    int U = 1 << n - 1, ans = 0;
    for (int S = 0; S <= U; S++) {
        if (popcount(S) == k) {
            int sum = 0;
            for (int i = 0; i < n; i++)
                if (S & (1 << i)) sum += a[i];
            if (check(sum)) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

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