完整解析

二、阅读程序

(1)

该程序实现了一种类似埃拉托斯特尼筛法（Sieve of Eratosthenes）的算法，用于预处理计算每个数的最小质因数。

• 程序逻辑：

  1. 初始化一个长度为 n+1 的数组 p，所有元素为 0。
  2. 从 i = 2 到 n 遍历。
  3. 如果 p[i] 仍为 0，说明 i 是一个质数（因为它没有被小于它的数筛掉），因此 i 的最小质因数是它自己。
  4. 然后，遍历 i 的所有倍数 j（从 i 开始，步长为 i）。
  5. 如果 p[j] 仍为 0，说明 j 还没有被标记过最小质因数，此时遇到的 i 就是 j 的最小质因数，因此将 p[j] 设为 i。
  6. 最后，程序累加从 p[2] 到 p[n] 的所有值并输出。

• 题目解析：

  1. 判断题 (真)：根据算法逻辑，p[i] 在循环结束后确实存储了 i 的最小质因数。例如，p[6] 会被 2 筛到，所以 p[6]=2；p[7] 不会被筛到，所以在 i=7 的循环中 p[7] 被置为 7。
  2. 判断题 (真)：当 n=10 时，手动模拟：
     • i=2: p[2]=2, p[4]=2, p[6]=2, p[8]=2, p[10]=2。
     • i=3: p[3]=3, p[9]=3。p[6] 已被标记，跳过。
     • i=5: p[5]=5。p[10] 已被标记，跳过。
     • i=7: p[7]=7。
     • 其余 p 值为 0。所以 p 数组为 {0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2} (注意 p 和 p 未使用，默认为0)。
  3. 判断题 (假)：这个算法是线性筛的变体，其内层循环 for (int j = i; ...) 只对 p[j] 为 0 的情况执行核心操作。其总执行次数近似于调和级数 n/2 + n/3 + n/5 + ...，时间复杂度为 O(n log log n)。O(n log n) 是一个更宽松的上界，但不是最紧确的描述。
  4. 选择题 (B)：当 n=12 时，p 数组的值为： p[2]=2, p[3]=3, p[4]=2, p[5]=5, p[6]=2, p[7]=7, p[8]=2, p[9]=3, p[10]=2, p[11]=11, p[12]=2。 求和：2+3+2+5+2+7+2+3+2+11+2 = 32。
  5. 选择题 (B)：移除 if (p[j] == 0) 后，p[j] 的值会被更大的因子覆盖。例如，p[6] 先被 i=2 设为 2，然后被 i=3 设为 3。p[j] 将存储 j 的最大质因数。对于 n=10，新的 p 值为： p[2]=2, p[3]=3, p[4]=2, p[5]=5, p[6]=3, p[7]=7, p[8]=2, p[9]=3, p[10]=5。 原和为 2+3+2+5+2+7+2+3+2=28。 新和为 2+3+2+5+3+7+2+3+5=32。输出会变大。

(2)

该程序使用深度优先搜索（DFS）算法来寻找一个二维字符网格中，由字符 '1' 构成的最大连通区域的面积。

• 程序逻辑：

  1. dfs(x, y) 函数用于从点 (x, y) 开始，探索所有与之四向连通（上下左右）的 '1'，并返回这个连通区域的大小。
  2. 函数通过递归调用实现。visited 数组用来防止重复访问同一个点，避免死循环。
  3. main 函数遍历整个 grid。每当遇到一个未被访问过的 '1'，就调用 dfs 计算其所在的连通区域大小，并用 max_area 记录遇到的最大值。

• 题目解析： 6. 判断题 (假)：程序通过递归函数 dfs 实现搜索，这是深度优先搜索（DFS）的典型特征。广度优先搜索（BFS）通常使用队列实现。 7. 判断题 (真)：如果所有 '1' 都是连通的，那么 dfs 函数只会被成功调用一次。main 函数的循环会遍历 n*m 个格子，dfs 函数内部也会访问每个 '1' 格子一次。因此，总时间复杂度与格子总数 n*m 成正比。 8. 判断题 (真)：增加的 dx, dy 坐标偏移量 (1,1), (1,-1), (-1,1), (-1,-1) 分别代表右下、右上、左下、左上四个对角线方向。将循环次数改为 8，即可实现八个方向的连通性检查。 9. 选择题 (C)：程序遍历所有点，对每个 '1' 连通块调用 dfs 计算其大小，并用 max_area 持续更新最大值。因此，程序旨在寻找最大连通区域的面积。 10. 选择题 (C)：输入中有三个连通块： * 左上角 2x2 的区域，面积为 4。 * 中间 (2,2) 的位置，面积为 1。 * 右下角 (3,3), (3,4) 的位置，面积为 2。 程序会分别计算出 4、1、2，并取最大值 4 作为输出。

(3)

该程序实现了一个经典的贪心算法，用于解决活动选择问题。

