普及组程序专项

二、阅读程序

(1)

01 #include <iostream>
02 #include <vector>
03 #include <numeric>
04
05 using namespace std;
06
07 int main() {
08     int n;
09     cin >> n;
10     vector<int> p(n + 1, 0);
11     for (int i = 2; i <= n; ++i) {
12         if (p[i] == 0) {
13             for (int j = i; j <= n; j += i) {
14                 if (p[j] == 0) {
15                     p[j] = i;
16                 }
17             }
18         }
19     }
20
21     long long sum = 0;
22     for (int i = 2; i <= n; ++i) {
23         sum += p[i];
24     }
25     cout << sum << endl;
26
27     return 0;
28 }

判断题

1. 程序结束后，p[i] 的值是 i 的最小质因数。 ( )
2. 若输入 n 为 10，则程序运行到第 19 行时，p 数组的内容为 {0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2}。 ( )
3. 该程序的时间复杂度约为 O(n log n)。 ( )

选择题

4. 若输入 n 为 12，则输出为 ( )。

   • A. 30
   • B. 32
   • C. 35
   • D. 37

5. 如果将第 14 行的 if (p[j] == 0) 判断移除，对于输入 n=10，程序的输出将会 ( )。

   • A. 不变
   • B. 变大
   • C. 变小
   • D. 程序会出错

(2)

01 #include <iostream>
02 #include <vector>
03 #include <string>
04
05 using namespace std;
06
07 int n, m;
08 vector<string> grid;
09 vector<vector<bool>> visited;
10
11 int dx[] = {0, 0, 1, -1};
12 int dy[] = {1, -1, 0, 0};
13
14 int dfs(int x, int y) {
15     if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || grid[x][y] == '0') {
16         return 0;
17     }
18     visited[x][y] = true;
19     int count = 1;
20     for (int i = 0; i < 4; ++i) {
21         count += dfs(x + dx[i], y + dy[i]);
22     }
23     return count;
24 }
25
26 int main() {
27     cin >> n >> m;
28     grid.resize(n);
29     visited.assign(n, vector<bool>(m, false));
30     for (int i = 0; i < n; ++i) {
31         cin >> grid[i];
32     }
33
34     int max_area = 0;
35     for (int i = 0; i < n; ++i) {
36         for (int j = 0; j < m; ++j) {
37             if (grid[i][j] == '1' && !visited[i][j]) {
38                 max_area = max(max_area, dfs(i, j));
39             }
40         }
41     }
42     cout << max_area << endl;
43     return 0;
44 }

判断题

6. 该程序的核心算法是广度优先搜索（BFS）。 ( )
7. 如果 grid 中所有的 '1' 形成一个连通块，程序的时间复杂度与 n*m 成正比。 ( )
8. 将第 11、12 行的 dx, dy 数组定义为 {0, 0, 1, -1, 1, 1, -1, -1} 和 {1, -1, 0, 0, 1, -1, 1, -1}，并将第 20 行的 i < 4 改为 i < 8，程序的功能将变为寻找八个方向连通的 '1' 区域。 ( )

选择题

9. 该程序旨在解决的问题是 ( )。

   • A. 寻找从左上角到右下角的最短路径
   • B. 计算 grid 中 '1' 的总数量
   • C. 寻找 grid 中由 '1' 构成的最大连通区域的面积
   • D. 计算 grid 中由 '1' 构成的连通区域的数量

10. 若输入为：

    4 5
    11000
    11000
    00100
    00011
    

    则输出为 ( )。

    • A. 1
    • B. 2
    • C. 4
    • D. 5

(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<pair<int, int>> activities(n);
11     for (int i = 0; i < n; ++i) {
12         cin >> activities[i].second >> activities[i].first;
13     }
14
15     sort(activities.begin(), activities.end());
16
17     int count = 0;
18     int current_end_time = 0;
19
20     if (n > 0) {
21         count = 1;
22         current_end_time = activities[0].first;
23     }
24
25     for (int i = 1; i < n; ++i) {
26         if (activities[i].second >= current_end_time) {
27             count++;
28             current_end_time = activities[i].first;
29         }
30     }
31
32     cout << count << endl;
33
34     return 0;
35 }

判断题

11. 程序的输入首先读入每个活动的结束时间，然后读入开始时间。 ( )
12. 程序实现的算法是动态规划。 ( )
13. 如果将第 15 行的排序去掉，程序的输出结果对于某些输入可能不正确。 ( )

选择题

14. 该程序解决的是经典的 ( ) 问题。

    • A. 任务调度
    • B. 背包问题
    • C. 最长公共子序列
    • D. 活动选择

15. 若输入为：

    5
    3 5
    1 4
    5 7
    2 6
    8 9
    

    则输出为 ( )。

    • A. 1
    • B. 2
    • C. 3
    • D. 4

三、完善程序

(1) 最长上升子序列

题目描述: 给定一个长度为 n 的序列 A，请求出 A 的最长上升子序列（LIS）的长度。上升子序列是指从原序列中，按顺序取出一些元素，这些元素是单调递增的。

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, 1);
21     int max_len = 1;
22
23     for (int i = 1; i < n; ++i) {
24         for (int j = 0; ①; ++j) {
25             if (②) {
26                 dp[i] = max(dp[i], ③);
27             }
28         }
29         max_len = ④(max_len, dp[i]);
30     }
31
32     cout << max_len << endl;
33     return 0;
34 }

16. ①处应填 ( )。

    • A. j <= i
    • B. j < n
    • C. j < i
    • D. j > 0

17. ②处应填 ( )。

    • A. a[i] > a[j]
    • B. a[i] >= a[j]
    • C. dp[i] > dp[j]
    • D. a[i] < a[j]

18. ③处应填 ( )。

    • A. dp[j]
    • B. dp[j] + 1
    • C. dp[i] + 1
    • D. a[j] + 1

19. ④处应填 ( )。

    • A. min
    • B. max
    • C. swap
    • D. abs

(2) 二分查找

题目描述: 在一个单调递增的整数序列 a 中，查找第一个大于等于 x 的元素的位置。如果所有元素都小于 x，则输出 n (序列长度，位置从0开始)。

01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int main() {
07     int n, x;
08     cin >> n >> x;
09     vector<int> a(n);
10     for (int i = 0; i < n; ++i) {
11         cin >> a[i];
12     }
13
14     int left = 0, right = n - 1;
15     int ans = n;
16
17     while (①) {
18         int mid = left + (right - left) / 2;
19         if (a[mid] >= x) {
20             ans = ②;
21             right = ③;
22         } else {
23             left = ④;
24         }
25     }
26
27     cout << ans << endl;
28     return 0;
29 }

20. ①处应填 ( )。

    • A. left < right
    • B. left <= right
    • C. left != right
    • D. left > right

21. ②处应填 ( )。

    • A. mid + 1
    • B. mid - 1
    • C. mid
    • D. left

22. ③处应填 ( )。

    • A. mid
    • B. mid - 1
    • C. mid + 1
    • D. left

23. ④处应填 ( )。

    • A. mid
    • B. mid - 1
    • C. mid + 1
    • D. right