普及组程序专项02
初赛程序题专项（二）
二、阅读程序
(1)
01 #include <iostream>
02
03 using namespace std;
04
05 int f(int x) {
06 if (x == 1) return 1;
07 int count = 0;
08 for (int i = 1; i * i <= x; ++i) {
09 if (x % i == 0) {
10 count++;
11 if (i * i != x) {
12 count++;
13 }
14 }
15 }
16 return count;
17 }
18
19 int main() {
20 int n;
21 cin >> n;
22 long long total_sum = 0;
23 for (int i = 1; i <= n; ++i) {
24 total_sum += f(i);
25 }
26 cout << total_sum << endl;
27 return 0;
28 }
判断题
- 函数
f(x)用于计算x的所有质因数的个数。 ( ) - 若输入
n为6，则f(6)的返回值为4。 ( ) - 将第 08 行的
i * i <= x修改为i <= x / i，程序的时空复杂度和输出结果均不受影响。 ( )
选择题
-
该程序的功能是 ( )。
- A. 计算从 1 到 n 所有数的质因数总和
- B. 计算从 1 到 n 所有数的约数个数总和
- C. 计算从 1 到 n 所有完数的个数
- D. 计算从 1 到 n 所有质数的个数
-
若输入
n为10，则输出为 ( )。- A. 23
- B. 25
- C. 27
- D. 30
(2)
01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04
05 using namespace std;
06
07 vector<vector<int>> adj;
08 pair<int, int> result; // {distance, node}
09
10 void dfs(int u, int p, int d) {
11 if (d > result.first) {
12 result = {d, u};
13 }
14 for (int v : adj[u]) {
15 if (v != p) {
16 dfs(v, u, d + 1);
17 }
18 }
19 }
20
21 int main() {
22 int n;
23 cin >> n;
24 adj.resize(n + 1);
25 for (int i = 0; i < n - 1; ++i) {
26 int u, v;
27 cin >> u >> v;
28 adj[u].push_back(v);
29 adj[v].push_back(u);
30 }
31
32 result = {-1, -1};
33 dfs(1, 0, 0);
34
35 int endpoint = result.second;
36 result = {-1, -1};
37 dfs(endpoint, 0, 0);
38
39 cout << result.first << endl;
40
41 return 0;
42 }
判断题
- 该程序输入的
n-1行数据，描述的是一个无向图的邻接表。 ( ) - 程序中的
p参数在dfs函数中是为了防止在树的遍历中走回头路（即从子节点返回父节点）。 ( ) - 如果只执行一次
dfs(即删除第 35-37 行)，程序对于所有输入，输出都将减半。 ( )
选择题
-
该程序计算的是 ( )。
- A. 图的最小生成树的边权和
- B. 从节点 1 出发的最长路径长度
- C. 树的直径
- D. 树的重心
-
若输入为：
7 1 2 1 3 2 4 2 5 3 6 3 7则输出为 ( )。
- A. 3
- B. 4
- C. 5
- D. 6
(3)
01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04
05 using namespace std;
06
07 int main() {
08 int n;
09 cin >> n;
10 vector<int> a(n);
11 for (int i = 0; i < n; ++i) {
12 cin >> a[i];
13 }
14
15 if (n == 0) {
16 cout << 0 << endl;
17 return 0;
18 }
19
20 vector<int> dp(n);
21 dp[0] = a[0];
22 int max_ans = dp[0];
23
24 for (int i = 1; i < n; ++i) {
25 dp[i] = max(a[i], dp[i - 1] + a[i]);
26 max_ans = max(max_ans, dp[i]);
27 }
28
29 cout << max_ans << endl;
30 return 0;
31 }
判断题
dp[i]的含义是：在数组a的前i+1个元素（a[0]到a[i]）中，任意子数组的最大和。 ( )- 如果输入数组
a的所有元素均为负数，程序的输出结果一定等于数组a中的最大元素。 ( ) - 该程序的时间复杂度和空间复杂度均为 O(n)。 ( )
选择题
-
该程序解决的问题是 ( )。
- A. 最长上升子序列
- B. 寻找数组中第 k 大的元素
- C. 最大子数组和
- D. 数组元素总和
-
如果将第 25 行的
dp[i] = max(a[i], dp[i - 1] + a[i]);改为dp[i] = dp[i-1] + a[i];，并且输入为5和-1 -2 5 -1 -2，则输出会 ( )。- A. 不变
- B. 从 5 变为 -1
- C. 从 5 变为 2
- D. 发生运行时错误
三、完善程序
(1) 乘船问题
题目描述: 有 n 个人，第 i 个人的重量为 w[i]。每艘船的最大载重量为 limit，且最多只能坐两个人。求最少需要多少艘船才能将所有人带走。
01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04
05 using namespace std;
06
07 int main() {
08 int n, limit;
09 cin >> n >> limit;
10 vector<int> w(n);
11 for (int i = 0; i < n; ++i) cin >> w[i];
12
13 sort(w.begin(), w.end());
14
15 int boats = 0;
16 int i = 0, j = ①;
17
18 while (②) {
19 boats++;
20 if (i < j && ③ <= limit) {
21 ④;
22 }
23 j--;
24 }
25
26 cout << boats << endl;
27 return 0;
28 }
-
①处应填 ( )。
- A.
0 - B.
n - C.
n - 1 - D.
i + 1
- A.
-
②处应填 ( )。
- A.
i < j - B.
i <= j - C.
i != j - D.
boats < n
- A.
-
③处应填 ( )。
- A.
w[i] - B.
w[j] - C.
w[i] + w[j] - D.
limit - w[j]
- A.
-
④处应填 ( )。
- A.
j-- - B.
i++ - C.
boats++ - D.
i = j
- A.
(2) 二维区域和
题目描述: 给定一个 n x m 的矩阵，有 q 次询问，每次询问一个子矩阵的元素之和。
01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int main() {
07 int n, m;
08 cin >> n >> m;
09 vector<vector<int>> a(n + 1, vector<int>(m + 1));
10 vector<vector<int>> s(n + 1, vector<int>(m + 1, 0));
11
12 for (int i = 1; i <= n; ++i) {
13 for (int j = 1; j <= m; ++j) {
14 cin >> a[i][j];
15 s[i][j] = s[i - 1][j] + ① - s[i - 1][j - 1] + a[i][j];
16 }
17 }
18
19 int q;
20 cin >> q;
21 while (q--) {
22 int x1, y1, x2, y2;
23 cin >> x1 >> y1 >> x2 >> y2;
24 int sum = s[x2][y2] - s[x1 - 1][y2] - ② + ③;
25 cout << sum << endl;
26 }
27
28 return 0;
29 }
-
①处应填 ( )。
- A.
s[i][j - 1] - B.
s[i][j + 1] - C.
a[i][j - 1] - D.
s[i - 1][j]
- A.
-
②处应填 ( )。
- A.
s[x2][y1] - B.
s[x1][y2] - C.
s[x2][y1 - 1] - D.
s[x1 - 1][y1]
- A.
-
③处应填 ( )。
- A.
s[x1][y1] - B.
s[x1 - 1][y1 - 1] - C.
a[x1][y1] - D.
s[x2 - 1][y2 - 1]
- A.