普及组 CSP-J2025 初赛模拟卷 3

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

第 1 题 如果 a 和 b 都是 char 类型的变量，下列哪个语句不符合 C++ 语法？（ ） {{ select(1) }}

• b = ++a;
• b = a'++;
• b = 'a' + 1;
• b = a++;

第 2 题 泛洪填充算法属于（ ）算法。 {{ select(2) }}

• 贪心
• 二分
• 动态规划
• 搜索

第 3 题 在下列代码的横线处填写（ ），可以使得输出是“58”。

#include
using namespace std;
int main() {
    int x = 8, y = 5;
    x = x ^ y;
    y = x ^ y;
    cout 
using namespace std;
int a[2025], dp[2025];
int main() {
    int n, i, j, ret = -1;
    cin >> n;
    for (i = 1; i > a[i];
        dp[i] = 1;
    }
    for (i = 1; i 
02 using namespace std;
03
04 bool isValid(string s) {
05     stack stk;
06     for (char ch : s) {
07         if (ch == '(' || ch == '[' || ch == '{') {
08             stk.push(ch);
09         } else {
10             if (stk.empty())
11                 return false;
12
13             if (ch == ')' && stk.top() != '(') {
14                 return false;
15             }
16
17             if (ch == ']' && stk.top() != '[') {
18                 return false;
19             }
20
21             if (ch == '}' && stk.top() != '{') {
22                 return false;
23             }
24
25             stk.pop();
26         }
27     }
28     return stk.empty();
29 }
30
31 int main() {
32     string s;
33     cin >> s;
34     if (isValid(s))
35         cout `，则只需要添加 `` 头文件就可以通过编译。
{{ select(18) }}
- 对
- 错

**第 19 题** 若输入（（（（（[））））），则输出是什么？（ ）
{{ select(19) }}
- Valid
- Invalid
- invalid
- valid

**第 20 题** 这个程序的时间复杂度是多少？（ ）
{{ select(20) }}
- $O(n)$
- $O(n²)$
- $O(nlogn)$
- $O(n \sqrt n)$

### （2）
```cpp
01 #include
02 using namespace std;
03
04 int main() {
05     int n;
06     cin >> n;
07     vector a(n);
08     for (int i = 0; i > a[i];
10     vector dp(n + 1, 0);
11     for (int i = 0; i = 2)
13             dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
14         else
15             dp[i] = a[i];
16         if (i >= 1)
17             dp[i] = max(dp[i], dp[i - 1]);
18     }
19     int ans = 0;
20     for (int i = 0; i = 2; 初值为 dp[0] = a[0], dp[1] = a[1]。
{{ select(22) }}
- 对
- 错

**第 23 题** （2 分）在主函数中，访问 dp[n] 不会发生越界错误。
{{ select(23) }}
- 对
- 错

**第 24 题** 当输入的 a 数组为 [2, 1, 1, 2] 时，程序的输出为（ ）
{{ select(24) }}
- 1
- 2
- 3
- 4

**第 25 题** 若将第 13 行改为 dp[i] = max(dp[i-1], dp[i-2] = a[i]);，则当输入的 a 数组为 [10, 1, 0, 25, 3] 时，程序的输出为（ ）
{{ select(25) }}
- 1
- 10
- 35
- 25

**第 26 题** （4 分）当输入的 a 数组为 [0, 2, 3, 4, 5, 6, 0, 8, 9] 时，程序的输出为（ ）
{{ select(26) }}
- 18
- 33
- 34
- 2

### （3）
```cpp
01 #include
02 using namespace std;
03
04 int bfs(vector>& grid) {
05     const int m = grid.size(), n = grid[0].size();
06     const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
07     using pii = pair;
08     queue
 q;
09     vector> vis(m + 1, vector(n + 1));
10     int ans = 0, tot = 0, cnt = 0;
11     for (int i = 0; i = m || cy = n || vis[cx][cy] || grid[cx][cy] != 1)
27                     continue;
28                 if (grid[cx][cy] == 1)
29                     q.push({cx, cy}), vis[cx][cy] = true;
30                 ans++;
31             }
32         }
33     }
34     if (tot == cnt)
35         return max(0, ans - 1);
36     else
37         return -1;
38 }
39
40 int main() {
41     int m, n;
42     cin >> m >> n;
43     vector> a(m, vector(n));
44     for (int i = 0; i > a[i][j];
47     cout 
02 using namespace std;
03
04 int main() {
05     string s;
06     cin >> s;
07     long long cnt = ①, ans = 0;
08     for (int i = 4; ②; i++) {
09         auto cur = ③;
10         if (cur == "heavy")
11             cnt++;
12         else if (cur == "metal")
13             ④;
14     }
15     cout = s.length()

**第 35 题** ③处应填（ ）
{{ select(35) }}
- s.substr(i, 5)
- s.substr(i - 5, 5)
- s.substr(i - 4, 5)
- s.substr(i - 5)

**第 36 题** ④处应填（ ）
{{ select(36) }}
- cur == "heavy"
- cur == "metal"
- cur != "heavy"
- cur != "metal"

**第 37 题** ⑤处应填（ ）
{{ select(37) }}
- ans++
- ans += cnt
- cnt += ans
- cnt++

### （2）
**题目描述**  
输入 l 和 r（1 ≤ l ≤ r ≤ 10¹⁸）。如果整数 x 的首位数字等于末位数字，那么称 x 是合法数字。例如 101，477474, 9 是合法数字，而 47, 253，1020 不是合法数字。输出 [l, r] 中有多少个合法数字？

```cpp
01 #include
02 using namespace std;
03 long long l, r;
04 long long fir(long long g) {
05     while (g >= 10)
06         ①;
07     return g;
08 }
09 long long fin(long long g) {
10     return g % 10;
11 }
12 long long solve(long long n) {
13     if (n > l >> r;
24     cout  fin(n)
- fir(n) >= fin(n)

**第 41 题** ④处应填（ ）
{{ select(41) }}
- base + flag
- base
- flag
- base - flag

**第 42 题** ⑤处应填（ ）
{{ select(42) }}
- solve(r)
- solve(l)
- solve(r) - solve(l - 1)
- solve(r) - solve(l)