2022—2023 学年第一学期期末 A 卷（有图论）

1. $\Theta(n\log n)$。
2. $\Theta(n^{\log_23})$。主定理中递归项占主导。
3. 现有原卷没有说明枢轴策略，也没说问最好、平均还是最坏时间，因此无法唯一作答。若按课程常用平均时间，则对 $N=2^{10}$ 个元素为 $\Theta(N\log N)$；最坏情况仍可为 $\Theta(N^2)$。不应把缺失条件偷偷补上。
4. 恰有 $n-1$ 条边，渐近为 $\Theta(n)$。

1. 错误。NPC 一定属于 NP；NP-hard 问题不一定属于 NP，甚至不一定是判定问题。
2. 无法判断。若 $P\ne NP$，交集为空；若 $P=NP$，NPC 问题也在 P 中。
3. 正确。最大独立集的判定版本 NP 完全；若它有多项式算法，则所有 NP 问题经规约都有多项式算法。
4. 错误。5 是固定常数，枚举所有五元顶点组需要 $O(n^5)$，仍为多项式时间。

图的强连通分量为

若每个邻接表按字母顺序访问，在反向图 $G^R$ 从 $a$ 开始，一种从早到晚的完成顺序是

h, i, g, f, d, c, e, b, a

再按完成时间逆序在原图启动 DFS，依次得到上述三个分量。题面没有规定同一顶点多条出边的访问顺序，因此发现/完成时间并非唯一；答案应与自己声明的邻接顺序一致，但 SCC 集合不变。

继续采用“邻接表按字母顺序访问”，并令计时器从 0 开始、每次发现或完成一个顶点时先加 1。第二遍 DFS 的发现/完成时间为：

三棵 DFS 树的根依次为 $a,d,g$，它们分别给出集合 {a,b,c,e}、{d,f} 和 {g,h,i}。

从 $a$ 出发，一种确定顶点顺序为

a, b, e, c, g, h, f, d

下表把每一行定义为“选定该行顶点，并完成它的出边松弛之后”的暂定距离；初始行还没有选定顶点：

因此最终最短距离为：

若把 $c\to e$ 改成 $-12$，不能继续使用 Dijkstra，因为已确定顶点的距离可能被后来负边再次降低。可改用 Bellman–Ford；该图若确认无环，也可按拓扑序松弛。

先把点坐标升序排序。取最左边尚未覆盖的点 $x_i$，放置区间

并跳过其中所有点，重复直到结束。

任何可行解都必须用某个区间覆盖当前最左点。把该区间右移到左端恰为 $x_i$ 不会丢失右侧覆盖能力，因此存在最优解包含贪心选择。排序 $O(n\log n)$，扫描 $O(n)$。

sort(x[1..n])
intervals = empty list
i = 1
while i <= n:
    left = x[i]
    right = left + l
    append [left, right] to intervals
    i = i + 1
    while i <= n and x[i] <= right:
        i = i + 1
return intervals

标准方法对单调谓词 A[i] == 1 二分，找第一个为真的位置，时间 $O(\log n)$。

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

若 1 的个数 $m\ll n$，从数组末尾向左做指数搜索：依次检查距离末尾 $1,2,4,8,\ldots$ 的位置，直到看到 0 或越过数组。第一个 1 位于最后两个检查位置之间，再二分该区间。指数搜索只走到 $O(m)$ 的后缀，时间 $O(\log m)$。

knownOne = n
step = 1
while n - step >= 1 and A[n - step] == 1:
    knownOne = n - step
    step = 2 * step

knownZero = max(1, n - step)
left = knownZero + 1
right = knownOne
while left < right:
    mid = floor((left + right) / 2)
    if A[mid] == 1:
        right = mid
    else:
        left = mid + 1
return left

题目保证 0 和 1 都出现，所以当指数搜索越过数组左端时，位置 1 一定可以作为 knownZero。指数阶段和二分阶段处理的范围都只有 $O(m)$。

先扫描所有边，找原图中度数最大的顶点 $v$，其度为 $\Delta(G)$。把 $v$ 的所有关联边加入生成树候选，此时形成一棵以 $v$ 为中心的星形局部树，不会成环。

再从已连接顶点出发做 BFS/DFS，每遇到一个尚未进入树的顶点就加入发现它的边，直到覆盖全图。原图连通，所以一定能扩展成生成树。

v = a vertex with maximum length(Adj[v])
T = empty edge set
visited[u] = false for every u in V
Q = empty queue

visited[v] = true
enqueue(Q, v)
for each w in Adj[v]:
    if not visited[w]:
        visited[w] = true
        add edge (v, w) to T
        enqueue(Q, w)

while Q is not empty:
    u = dequeue(Q)
    for each w in Adj[u]:
        if not visited[w]:
            visited[w] = true
            add edge (u, w) to T
            enqueue(Q, w)
return T

所得树中 $\deg_T(v)=\Delta(G)$。任何生成树都是原图子图，任何顶点在树中的度都不可能超过它在原图中的度，因此这已经达到全局上界。时间 $O(V+E)$。

两人均分时目标为 $S=m/2$。做 0-1 子集和：

保留前驱即可恢复第一人的袋子，剩余袋子给第二人。时间 $O(nm)$、空间 $O(nm)$；只判断可压为 $O(m)$。

三人均分时目标 $S=m/3$，只显式记录前两人的和：

第 $i$ 袋可给第一人、第二人或第三人。若 $dp[n][S][S]$ 为真，剩余总和也恰为 $S$。时间 $O(nm^2)$、空间可滚动为 $O(m^2)$。