• 程序逻辑：

  1. 输入 n 个活动，每个活动有开始时间和结束时间。注意，代码中 cin >> activities[i].second >> activities[i].first 表示先读入开始时间存入 second，再读入结束时间存入 first。
  2. sort 函数对 pair 类型的 vector 进行排序时，默认先按 first 成员（即结束时间）升序排序。如果结束时间相同，再按 second 成员（开始时间）排序。
  3. 贪心策略：首先选择结束时间最早的活动。然后，从剩下的活动中，选择与已选活动不冲突（即开始时间晚于或等于上一个已选活动的结束时间）且结束时间最早的活动。
  4. current_end_time 记录上一个被选中的活动的结束时间。遍历排序后的活动列表，只要当前活动的开始时间不早于 current_end_time，就选中这个活动，并更新 count 和 current_end_time。

• 题目解析： 11. 判断题 (假)：根据第 12 行 cin >> activities[i].second >> activities[i].first，程序先将读入的第一个数存入 pair 的 second 成员，第二个数存入 first 成员。结合上下文，程序是按结束时间排序的，所以 first 对应结束时间，second 对应开始时间。因此，输入是先开始时间，后结束时间。 12. 判断题 (假)：该算法是贪心算法。它在每一步都做出局部最优选择（选择结束时间最早的活动），并最终达到全局最优。 13. 判断题 (真)：贪心策略的正确性依赖于活动已按结束时间排好序。如果不排序，算法可能会先选择一个结束时间很晚的活动，导致许多其他活动无法被选择，从而得不到最优解。 14. 选择题 (D)：这是一个标准的活动选择（或称为区间调度）问题的贪心解法。 15. 选择题 (C)：输入数据为（开始时间, 结束时间）：(3,5), (1,4), (5,7), (2,6), (8,9)。 1. 按结束时间排序后：(1,4), (3,5), (2,6), (5,7), (8,9)。 2. 选择第一个活动 (1,4)。count=1, current_end_time=4。 3. 下一个活动 (3,5)，开始时间 3 < 4，冲突，跳过。 4. 下一个活动 (2,6)，开始时间 2 < 4，冲突，跳过。 5. 下一个活动 (5,7)，开始时间 5 >= 4，不冲突。选择该活动。count=2, current_end_time=7。 6. 下一个活动 (8,9)，开始时间 8 >= 7，不冲突。选择该活动。count=3, current_end_time=9。 最终 count 为 3。

三、完善程序

(1) 最长上升子序列

这是一个经典的动态规划问题，使用 O(n²) 的时间复杂度解决。dp[i] 表示以 a[i] 结尾的最长上升子序列的长度。

• 状态转移方程：dp[i] = max(dp[j]) + 1，其中 0 <= j < i 且 a[j] < a[i]。

• 代码逻辑：

  • 外层循环 for (int i = 1; i < n; ++i) 遍历序列中的每个元素，计算 dp[i]。
  • 内层循环 for (int j = 0; j < i; ++j) 遍历 a[i] 之前的所有元素 a[j]。
  • 如果 a[i] > a[j]，说明 a[i] 可以接在以 a[j] 结尾的上升子序列后面，形成一个更长的序列。此时，我们尝试用 dp[j] + 1 来更新 dp[i]。
  • max_len 用于记录所有 dp[i] 中的最大值，即为整个序列的 LIS 长度。

• 题目解析： 16. C: 内层循环需要遍历 i 之前的所有元素，所以 j 的范围是 0 到 i-1，即 j < i。 17. A: 要构成上升子序列，当前元素 a[i] 必须大于之前的某个元素 a[j]。 18. B: 如果 a[i] 可以接在 a[j] 后面，那么以 a[i] 结尾的 LIS 长度至少是 dp[j] + 1。我们要取所有可能的前驱 j 中能使 dp[i] 最大的那一个。 19. B: max_len 需要在每次计算完一个 dp[i] 后，更新全局的最大值，因此使用 max 函数。

(2) 二分查找

本题要求在一个升序序列中，找到第一个大于等于 x 的元素的位置。这是一个二分查找的变种。

• 算法思想:

  • 维护一个搜索区间 [left, right]。
  • ans 变量用于记录“可能的答案”，初始化为一个哨兵值 n。
  • 当 a[mid] >= x 时，mid 是一个潜在的答案，我们记录下来 ans = mid。但是，可能还有更靠左的（更小的下标）也满足条件，所以我们需要在左半部分 [left, mid - 1] 继续查找。
  • 当 a[mid] < x 时，mid 以及 mid 左边的所有元素都小于 x，不可能是答案，所以我们必须在右半部分 [mid + 1, right] 查找。
  • 循环条件是 left <= right，确保当 left 和 right 相遇时，这个点也能被检查到。

• 题目解析： 20. B: left <= right 是包含端点的二分查找的经典循环条件，能确保搜索区间为空时才退出。 21. C: 当 a[mid] >= x 时，mid 本身就是一个满足条件的答案。我们用 ans 记下它。 22. B: 既然 mid 已经是一个可能的答案，我们就要尝试在 mid 的左边寻找是否有“更早”的答案，所以将搜索区间的右边界缩为 mid - 1。 23. C: 当 a[mid] < x 时，mid 以及它左边的所有元素都太小了，不可能是答案。因此，新的搜索区间应该从 mid + 1 开始。