CSP-J 2026 第一轮模拟卷 AI-3（按 2025 卷型）

共 15 题，每题 2 分，共 30 分。每题有且仅有一个正确选项。

假设 1≤n≤100000，且所有输入整数绝对值不超过 1000。阅读程序并回答问题。

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 | int main() {
 4 |     int n;
 5 |     cin >> n;
 6 |     vector<int> a(n);
 7 |     for (int i = 0; i < n; ++i) cin >> a[i];
 8 |     int best = 1, cur = 1;
 9 |     int turns = 0;
10 |     for (int i = 1; i < n; ++i) {
11 |         if (a[i] > a[i - 1]) {
12 |             ++cur;
13 |         } else {
14 |             best = max(best, cur);
15 |             cur = 1;
16 |         }
17 |         if (i >= 2) {
18 |             int x = a[i - 1] - a[i - 2];
19 |             int y = a[i] - a[i - 1];
20 |             if (x * y < 0) ++turns;
21 |         }
22 |     }
23 |     best = max(best, cur);
24 |     cout << best << " " << turns << "\n";
25 | }

输入满足 1≤n,m≤30，起点坐标使用从 0 开始的行列编号。相邻格仅指上、下、左、右四个方向。阅读程序并回答问题。

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 | const int N = 35;
 4 | int h[N][N], dista[N][N];
 5 | int main() {
 6 |     int n, m, sx, sy;
 7 |     cin >> n >> m >> sx >> sy;
 8 |     for (int i = 0; i < n; ++i)
 9 |         for (int j = 0; j < m; ++j)
10 |             cin >> h[i][j];
11 |     queue<pair<int, int>> q;
12 |     for (int i = 0; i < n; ++i)
13 |         for (int j = 0; j < m; ++j)
14 |             dista[i][j] = -1;
15 |     dista[sx][sy] = 0;
16 |     q.push({sx, sy});
17 |     int dx[4] = {-1, 1, 0, 0};
18 |     int dy[4] = {0, 0, -1, 1};
19 |     while (!q.empty()) {
20 |         pair<int, int> cur = q.front();
21 |         q.pop();
22 |         int x = cur.first, y = cur.second;
23 |         for (int k = 0; k < 4; ++k) {
24 |             int nx = x + dx[k], ny = y + dy[k];
25 |             if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
26 |             if (dista[nx][ny] != -1) continue;
27 |             if (abs(h[nx][ny] - h[x][y]) > 2) continue;
28 |             dista[nx][ny] = dista[x][y] + 1;
29 |             q.push({nx, ny});
30 |         }
31 |     }
32 |     int cnt = 0, farthest = 0;
33 |     for (int i = 0; i < n; ++i)
34 |         for (int j = 0; j < m; ++j)
35 |             if (dista[i][j] != -1) {
36 |                 ++cnt;
37 |                 farthest = max(farthest, dista[i][j]);
38 |             }
39 |     cout << cnt << " " << farthest << "\n";
40 | }

输入满足 1≤n≤200，1≤k≤输入中不同整数的个数。程序按结点数定义树高。阅读程序并回答问题。

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 | struct Node {
 4 |     int v;
 5 |     Node *left, *right;
 6 |     Node(int x) : v(x), left(nullptr), right(nullptr) {}
 7 | };
 8 | Node* insertNode(Node* p, int x) {
 9 |     if (p == nullptr) return new Node(x);
10 |     if (x < p->v) p->left = insertNode(p->left, x);
11 |     else if (x > p->v) p->right = insertNode(p->right, x);
12 |     return p;
13 | }
14 | int height(Node* p) {
15 |     if (p == nullptr) return 0;
16 |     return max(height(p->left), height(p->right)) + 1;
17 | }
18 | int leaves(Node* p) {
19 |     if (p == nullptr) return 0;
20 |     if (p->left == nullptr && p->right == nullptr) return 1;
21 |     return leaves(p->left) + leaves(p->right);
22 | }
23 | void inorder(Node* p, vector<int>& out) {
24 |     if (p == nullptr) return;
25 |     inorder(p->left, out);
26 |     out.push_back(p->v);
27 |     inorder(p->right, out);
28 | }
29 | int main() {
30 |     int n, k;
31 |     cin >> n >> k;
32 |     Node* root = nullptr;
33 |     for (int i = 0; i < n; ++i) {
34 |         int x;
35 |         cin >> x;
36 |         root = insertNode(root, x);
37 |     }
38 |     vector<int> order;
39 |     inorder(root, order);
40 |     cout << height(root) << " " << leaves(root) << " "
41 |          << order[k - 1] << "\n";
42 | }

给定一个含 n 个整数的环形序列和整数 k（1≤k≤n≤100000）。要从 n 个起点中选一个，求连续 k 个元素的最大和。输入元素绝对值不超过 10^9。请补全程序。

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
long long a[N], pre[N];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[①] = a[i];
    }
    pre[0] = 0;
    for (int i = 1; i <= 2 * n; ++i)
        pre[i] = ②;
    long long best = LLONG_MIN;
    for (int l = 1; l <= n; ++l) {
        int r = ③;
        long long cur = ④;
        best = ⑤;
    }
    cout << best << "\n";
}

给定 n 种正整数面值的硬币，每种硬币可使用任意次，求恰好凑出 target（1≤target≤10000）所需的最少硬币数，并输出一种方案；若无法凑出则输出 -1。请补全程序。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main() {
    int n, target;
    cin >> n >> target;
    vector<int> coin(n);
    for (int i = 0; i < n; ++i) cin >> coin[i];
    vector<int> dp(target + 1, INF);
    vector<int> last(target + 1, -1);
    ①;
    for (int x = 1; x <= target; ++x) {
        for (int j = 0; j < n; ++j) {
            if (②) {
                if (③) {
                    dp[x] = dp[x - coin[j]] + 1;
                    ④;
                }
            }
        }
    }
    if (dp[target] == INF) {
        cout << -1 << "\n";
        return 0;
    }
    cout << dp[target] << "\n";
    int x = target;
    while (x > 0) {
        cout << coin[last[x]]
             << (x == coin[last[x]] ? '\n' : ' ');
        ⑤;
    }
}