完整解释

二、阅读程序

(1)

该程序计算从 1 到 n 的所有整数的约数个数之和。

• 程序逻辑：

  1. f(x) 函数计算正整数 x 的约数个数。它通过循环从 i = 1 到 sqrt(x) 来查找约数。如果 i 是 x 的约数，那么 x/i 也是 x 的约数。
  2. 为避免重复计数（当 x 是完全平方数时，i == x/i），代码检查 i * i != x。
  3. main 函数循环调用 f(i) 并将结果累加，最终输出总和。

• 题目解析：

  1. 判断题 (假)：f(x) 计算的是 x 的所有约数的个数，而非质因数个数。
  2. 判断题 (真)：6 的约数是 1, 2, 3, 6，共 4 个，f(6) 返回 4。
  3. 判断题 (真)：i * i <= x 和 i <= x / i 在整数运算下是等价的，后者是防止 i*i 溢出的更安全写法，不影响算法逻辑。
  4. 选择题 (B)：程序功能是累加每个数的约数个数。
  5. 选择题 (C)：f(1)到f(10) 的值分别为：1, 2, 2, 3, 2, 4, 2, 4, 3, 4。总和为 27。

(2)

该程序使用两次深度优先搜索（DFS）来求解树的直径（树中任意两点间的最长路径）。

• 程序逻辑：

  1. 从任意点（程序中为节点1）出发，通过 DFS 找到离它最远的点 endpoint。
  2. 再从 endpoint 出发，通过 DFS 找到离 endpoint 最远的点，这两点间的距离就是树的直径。

• 题目解析： 6. 判断题 (真)：n-1 条边，双向添加，构成了一个无向图的邻接表表示。对于 n 个点和 n-1 条边，这是一个树形结构。 7. 判断题 (真)：在树的 DFS 中，p 参数代表父节点，if (v != p) 的判断是为了防止从当前节点 u 遍历到邻居 v 后，又立刻返回到父节点 p。 8. 判断题 (假)：只执行一次 DFS 是找到从起始点（节点1）出发的最长路径，其长度不一定与树的直径有固定的比例关系。 9. 选择题 (C)：两次 DFS 是求解树的直径的经典算法。 10. 选择题 (B)：第一次 DFS 从 1 出发，最远的点是 4, 5, 6, 7 中的任意一个，距离为 2。假设找到 endpoint 为 4。第二次 DFS 从 4 出发，最远可以到达 6 或 7，路径为 4-2-1-3-6（或7），长度为 4。

(3)

该程序使用动态规划解决最大子数组和问题。

• 程序逻辑：

  1. dp[i] 的定义是：以 a[i] 元素结尾的连续子数组的最大和。
  2. 状态转移方程为 dp[i] = max(a[i], dp[i-1] + a[i])，表示以 a[i] 结尾的最大和要么是 a[i] 本身，要么是 a[i] 连接上之前以 a[i-1] 结尾的最大和。
  3. max_ans 变量用于记录所有 dp[i] 中的最大值。

• 题目解析： 11. 判断题 (假)：dp[i] 的定义是以 a[i] 结尾的子数组的最大和，这是一个关键且易混淆的细节。max_ans 才是记录全局的最大值。 12. 判断题 (真)：若所有元素为负，dp[i-1] 必为负，则 dp[i-1] + a[i] 必小于 a[i]。因此 dp[i] 总等于 a[i]，最终 max_ans 为数组中的最大值。 13. 判断题 (真)：程序只有一个 for 循环，时间复杂度 O(n)。使用了一个 dp 数组，空间复杂度 O(n)。 14. 选择题 (C)：这是解决最大子数组和问题的标准动态规划解法。 15. 选择题 (C)：原程序输出为 5。修改后 dp 数组变成了计算前缀和，其值为 {-1, -3, 2, 1, -1}。max_ans 在遍历过程中会记录 dp 数组出现过的最大值，即 2。因此输出从 5 变为 2。

三、完善程序

(1) 乘船问题

这是一个贪心问题。策略是优先让最重的人和最轻的人配对，以最大限度利用船的载重。

• 题目解析： 16. C: 指针 j 应初始化为指向最重的人，即数组末尾，下标为 n - 1。 17. B: 循环条件为 i <= j。当 i == j 时，剩下最后一个人，他需要自己坐一艘船，此情况需被处理。 18. C: 判断是否能配对，需要计算最轻 w[i] 和最重 w[j] 的体重之和。 19. B: 如果可以配对 (w[i] + w[j] <= limit)，说明最轻的人 w[i] 也上船了，所以 i 指针向右移动，即 i++。

(2) 二维区域和

本题使用二维前缀和来优化查询。s[i][j] 存储从 (1,1) 到 (i,j) 的矩阵和。

• 题目解析：
  • 预处理公式: s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
  • 查询公式: sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
  20. A: 对应预处理公式中的 s[i][j - 1]。
  21. C: 对应查询公式中的 s[x2][y1 - 1]。
  22. B: 对应查询公式中被重复减去而需要加回的左上角区域 s[x1 - 1][y1 - 1]。