3355：2024CSP-J初赛绝密押题卷
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
1
提交：891
解决：3
题目描述
答题模版如图
```cpp
选择题:题号和答案
中间有空格
1 A
2 B
3 C
判断题：题号和答案
中间有空格 正确A,错误B
1 A
2 B
3 A
如果右侧编辑器题号没出现，复制下面的模版到右侧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
```
### 选择题（每题2分）
1.以下哪个国家在IOI历史上获得过最多的金牌？
- 中国
- 俄罗斯
- 美国
- 日本
2.以下哪个不是C++中的基本数据类型？
- int
- double
- char
- array
3.假设有以下代码：
```cpp p
#include
#include
using namespace std;
int main() {
string s = "Hello, World!";
string t = "World";
int pos = s.find(t);
s.replace(pos, t.length(), "C++");
for (int i = 0; i < s.length(); i++) {
if (s[i] == ',') {
s.erase(i, 1);
}
}
cout << s << endl;
return 0;
}
```
则程序的输出结果为？
- Hello C++
- Hello, C++
- Hello, C++!
- Hello C++!
4.从100到999这900个整数中，不包含数字8的整数共有（ ）个。
- 632
- 640
- 648
- 800
5.现有1元、2元、5元、10元纸币各若干张，共有（ ）种方法能凑出10元金额。
- 9
- 10
- 11
- 12
6.10个同学围成一圈，依次编号为1到10，从1号开始报数，报到3的人离开，下一个人重新从1号开始报数，报到3的又离开，以此类推，则最后一个出圈的同学编号为（ ）。
- 4
- 5
- 8
- 10
7.有一个序列，采用冒泡排序，第一轮排序之后的结果是：1,6,2,7,9,8 。那么该数组的原始顺序不可能是（）。
- 6,1,2,9,7,8
- 1,6,9,2,7,8
- 6,1,7,9,2,8
- 6,1,2,9,8,7
8.某算法的计算时间表示为递推关系式 $T(n) = 2 * T(n/2) + n^2$($n$为正整数)及$T(1) = 1$，则该算法的时间复杂度为( )。
- O(logn)
- O(n)
- O(nlogn)
- O(n^2)
9.下图
输入 `1374 2677`，输出为( )。
- 3867
- 4051
- 4555
- 7934
10.十六进制数字 AB.C对应的十进制数字是( )
- 168.75
- 170.25
- 171.25
- 171.75
11.对于有$n$个顶点、$m$条边的简单无向图，至少需要添加（）条边才能使其成为一个完全图。
- n(n-1)/2 - m
- n(n+1)/2 - m
- m - n + 1
- m - n - 1
12.将一个平面分割为$x$个区域，使这些区域彼此邻接，则$x$的值最大为 ( )。
- 3
- 4
- 5
- 6
13.4个相同结点的二叉树共有（ ）种。
- 9
- 10
- 12
- 14
14.定义一个指针数组a，这个数组有10个元素，每个元素都是一个指向整型的指针。以下哪种方式是正确的( )
- int *a[10];
- int (*a)[10];
- int &a[10];
- int *a();
15.设图G有$n$个结点和$m$条边，且G中每个结点的度数均为$k$或$k+1$，则度数为$k$的结点数为（ ）。
- k * n-2 * m
- k * (n+1)-2 * m
- (k+1) * n-2 * m
- (k+1) * (n+1)-2 * m
### 阅读程序1（2分/题）
输入的$n$是正整数且不超过$10^5$, $t$ 在`int`范围内。
#### 判断题
16.程序的作用是把输入的数从大到小排序后输出。（）
- A.正确
- B.错误
17.最坏情况下，该程序最为准确的时间复杂度分析结果是$O(n\log n)$。（）
- A.正确
- B.错误
18.最好情况下，该程序最为准确的时间复杂度分析结果是$O(n\log n)$。（）
- A.正确
- B.错误
19.把第10行`int L = 0, R = i;`改为`int L = 0, R = i - 1;`，对于同样的输入，输出结果没有变化。（）
- A.正确
- B.错误
#### 选择题
20.当$n = 100$时，第13行`if (a[mid] >= t)`的最多执行次数是（）。
- A. 479
- B. 480
- C. 573
- D. 579
21.当$n = 100$时，第13行`if (a[mid] >= t)`的最少执行次数是（）。
- A. 479
- B. 480
- C. 573
- D. 579
#### 阅读程序2（前4题2分/题，后2题3分/题）
输入的$n,a[i]$是不超过$31$的正整数，$m$是不超过$10^9$的正整数。
#### 判断题
22.第6~8行的循环结束后，一定有$t < 0$。（）
- A.正确
- B.错误
23.如果输入的$a[i]$中至少有一个$0$，则输出一定不会有$0$。（）
- A.正确
- B.错误
24.如果输入的$m = 1$，且$a[i]$全都是$0$，那么程序将会从小到大输出$1$~$n$的正整数。（）
- A.正确
- B.错误
25.程序输出$n$个数，且必定两两不会重复。（）
- A.正确
- B.错误
#### 选择题
26.如果输入是：
```
4 2
1 1 1 1
```
那么输出结果是（）：
- A. `0 1 2 3`
- B. `1 0 2 3`
- C. `1 2 0 3`
- D. `1 2 3 0`
27.如果输入的$n = 20$，那么把输入的$m$增大（），输出结果一定不会改变。
- A. $20$
- B. $21$
- C. $40$
- D. $41$
### 阅读程序3（前4题2分/题，后2题3分/题）
输入的$n,m$是不超过$50$的正整数，字符矩阵`mp`中保证只出现小写字母。
#### 判断题
28.存在一种合法的输入，使得程序输出`1000000000`。（）
- A.正确
- B.错误
29.如果程序输出`0`，则说明字符矩阵`mp`中一定只有一种字母。（）
- A.正确
- B.错误
#### 选择题
30.在最好情况下和最坏情况下，对该程序最为准确的时间复杂度分析结果是（）。
- A. $O(nm),O((n+m)^2)$
- B. $O((n+m)^2),O(n^2m^2)$
- C. $O(nm),O(n^2m^2)$
- D. $O(n^2m^2),O(n^2m^2)$
31.如果输入是：
```cpp
4 4
abcd
bcdd
cdde
ddef
```
那么程序输出（）：
- A. 2
- B. 3
- C. 4
- D. 5
32.如果输入的字符矩阵的任意两个相邻（上下和左右都算相邻）字符都不相同，那么程序的输出值是（）：
- A. $\left\lceil\frac{n + m}{2}\right\rceil$
- B. $\left\lfloor\frac{n + m}{2}\right\rfloor$
- C. $\left\lceil\frac{n}{2}\right\rceil + \left\lceil\frac{m}{2}\right\rceil$
- D. $\left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{m}{2}\right\rfloor$
33.如果输入的字符矩阵包括除`z`外的全部25种小写字母，那么程序输出的最小值是（）：
- A. 1
- B. 2
- C. 3
- D. 4
### 完善程序1（3分/题）
（数对计数）给出$n$个数对($x_i,y_i$)，问有多少对$1\le i \lt j \le n$，使得$x_i \times x_j = y_i + y_j$。所有的$x_i,y_i$都是$1$ ~ $n$的正整数 。$1 \le n \le 2 \times 10^5$ 。
使用$O(n\sqrt{n})$ 的时间复杂度完成。
输入样例：
```
3
2 3 2
3 3 1
```
输出样例：
```
2
```
34.第一空
- A. ` sort(p + 1, n + 1, cmp)`
- B. `sort(p + 1, p + n, cmp)`
- C. `sort(p[1], p[n + 1], cmp)`
- D. `sort(&p[1], &p[n + 1], cmp)`
35.第二空
- A. `a <= n`
- B. `a <= 2 * n`
- C. `a * a <= n`
- D. `a * a <= 2 * n`
36.第三空
- A. `p[i].x * a - p[i].y`
- B. `p[i].x * a + p[i].y`
- C. `p[i].y * a - p[i].x`
- D. `p[i].y * a + p[i].x`
37.第四空
- A. `a > 0`
- B. `a <= n`
- C. `b <= n`
- D. `true`
38.第五空
- A. `cnt[p[i].x]++`
- B. `cnt[p[i].y]++`
- C. `cnt[p[i].x] += cnt[i]`
- D. `cnt[p[i].y] += cnt[i]`
### 完善填空2（3分/题）
Zeratul今天也要当一次粉刷匠，他需要把$m$面墙刷好。
Zeratul有$n$把神奇的刷子，其中第$i$把刷子可以把第$L[i]$面墙到第$R[i]$面墙的每一面墙都刷上$V[i]$个单位的颜色。
Zeratul有$k$次强化刷子的机会。每次强化刷子时，这个刷子能刷上的颜色将会加上$1$。也就是说，如果把第$x$个刷子强化$y$次，那么这个刷子就可以把覆盖到的每面墙刷上$V[x]+y$个单位的颜色。
强化完成之后，Zeratul将会依次使用每个刷子。如果一面墙被重复刷了多次，那么这面墙被刷上的颜色是每次被刷上的颜色之和。
现在Zeratul想要知道：所有的$m$面墙中，被刷上最少颜色的墙最多有多少个单位的颜色。
输入格式：第一行包括三个整数$n,m,k$，含义见题目描述。
接下来$n$行，每行包括三个整数$L[i],R[i],V[i]$，代表第$i$个刷子的覆盖范围和最开始能刷上多少个单位的颜色。
输出格式：一个整数，代表所有的$m$面墙中，被刷上最少颜色的墙最多有多少个单位的颜色。
$1 \le n,m \le 10^6, 1 \le V[i] \le 1000，1 \le L[i] \le R[i] \le m，0 \le k \le 10^9$
输入样例：
```cpp
3 6 3
1 4 5
2 6 1
3 4 1
```
输出样例：
```
4
```
下面的程序使用二分答案完成。
39.第一空
- A. `now += nowd, cnt -= nowd`
- B. `diff[i] += nowd, cnt -= nowd`
- C. `now += nowd, cnt += nowd`
- D. `diff[i] += nowd, cnt += nowd`
40.第二空
- A. `if (cnt > k) return 0;`
- B. `if (cnt > k) break;`
- C. `if (cnt >= k) return 0;`
- D. `if (cnt >= k) break;`
41.第三空
- A. `Right[L] = R`
- B. `Right[L] = R + 1`
- C. `Right[L] = max(Right[L], R)`
- D. `Right[L] = max(Right[L], R + 1)`
42.第四空
- A. `int i = 0; i < n; i++`
- B. `int i = 1; i <= n; i++`
- C. `int i = 1; i <= m; i++`
- D. `int i = 1; i <= k; i++`
43.第五空
- A. `check(mid) ? l = mid : r = mid`
- B. `check(mid) ? r = mid - 1 : l = mid + 1`
- C. `check(mid) ? l = mid : r = mid - 1`
- D. `check(mid) ? l = mid + 1 : r = mid`