2025 洛谷 SCP-J 第一轮模拟题（入门级 C++）

（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | int main() {
 5 |     int l, r;
 6 |     cin >> l >> r;
 7 |     int cnt = 0;
 8 |     long long sum = 0;
 9 |     for (int i = l; i <= r; ++i) {
10 |         if ((i & (i - 1)) != 0) {
11 |             cnt += 1;
12 |             sum += i;
13 |         }
14 |     }
15 |     cout << cnt << " " << sum << endl;
16 |     return 0;
17 | }

假设输入的 `l` 和 `r` 均为不超过 $10^6$ 的正整数，且满足 $l\le r$，完成下面的判断题和单选题。

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | int main() {
 5 |     int n, m;
 6 |     cin >> n >> m;
 7 |     vector<int> a(n);
 8 |     for (int i = 0; i < n; ++i) {
 9 |         cin >> a[i];
10 |     }
11 |     vector<int> dp(m + 1);
12 |     dp[0] = 0;
13 |     for (int i = 1; i <= m; ++i) {
14 |         int now = 0;
15 |         for (int j = 0; j < n; ++j) {
16 |             if (i >= a[j] && dp[i - a[j]] == 0) {
17 |                 now = a[j];
18 |             }
19 |         }
20 |         dp[i] = now;
21 |     }
22 |     cout << dp[m] << endl;
23 |     return 0;
24 | }

假设输入的 `n` 和 `m` 均为不超过 1000 的正整数，输入的 `a[i]` 均为不超过 `m` 的正整数，完成下面的判断题和单选题。

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | vector<int> primes;
 5 | int comp_by[2000005];
 6 | void sieve(int n) {
 7 |     for (int x = 2; x <= n; x++) {
 8 |         if (comp_by[x] == 0)
 9 |             primes.push_back(x);
10 |         for (int i = 0; i < primes.size(); i++) {
11 |
12 |             if (x * primes[i] > n) break;
13 |             comp_by[x * primes[i]] = primes[i];
14 |             if (x % primes[i] == 0) break;
15 |         }
16 |     }
17 | }
18 | int main() {
19 |     freopen("input.txt", "w", stdout);
20 |     freopen("output.txt", "r", stdin);
21 |     int n;
22 |     cin >> n;
23 |     sieve(n);
24 |     for (int i = 1; i <= n; i++)
25 |         cout << comp_by[i] << ' ';
26 |     return 0;
27 | }

假设输入的 `n` 是不超过 $10^6$ 的正整数，完成下面的判断题和选择题。

提示：伯特兰-切比雪夫定理：对任意 $n>1$，存在质数 $p$ 使得 $n<p<2n$。

（全排列检查）给定长度为 `n` 的数组 `a`，判断其是否构成全排列。如果 $1,2,\ldots,n$ 都恰好在数组 `a` 中出现且仅出现一次，那么就称这个数组是一个全排列。

试补全程序。

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

bool is_permutation(vector<int> &a) {
    int n = /* ① */;
    vector<int> count(/* ② */);
    for (int i = 0; i < n; i++) {
        if (/* ③ */)
            count[a[i]]++;
        else
            /* ④ */;
    }
    for (int i = 1; i <= n; i++)
        if (count[/* ⑤ */] > 1)
            return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (is_permutation(a))
        cout << "The sequence is a permutation.";
    else
        cout << "The sequence is not a permutation.";
    return 0;
}

（跳跃）给定一个数组 $a[0],a[1],\ldots,a[n-1]$，每次跳跃从当前位置 `x` 跳至位置 `a[x]`。回答 `q` 次询问，每次给出 `(x,k)`，输出从 `x` 跳跃 `k` 次后的位置编号。

试补全程序。

#include <iostream>
using namespace std;

const int N = 100010, LOG = 20;
int a[N], dp[N][LOG];

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        dp[i][0] = /* ① */;
    }
    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i < n; i++) {
            dp[i][k] = /* ② */;
        }
    }

    while (q--) {
        int x, k;
        cin >> x >> k;
        int u = x;
        for (int j = 0; j < LOG; j++) {
            if (/* ③ */) {
                u = /* ④ */;
            }
        }
        cout << /* ⑤ */ << endl;
    }
    return 0;
}