2020—2021 学年第一学期补考试卷（有图论）

• 第 1 题：$\Theta(n\log n)$。因为

• 第 2 题：$\Theta(n)$。递归树代价是 $n+n/2+n/4+\cdots$。
• 第 3 题：$\Theta(\log n)$；更完整地写是 $\Theta(\log n+\log m)$，而 $m<n$ 时可用 $\Theta(\log n)$ 表示。
• 第 4 题：最多 $n(n-1)/2=\Theta(n^2)$ 条边。

这与随卷答案的选项 (d)、(c)、(b)、(e) 一致。

1. 正确。能在多项式时间求解，自然也能在多项式时间验证。
2. 错误。$X\le_p3SAT$ 只说明 3SAT 至少和 $X$ 一样难；许多 P 问题也能规约到 3SAT。
3. 正确，这里把 TSP 理解为经典 NP 完全判定问题。若 3SAT 在 P 中，则所有 NP 问题、包括 TSP 都在 P 中；取逆否命题即可。
4. 错误。10 是固定常数，可枚举所有 10 个顶点的组合并检查，时间 $O(n^{10})$，仍是多项式。

按图中从左到右的邻接顺序，一种 BFS 出队顺序为

6, 4, 2, 7, 1, 5, 9, 10, 3, 8, 11

各层与距离：

• 距离 0：$6$；
• 距离 1：$4$；
• 距离 2：$2,7$；
• 距离 3：$1,5,9,10$；
• 距离 4：$3,8$；
• 距离 5：$11$。

邻接顺序改变时同层顶点的先后可变，但距离不变。

一种没有同权歧义的选边顺序是：

每一步都选跨越“已入树顶点与树外顶点”这个割的最轻边。九条边连接十个顶点，总权重为

原卷只写了“递增—递减—递增”，没有说明相邻元素能否相等，也没有另行声明内部最小值必为负。下面的 $O(\log n)$ 算法按示例所表达的意图，作如下解释：以下按严格单调理解，并假设内部谷值小于 0。若允许中途出现平台，仅靠当前元素与相邻元素的大小关系可能无法判断谷底在哪一侧；缺少进一步条件时，可线性扫描求最小值，时间 $O(n)$。

对中点 mid：

• 若 $A[mid]\ge0$，最小值一定在右侧；
• 若 $A[mid]<0$ 且 $A[mid]>A[mid+1]$，仍在下降，最小值在右侧；
• 若 $A[mid]<0$ 且 $A[mid]<A[mid+1]$，已在谷底右坡，最小值在左侧或就是当前点。

left = 1
right = n - 1
while left < right:
    mid = floor((left + right) / 2)
    if A[mid] >= 0 or A[mid] > A[mid + 1]:
        left = mid + 1
    else:
        right = mid
return A[left]

每轮把区间减半，时间 $O(\log n)$、空间 $O(1)$。这里的严格单调和负谷值是解法采用的解释，不是原卷明写的额外条件。

用指针 $i$ 指向 $X$ 下一个待匹配元素，扫描 $Y$：

i = 1
for j = 1..n:
    if i <= m and X[i] == Y[j]:
        i++
return i == m + 1

扫描过程中总是用当前最早可用位置匹配，不会损失后续可能。时间 $O(n)$、额外空间 $O(1)$。

令

表示前 $i$ 个数字插入 $k$ 个加号后的最小和。最后一段若从 $p+1$ 到 $i$，则

边界为 $dp[i][0]=number(1,i)$，答案 $dp[n][m]$。状态 $O(nm)$，每个枚举 $O(n)$ 个分割点，总时间 $O(n^2m)$。

若 number(i,j) 直接解析需 $O(j-i+1)$，先预处理所有子串数字：

预处理 $O(n^2)$，DP 仍为 $O(n^2m)$。实际实现还要考虑长整数溢出。