2024 CSP-S 满分之路 模拟卷三
单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
- 下面的代码属于哪个算法的核心代码？（ ）
Long Long c[20][20];
c[0][0] = 1;
for (int i = 1; i <= n; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
{{ select(1) }}
- 0-1背包
- 杨辉三角形
- 完全背包
- 部分背包
- NOI Linux2.0中缺省指定编译的C++版本是（ ）。 {{ select(2) }}
C++03C++17C++11C++14
- 下列属于视频文件格式的是（ ）。 {{ select(3) }}
PNGAVIJPEGBMP
- 以下不属于常见的平衡树的是（ ）。 {{ select(4) }}
AVL树- 伸展树
- 三叉树
- 红黑树
- 字符串
"dededfede"和字符串"defed"的最长公共子串是（ ）。 {{ select(5) }}
feddefeddefde
- 下面哪个操作不属于二叉搜索树的常见操作？（ ） {{ select(6) }}
- 查找
- 插入
- 删除
- 交换排序
- 具有m个顶点、n条边的有向图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度是（ ）。 {{ select(7) }}
- (O(m))
- (O(n))
- (O(m + n))
- (O(nm))
- 将关键码集合
(100, 300, 800, 70, 500, 900)逐一保存在一张长度为100的哈希表中。选取哈希函数为Hash(key) = key / 100，则500保存在表中的位置应该是（ ）。 {{ select(8) }}
5678
- 设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子结点数为（ ）。 {{ select(9) }}
5678
- 在C++程序中执行
cout << (928 > 7 > 6)会输出什么结果？（ ） {{ select(10) }}
10truefalse
- 已知240个一模一样的小球里面有一个次品，比正常球轻一些。现在有一架天平（每一端都可以放下240个小球），请问最少称重几次可以找出这个次品小球？（ ） {{ select(11) }}
6457
- 正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形共有（ ）个。 {{ select(12) }}
30353228
- 下面的C++代码运行后，输出的是（ ）。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[100] = {1, 2};
string s = "CSP-S";
cout << s[a[2]] << endl;
return 0;
}
{{ select(13) }}
CSPCSP-S
- 由数字0,1,2,3,4,5组成没有重复数字的六位数，其中个位数字小于十位数字的共有（ ）个。 {{ select(14) }}
210300464600
- 已知元素
(7, 25, 14, 87, 51, 90, 5, 19, 20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：7在51的前面；90在87的后面；20在14的后面；25在5的前面；19在90的后面？（ ） {{ select(15) }}
20, 5, 7, 51, 90, 25, 14, 19, 8751, 5, 19, 20, 14, 8, 87, 90, 2519, 20, 90, 7, 5, 25, 51, 14, 875, 25, 51, 7, 20, 19, 90, 87, 14
阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填，错误填x；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）
(1)
01 #include <iostream>
02 using namespace std;
03
04 const int mod = 1e9 + 7;
05 const int N = 1010, C = 10010;
06 int nn, CC;
07 Long long a[2][C], b[2][C];
08
09 int main() {
10 cin >> nn >> CC;
11 a[1][0] = 1; b[1][0] = 1;
12 for (int n = 2; n <= nn; n++) {
13 for (int c = min(CC, (n - 1) * (n - 2) / 2) + 1; c <= min(CC, n * (n - 1) / 2); c++) {
14 b[(n - 1) & 1][c] = b[(n - 1) & 1][c - 1];
15 }
16 a[n & 1][0] = 1; b[n & 1][0] = 1;
17 for (int c = 1; c <= min(CC, n * (n - 1) / 2); c++) {
18 int en = max(c - n + 1, 0);
19 a[n & 1][c] = b[(n - 1) & 1][c];
20 if (en > 0) a[n & 1][c] -= b[(n - 1) & 1][en - 1];
21 a[n & 1][c] %= mod;
22 if (a[n & 1][c] < 0) a[n & 1][c] += mod;
23 b[n & 1][c] = b[n & 1][c - 1] + a[n & 1][c];
24 b[n & 1][c] %= mod;
25 }
26 }
27 cout << a[nn & 1][CC] << endl;
28 return 0;
29 }
■ 判断题
16. 输入为"10 1"时，输出为"10"。（ ）
{{ select(16) }}
- 正确
- 错误
- 输入为
"4 3"时，输出为"6"。（ ） {{ select(17) }}
- 正确
- 错误
- 本题与计算逆序对有关。（ ） {{ select(18) }}
- 正确
- 错误
- 第16行可以放到第13行前面，程序的运行结果不会改变。（ ） {{ select(19) }}
- 正确
- 错误
■ 选择题 20. 本程序的时间复杂度是（ ）。 {{ select(20) }}
- (O\left(n^{2}\right))
- (O\left(n^{3}\right))
- (O\left(n^{2} log n\right))
- (O\left(n^{4}\right))
- 数组a、b的调用经常有
"&1"的操作，这是为了（ ）。 {{ select(21) }}
- 没什么意义，干扰读题
- 用位运算快速减一
- 快速取二进制尾数
&运算符用于获取存储地址
(2)
01 #include <iostream>
02 #include <iomanip>
03 #include <math.h>
04 using namespace std;
05 pair<long long, long long> calc(int n, long long m) {
06 if (n == 0) return make_pair(0, 0);
07 long long len = 1LL << (n - 1), cnt = 1LL << (2 * n - 2);
08 pair<long long, long long> pos = calc(n - 1, m % cnt);
09 long long z = m / cnt;
10 long long x = pos.first, y = pos.second;
11 if (z == 0) return make_pair(y, x);
12 if (z == 1) return make_pair(x, y + len);
13 if (z == 2) return make_pair(x + len, y + len);
14 if (z == 3) return make_pair(2 * len - y - 1, len - x - 1);
15 }
16 int main() {
17 int n, p, q;
18 cin >> n >> p >> q;
19 cout << setprecision(3)
20 << sqrt(pow(1.0 * calc(n, p).first - calc(n, q).first, 2.0)
21 + pow(1.0 * calc(n, p).second - calc(n, q).second, 2.0))
22 << endl;
23 return 0;
24 }
■ 判断题 22. 本程序编译会报warning。（ ） {{ select(22) }}
- 正确
- 错误
- 若想程序不出错，p、q不能超过(2^{2n})。（ ） {{ select(23) }}
- 正确
- 错误
- 输入数据符合要求时，本程序的时间复杂度是(O(max{N, log M}))。（ ） {{ select(24) }}
- 正确
- 错误
■ 选择题
25. 若输入为"2 0 10"，输出为（ ）。
{{ select(25) }}
4.2433.004.243.606
- 当(|p - q| = 1)时，不论输入的n是多少，只要p、q在符合要求的范围内，则输出为（ ）。 {{ select(26) }}
12-10
- 对同一个n，共有几种输入，可以让输出达到最大？（ ） {{ select(27) }}
2418
(3)
01 #include <iostream>
02 using namespace std;
03
04 const int N = 500010;
05 int n;
06 long long ans, mod = 100000007;
07 long long a[N], b[N], A[N], B[N], sa[N], sb[N];
08
09 int main() {
10 cin >> n;
11 for (int i = 1; i <= n; i++) {
12 cin >> a[i];
13 A[i] = A[i - 1] + a[i];
14 A[i] %= mod;
15 sa[i] = sa[i - 1] + A[i];
16 sa[i] %= mod;
17 }
18 for (int i = 1; i <= n; i++) {
19 cin >> b[i];
20 B[i] = B[i - 1] + b[i];
21 B[i] %= mod;
22 sb[i] = sb[i - 1] + B[i];
23 sb[i] %= mod;
24 }
25 long long t;
26 for (int i = 0; i <= n; i++) {
27 t = A[i];
28 t *= B[i]; t %= mod;
29 t *= n; t %= mod;
30 ans += t;
31 ans %= mod;
32 }
33 for (int i = 0; i < n; i++) {
34 t = A[i] * (sb[n] - sb[i]);
35 t %= mod;
36 ans -= t;
37 if (ans < 0) ans += mod;
38 t = B[i] * (sa[n] - sa[i]);
39 t %= mod;
40 ans -= t;
41 ans %= mod;
42 if (ans < 0) ans += mod;
43 }
44 cout << ans << endl;
45 return 0;
46 }
■ 判断题 28. 因为有第39行，所以若去掉第35行，程序结果不受影响。（ ） {{ select(28) }}
- 正确
- 错误
- 去掉第37行，程序结果不受影响。（ ） {{ select(29) }}
- 正确
- 错误
- 第34行有溢出风险，必须按照第27-28行的方式来写。（ ） {{ select(30) }}
- 正确
- 错误
■ 选择题
31. 若输入3 2 3 4 3 4 5，则输出为（ ）。
{{ select(31) }}
243244253254
- 本题实际在计算（ ）。 {{ select(32) }}
- (\sum_{r=1}^{n} \sum_{l=r}^{n}\left(\sum_{i=1}^{r} a_{i} * \sum_{i=1}^{r} b_{i}\right))
- (\sum_{l=1}^{n} \sum_{r=1}^{n}\left(\sum_{i=1}^{r} a_{i} * b_{i}\right))
- (\sum_{l=1}^{n} \sum_{r=1}^{n}\left(\sum_{i=1}^{r} a_{i} * \sum_{i=1}^{r} b_{l}\right))
- (\sum_{l=1}^{n} \sum_{r=1}^{n}\left(\sum_{i=1}^{r} a_{i} * \sum_{i=1}^{r} b_{i}\right))
- （4分）本代码将原问题的时间复杂度从(O(N^{3}))优化到(O(N))。如果希望继续优化，应该（ ）。 {{ select(33) }}
- 没有太大优化空间
- 减少取模运算
- 将
long long改为int，以提高处理速度 - 做更多的预处理
完善程序（单选题，每小题3分，共计30分）
(1) **有一个字符串S，最开始其中只有一个字符a，之后你要对这个字符串进行若干次操作，每次将其中每一个字符c替换成某个字符串s（例如对于字符串ball，将其中的l替换为na后将得到banana）。现在给定(l, r)，你需要输出变换完毕后，S的第l个字符到第r个字符对应的子串是什么。
算法是逆序建树，从最后一次操作开始，将字符替换的规则视为树的连线，叶子结点为最后被替换的字母。建树完毕后，再根据(l, r)的数值，在树上DFS遍历并输出。
01 #include <bits/stdc++.h>
02 using namespace std;
03 #define ll long long
04 const int NN = 2e5 + 10;
05 char c[NN]; string s[NN];
06 int first[26]; ll tot[NN], tf[26];
07 vector<ll> cnt[NN]; vector<int> nxt[NN];
08
09 int num(char c) {
10 return ①;
11 }
12
13 ll search(int cur, ll l, ll r, ll acc) {
14 for (int i = 0; i < cnt[cur].size(); i++) {
15 if (acc >= r) break;
16 if (acc + cnt[cur][i] >= l) {
17 if (!nxt[cur][i]) {
18 cout << s[cur][i];
19 acc++;
20 } else {
21 ②;
22 }
23 } else {
24 acc += cnt[cur][i];
25 }
26 }
27 return acc;
28 }
29
30 int main() {
31 ios_base::sync_with_stdio(false);
32 cin.tie(NULL);
33 ll l, r; int n;
34 cin >> l >> r >> n;
35 for (int i = 1; i <= n; i++) {
36 cin >> c[i] >> s[i];
37 }
38 for (int i = n; i > 0; i--) {
39 for (int j = 0; j < s[i].size(); j++) {
40 ③;
41 }
42 first[num(c[i])] = i;
43 }
44 for (int i = 0; i < 26; i++) tf[i] = 1;
45 for (int i = n; i > 0; i--) {
46 tot[i] = 0;
47 for (int j = 0; j < s[i].size(); j++) {
48 ④;
49 cnt[i].push_back(tf[k]);
50 tot[i] += tf[k];
51 if (tot[i] > r) break;
52 }
53 tf[num(c[i])] = tot[i];
54 }
55 ⑤;
56 }
- ①处应填（ ）。 {{ select(34) }}
c - ac - 'a'c - 'a' + 1'c' - 'a'
- ②处应填（ ）。 {{ select(35) }}
acc = search(acc, nxt[cur][i], l, r, acc)acc = search(nxt[cur][i], -cnt[cur][i], r, acc)acc = search(nxt[cur][i], l, r, acc)acc = search(nxt[cur][i], l, r, acc + cnt[cur][i])
- ③处应填（ ）。 {{ select(36) }}
nxt[i].push_back(first[num(s[i][j])])nxt[i].push_back(num(s[i][j]))cnt[i].push_back(num(s[i][j]))cnt[i].push_back(first[num(s[i][j])])
- ④处应填（ ）。 {{ select(37) }}
int k = 0int k = num(c[i])int k = num(s[i][j])int k = first[num(s[i][j])]
- ⑤处应填（ ）。 {{ select(38) }}
search(first[1], l, r, nxt[0])search(first[1], l, r, 0)search(1, l, r, 1)search(1, l, r, 0)
(2) 给定函数(h(x))，(x \in Z)，(1 ≤ x ≤ n)，定义seepairs(h)为这样的无序数对((i, j))的个数：(i < j)，且连接((i, h(i)))与((j, h(j)))的线段不低于((k, h(k)))，其中(i < k < j)。对h函数进行Q次调整，每次把(h(x))调整为(h(x) + y)，(y > 0)。求每次调整之后的seepairs(h)。
数据规模：n，(Q ≤ 2000)，初始(h(x))和调整后的(h(x))都不超过(10^9)。
本代码使用set存储，初始化每个(h(i))能“看到”的点的数量see(i)，则对see(i)求和即为seepairs()，每次调整(h(x))之后，因为(h(x))只增不减，所以see(x)只增不减。对于(i > x)，see(i)不变，对于(i < x)，see(i)只减不增，因此把see(1)至see(x)调整之后再求和，即为调整后的seepairs(h)。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int N = 2010;
05 int n, q, x, y; long long h[N];
06 set<int> see[N];
07 typedef set<int>::iterator iter;
08
09 bool small(int i, int k, int j) {
10 return ①;
11 }
12
13 int main() {
14 cin >> n;
15 for (int i = 1; i <= n; i++) {
16 cin >> h[i];
17 }
18 for (int i = 1; i < n; i++) {
19 see[i].insert(i + 1);
20 for (int j = i + 2; j <= n; j++) {
21 ②;
22 see[i].insert(j);
23 }
24 }
25 cin >> q;
26 for (int qq = 1; qq <= q; qq++) {
27 cin >> x >> y;
28 h[x] += y;
29 for (int i = 1; i < x; i++) {
30 iter it = ③;
31 if (it == see[i].end()) {
32 --it;
33 if (small(i, *it, x)) see[i].insert(x);
34 } else {
35 bool ins = false;
36 if (*it == x) {
37 ins = true;
38 it++;
39 } else {
40 --it;
41 if (small(i, *it, x)) {
42 see[i].insert(x);
43 ins = true;
44 it++;
45 }
46 }
47 ④;
48 if (ins) {
49 while (⑤) {
50 it = see[i].erase(it);
51 }
52 }
53 }
54 }
55 if (x < n) {
56 see[x].clear();
57 see[x].insert(x + 1);
58 for (int j = x + 2; j <= n; j++) {
59 if (small(x, *see[x].rbegin(), j)) see[x].insert(j);
60 }
61 }
62 int ans = 0;
63 for (int i = 1; i < n; i++) {
64 ans += see[i].size();
65 }
66 cout << ans << endl;
67 }
68 return 0;
69 }
- ①处应填（ ）。 {{ select(39) }}
(h[k] - h[i]) * (j - k) < (h[j] - h[k]) * (k - i)(h[k] - h[i]) * (j - k) < (h[j] - h[k]) * (i - k)(h[k] - h[i]) * (j - i) < (h[j] - h[i]) * (k - i)(h[k] - h[i]) * (j - i) <= (h[j] - h[i]) * (k - i)
- ②处应填（ ）。 {{ select(40) }}
if (small(i, *see[i].rbegin(), j))if (small(i, *see[i].rbegin(), j - 1))if (small(i, *see[i].end(), j))if (small(i, *see[i].end() - 1, j))
- ③处应填（ ）。 {{ select(41) }}
see[i].upper_bound(x)see[i].lower_bound(x)see[i].lower_bound(x) + 1see[i].upper_bound(x + 1)
- ④处应填（ ）。 {{ select(42) }}
it--it++// 无内容}
- ⑤处应填（ ）。 {{ select(43) }}
it != see[i].end() && small(i, x, *it)it != see[i].end() - 1 && !small(i, x, *it)it != see[i].end() && !small(i, x, *it)it != see[i].end() && !small(i, x, it)