2022 秋期末考试（无图论）

源目录中的文档只记录了题目概要，没有正式试卷和标准答案。我在下面忠实保留可确认的题意，并给出折叠参考解析。

一、连续 1 后接连续 0

有一个长度为 $n$ 的 01 串，其中所有 1 连续地出现在所有 0 之前，例如 1111100000。完成下面两问：

查看两种复杂度要求

字符串形如 $11\cdots1100\cdots0$ ，和就是 1 的数量，也就是第一个 0 的位置减 1。

在全长上二分第一个 0，时间 $O(\log n)$ ；
若 1 的个数为 $k\ll n$ ，从左端按位置 $1,2,4,8,\ldots$ 指数搜索到第一个 0，再在括住边界的区间二分，时间 $O(\log k)$ 。

第 $i$ 头牛每天吃 $d_i$ 斤草，处理并送走需要 $t_i$ 天，要求总耗草最少。

查看贪心顺序与交换论证

比较相邻两头牛 $i,j$ 。若先送 $i$ ， $j$ 在这 $t_i$ 天额外吃 $d_jt_i$ ；反序则 $i$ 额外吃 $d_it_j$ 。应让 $i$ 在前，当且仅当

d_jt_i\le d_it_j,

即

\frac{d_i}{t_i}\ge\frac{d_j}{t_j}.

所以按 $d_i/t_i$ 降序排列。用交叉乘积比较可避免浮点误差，排序时间 $O(n\log n)$ 。

有 $n$ 个哑铃和 $m$ 个轻重关系。第 $i$ 个关系 $(a_i,b_i)$ 表示第 $a_i$ 个哑铃比第 $b_i$ 个哑铃轻。请据此把全部 $n$ 个哑铃从轻到重排列；若两个哑铃的轻重关系无法由已知条件确定，则它们之间可以任意排列。

查看拓扑排序建模

关系 $(a_i,b_i)$ 表示 $a_i$ 比 $b_i$ 轻，建立有向边 $a_i\to b_i$ 。对该 DAG 做拓扑排序，输出任一拓扑序即可；无法比较的哑铃会自然以任意合法顺序出现。

若最终不能输出全部顶点，说明关系中存在矛盾环。时间 $O(n+m)$ 。

有 $n$ 个气球，第 $i$ 个气球上的数字为 $a_i$ 。只戳编号为 $2,3,\ldots,n-1$ 的气球；戳破一个气球时，所得分数等于它与当时左右相邻气球上三个数字的乘积。请设计戳球顺序，使总得分最高。

查看区间动态规划

在原数组两端保留边界。令

dp[l][r]

表示已经戳完开区间 $(l,r)$ 内所有气球能得的最高分。枚举区间内最后一个被戳的气球 $k$ ，此时它的相邻气球必是 $l,r$ ：

dp[l][r]=\max_{l<k<r} \left\{dp[l][k]+dp[k][r]+a_la_ka_r\right\}.

按区间长度递增计算，时间 $O(n^3)$ 、空间 $O(n^2)$ 。选择“最后一个”而不是“第一个”，才能让左右子问题互相独立。