Day7 阅读程序完整程序组（重制版·15题）

共 3 个完整程序组。判断题正确填 A，错误填 B；请先识别程序功能，再分析输出、修改影响和复杂度。

第一组：筛法与区间质数个数

---

程序一

#include <iostream>
using namespace std;

const int N = 1000;
bool prime[N + 1];
int pre[N + 1];

int main() {
    for (int i = 0; i <= N; ++i) prime[i] = true;
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= N; ++i)
        if (prime[i])
            for (int j = i * i; j <= N; j += i)
                prime[j] = false;

    for (int i = 1; i <= N; ++i)
        pre[i] = pre[i - 1] + prime[i];

    int l, r;
    cin >> l >> r;
    cout << pre[r] - pre[l - 1];
    return 0;
}

第 1 题

输入 10 30 时，程序输出（ {{ select(1) }} ）。

• $5$
• $6$
• $7$
• $8$

---

第 2 题

程序将 $1$ 正确地排除在质数之外（ {{ input(2) }} ）。

---

第 3 题

把内层循环初值 i*i 改为 2*i 不会改变筛法结果，但会产生更多重复标记（ {{ input(3) }} ）。

---

第 4 题

数组 pre 的主要作用是（ {{ select(4) }} ）。

• 保存每个质数的最小因数
• 支持 $O(1)$ 回答区间质数个数
• 保存质数之和
• 降低筛法空间为 $O(1)$

---

第 5 题

完成预处理后，每次给定一组 $l,r$ 并输出答案所需的时间复杂度是（ {{ select(5) }} ）。

• $O(1)$
• $O(\log N)$
• $O(r-l+1)$
• $O(N)$

---

第二组：Pascal 递推与组合数

---

程序二

#include <iostream>
using namespace std;

long long c[35][35];

int main() {
    int n, k;
    cin >> n >> k;
    c[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    cout << c[n][k] << " " << c[n][k] + c[n][k - 1];
    return 0;
}

第 6 题

输入 7 3 时，程序输出（ {{ select(6) }} ）。

• 21 35
• 35 56
• 35 70
• 56 84

---

第 7 题

当 $1\le k\le n$ 时，第二个输出等于 $C_{n+1}^{k}$（ {{ input(7) }} ）。

---

第 8 题

第 $n$ 行所有组合数之和 $\sum_{k=0}^{n}c[n][k]$ 等于（ {{ select(8) }} ）。

• $n$
• $n^2$
• $2^n$
• $n!$

---

第 9 题

程序中二维数组实际使用部分的空间复杂度是（ {{ select(9) }} ）。

• $O(1)$
• $O(n)$
• $O(n\log n)$
• $O(n^2)$

---

第 10 题

若输入中的 $k=0$，原程序仍能安全输出两个有意义的组合数（ {{ input(10) }} ）。

---

第三组：枚举满足和条件的子集

---

程序三

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    int a[20];
    for (int i = 0; i < n; ++i) cin >> a[i];

    int cnt = 0, best = n + 1;
    for (int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0, num = 0;
        for (int i = 0; i < n; ++i)
            if ((mask >> i) & 1) {
                sum += a[i];
                ++num;
            }
        if (sum == target) {
            ++cnt;
            best = min(best, num);
        }
    }
    cout << cnt << " " << best;
    return 0;
}

第 11 题

输入 5 9 2 3 4 5 6 时，程序输出（ {{ select(11) }} ）。

• 2 2
• 3 2
• 3 3
• 4 2

---

第 12 题

外层循环恰好枚举了数组所有可能的子集，包括空集（ {{ input(12) }} ）。

---

第 13 题

表达式 (mask >> i) & 1 用于判断（ {{ select(13) }} ）。

• 第 $i$ 个元素是否被选中
• 子集元素和是否为奇数
• mask 是否为 $2$ 的幂
• 数组是否有重复元素

---

第 14 题

若所有数组元素均为正数且 target=0，程序输出 1 0（ {{ input(14) }} ）。

---

第 15 题

程序关于 $n$ 的时间复杂度是（ {{ select(15) }} ）。

• $O(n)$
• $O(n^2)$
• $O(2^n)$
• $O(n2^n)$

---