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

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

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | bool isPrime(int n) {
 5 |     for (int i = 2; i < n; ++i) {
 6 |         if (n % i == 0) {
 7 |             return false;
 8 |         }
 9 |     }
10 |     return true;
11 | }
12 |
13 | int main() {
14 |     int n;
15 |     cin >> n;
16 |     for (int i = 2; i + 2 <= n; ++i) {
17 |         if (isPrime(i) && isPrime(i + 2)) {
18 |             cout << i << " " << i + 2 << endl;
19 |         }
20 |     }
21 |     return 0;
22 | }

假设输入的 `n` 是 5 到 1000 之间的正整数，完成下面的判断题和单选题。

 1 | #include <iostream>
 2 | #include <string>
 3 | #include <vector>
 4 | #include <algorithm>
 5 | using namespace std;
 6 | int main() {
 7 |     string a, b;
 8 |     cin >> a >> b;
 9 |     int n = a.size(), m = b.size();
10 |     vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
11 |     for (int i = 0; i <= n; ++i) {
12 |         for (int j = 0; j <= m; ++j) {
13 |             if (i == 0) {
14 |                 dp[i][j] = j;
15 |             }
16 |             else if (j == 0) {
17 |                 dp[i][j] = i;
18 |             }
19 |             else if (a[i - 1] == b[j - 1]) {
20 |                 dp[i][j] = dp[i - 1][j - 1] + 1;
21 |             }
22 |             else {
23 |                 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
24 |             }
25 |         }
26 |     }
27 |     cout << dp[n][m] << endl;
28 |     return 0;
29 | }

假设输入的 `a`、`b` 是长度不超过 1000 的仅包含小写字母的字符串，完成下面的判断题和单选题。

 1 | #include <iostream>
 2 | #include <string>
 3 | #include <algorithm>
 4 | using namespace std;
 5 | int n;
 6 | string s;
 7 | int dfs(string t, int lst) {
 8 |     int ret = 0;
 9 |     for (int i = 0; i <= n; i++)
10 |         if (t[i] != '1')
11 |             ret = 1e9;
12 |     if (ret == 0) return 0;
13 |     for (int i = 0; i <= n; i++)
14 |         if (i != lst && s.substr(n - i, i) == t.substr(0, i)) {
15 |             string cur = t;
16 |             cur[i] ^= 1;
17 |             ret = min(ret, dfs(cur, i) + 1);
18 |         }
19 |     return ret;
20 | }
21 | int main() {
22 |     cin >> s;
23 |     n = s.size();
24 |     string t0(n + 1, '0');
25 |     cout << dfs(t0, -1);
26 |     return 0;
27 | }

假设若无特殊说明，输入的字符串 `s` 是一个长度不超过 18 的非空 01 串，完成下面的判断题和单选题。字符 `0` 和 `a` 的 ASCII 码分别是 48 和 97。

（序列第 $k$ 小）给出一个长度为 $n$ 的数列 $a_1,a_2,\ldots,a_n$ 和一个正整数 $k$，你需要输出第 $k$ 小的数字。输入保证 $1\le k\le n\le10^5$，$1\le a_i\le2\times10^9$，且 $a_i$ 均为整数。下面的程序采用二分答案的方法，通过二分法找到最小的 $x$，使得至少 $k$ 个数字不超过 $x$。试补全程序。

#include <iostream>
using namespace std;

int n, k, a[100'005];

bool check(int x) {
    int c = 0;
    for (int i = 1; i <= n; i++)
        if (/* ① */)
            c++;
    return /* ② */;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = /* ③ */;
    while (l < r) {
        int x = /* ④ */;
        if (check(x))
            r = x;
        else
            /* ⑤ */;
    }
    cout << l << endl;
    return 0;
}

（走迷宫）有一个 $n\times m$ 的网格迷宫。记第 $i$ 行第 $j$ 列的格子为 $(i,j)$。迷宫由空地（用 `.` 表示）和墙壁（用 `#` 表示）组成。起点是 $(1,1)$，终点是 $(n,m)$，保证起点和终点都是空地。小 R 希望使用两种操作从起点到达终点：

- 步行：移动到上下左右相邻的空地。 - 传送：移动到上下左右距离为 2 的空地。中间跨越的格子可以是空地也可以是墙壁。

小 R 最多使用 $k$ 次传送。请计算她到达终点的最少操作次数。如果无法到达，输出 -1。输入保证 $1\le n,m\le100$，$0\le k\le10$。输入的 `grid[i][j]` 只有 `.` 和 `#` 两种字符。下面的程序使用广度优先搜索完成本题。试补全程序。

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

const int MAXN = 105, MAXK = 15;
const int dx[4] = /* ① */;
const int dy[4] = {0, 0, -1, 1};
int n, m, k, dis[MAXN][MAXN][MAXK];
char grid[MAXN][MAXN];

struct Node {
    int x, y, k;
};

int bfs() {
    memset(dis, 0x3f, sizeof(dis));
    queue<Node> q;
    q.push({1, 1, 0});
    dis[1][1][0] = 0;
    while (/* ② */) {
        Node u = q.front();
        q.pop();
        if (u.x == n && u.y == m) {
            return /* ③ */;
        }
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#') {
                if (dis[nx][ny][u.k] > dis[u.x][u.y][u.k] + 1) {
                    dis[nx][ny][u.k] = dis[u.x][u.y][u.k] + 1;
                    q.push({nx, ny, u.k});
                }
            }
        }
        if (/* ④ */) {
            for (int i = 0; i < 4; i++) {
                int nx = u.x + dx[i] * 2;
                int ny = u.y + dy[i] * 2;
                int nk = u.k + 1;
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#') {
                    if (dis[nx][ny][nk] > dis[u.x][u.y][u.k] + 1) {
                        dis[nx][ny][nk] = dis[u.x][u.y][u.k] + 1;
                        /* ⑤ */;
                    }
                }
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}