第四课

A - 点到线段的距离

三分经典题，带点计算几何，也可以纯数学解法。

设一个线段 $AB$ 上的动点 $C$，那么一般来说 $C$ 与 $P$ 的距离是先减小后增大的，这显然是一个单峰函数，所以我们直接三分 $C$ 点的位置即可。

如果三分的是 $C$ 至 $A$ 的长度在整个线段中的占比，那么可以直接用缩放向量的方式求出 $C$ 点坐标；如果是直接三分了 $C$ 至 $A$ 的长度，那么可以考虑转化成比例来计算。

另外就是一个小常识，在一个三维空间中两点的距离满足：

B - 三角形与四边形

一看就不是三分题。因为随着 AD 的增大，ADE 与 BDEC 的面积比也会越来越大。

所以直接二分 AD 长度，用海伦公式计算面积并求出比例即可。

另外细节：浮点二分的判断条件是 $lr$ 。

C - 最大比例

01分数规划模板题。

首先我们考虑一个最大比例 $ans$，则其应该满足要求：

其中 $x_i$ 表示构造出这个最大比例的序列中选或者不选这个数字。

进行简单的移项等操作，可以得到：

接下来考虑如何得到这个 $ans$ 。很显然答案具有单调性，即 $ans$ 越大，单个被选中的物体对答案的贡献就越小，我们就需要选择更多的物体来使得他们的和等于 $0$（因为等于 $0$ 时就代表了我们取到了正确答案）

所以考虑二分答案，问题来到了如何判断选择的 $mid$ 是大了还是小了。因为我们知道随着 $mid$ 的增大，贡献一定会越来越小，所以我们直接选择最大的 $k$ 个，这样如果大于等于零就意味着答案还能提升，否则就是太大了。

最后有个细节，别忘了用最终的答案处理一下有哪些是要选择的，因为如果你是在 check 的时候记录了那些需要选择，那么最后一次 check 也有可能不是答案，所以要在最后处理一下哪些二元组需要选择。

D - 后缀零

很显然题目有单调性：$n$ 越大 $n!$ 后缀零越多。

考虑如何快速求 $n!$ 中后缀零的个数。每有一个后缀零其实都意味着有一个因子 $10$，而 $10=2\times 5$ 。

很显然在 $1\sim n$ 中，$2$ 的倍数的数量远远大于 $5$ 的倍数的数量。

所以说问题就变成了让我们数 $n!$ 中有多少个质因子 $5$ 。

而关于求 $n!$ 中有多少个质因子 $p$ 我们有一个计算公式：

证明也很简单，因为我们是若干个数乘在一起，所以因子数量可以相加。而每一个除法的含义就是数 $1\sim n$ 中 $p^i$ 的倍数的数量。那有人可能会问，那你看看 $p^{i}$ 的倍数是不是都是 $p^{i-1}$ 的倍数，那你不是数重复了吗？非也。因为 $p^i$ 和 $p^{i-1}$ 差了 $p$，这个 $p$ 就是我们要数的内容，所以重复数是正确的。

E - 最小距离最大化

基础题。

二分最小距离，贪心 Check 即可。

F - 矩阵

二分套二分。

首先发现直接计算特别困难，所以我们考虑优先二分答案然后判断它是不是第 $m$ 小。

对于二分的答案，我们只需要数出比他小的数是不是 $m-1$ 个即可。

而发现 $i$ 对答案的贡献永远为正，又是一个单调性，所以可以二分 $i$ 求出每一列比答案小的数的数量。注意边界，如果这一列所有的元素都比该元素大，那么贡献就是 $0$，所以 $l$ 的下限应该是 $0$ ；而当出现所有数都小于当前数的情况时，我们需要一个极大值让我们二分到最后一个数而不是 $n+1$ 或者 $-1$，所以 $r$ 的上限应该是 $n+1$；并且在计算价值时要把这两个特殊值记录了。

第五课

A - 最少末尾零

经典题。

很显然如果我们选择走了最少的 $2$ 因子路线就难以兼顾 $5$ 因子。即使我们这条 $2$ 路径上 $5$ 因子的数量比 $2$ 因子还少，那么会有以下几种可能：

  1. $2$ 路径上的 $5$ 同样是最少的 $5$ 路径，那么我们会选择另外一个 $dp$ 状态
  2. $2$ 路径上的 $5$ 不是最少的 $5$ 路径，那么我们肯定会选择最少的 $5$ 路径状态作为答案。

对于 $5$ 路径上的分讨同理。所以说这样我们只需要求出最后的状态从 $dp[n][n][0/1]$ 中取一个最小值就是答案。

然后转移的时候记录前驱即可。

另外有一些细节，如果最终答案大于一，我们可以选择直接走 $0$ 以获得只有 $1$；另外对于 $(1,1)$ 节点就是 $0$ 的情况也需要特判。

B - 最小的最长上升子序列

经典题。

状态为 $dp[i]$ 表示以 $i$ 结尾的最长上升子序列长度。然后维护一个数组 $b[i]$ 表示长度为 $i$ 的最长上升子序列最后一位的最小值。

然后每次插入一个 $a_i$ 去取代掉 $b$ 中第一个大于等于它的元素，并更新状态。

统计答案很简单。从后往前，遇到 $dp[i]=len$ 的就记录，然后 $len-1$，以此类推找出最小的最长上升子序列

但为什么对呢？因为我们会注意到从后往前按理来说应该是不能兼顾到字典序的。

我们假设按照此算法得出的最长上升子序列是：$a_{i_1},\dots,a_{i_x} ,a_{k_x}, \dots,a_{i_{len}}$
但是，真正的答案应该是：$a_{j_1},\dots,a_{j_y} ,a_{k_y}, \dots,a_{j_{len}}$

这两个序列的前面 $[i_1,i_x]$ 和 $[j_1,j_y]$ 完全一样，但是 $k_x$ 和 $k_y$ 不一样。

  1. 如果 $a_{k_x} > a_{k_y}$：这意味着算法选择的元素值大于真实字典序最小序列中的对应元素。但根据算法的工作原理，$b$ 数组存储了每个长度的最小末尾值，并且重建时从后往前选择最后一个满足 $dp[i] == len$ 的元素，这确保了算法会选择可能的最小值。如果 $a_{k_y} < a_{k_x}$，那么 $a_{k_y}$ 必须已经出现在 $b$ 数组中，且算法会优先选择它（因为它是更小的值），这就产生了矛盾。因此，这种情况不可能发生。
  2. 如果 $a_{k_x} < a_{k_y}$：这意味着算法选择的元素值更小，因此算法序列的字典序更小，这与真实字典序最小的假设矛盾。所以，真实序列不可能是字典序最小的。
  3. 如果相等：则序列相同，没有矛盾。

证毕。

C - 拾牌游戏

数据范围极小，所以考虑开状态 $dp[l1][r1][l2][r2]$ 表示第一堆卡还剩下 $l1\sim r1$，第二堆卡还剩下 $l2\sim r2$ 的最高分数。

由于两个人都绝对聪明，所以两个人策略相同，可以使用同一个代码计算。

D - 凑硬币

经典的多重背包。

因为每个单位可以选多次但有一个上限，我们不难想到一个单位一个单位地选，但是这样空间会爆炸，泛用性不高。

于是考虑优化。

因为若干个二的整数次幂是可以凑出所有数字的，所以说我们可以考虑把物品拆成捆绑的若干个二整数次幂组。

但是注意，我们的目的是要让他凑出尽可能多的二进制数，所以应该从小到大拆。如果将其数量进行二进制分解，就达不到我们的目的了。

除此之外应该没有什么注意事项了。

E - 补充括号

区间DP。

设状态 $dp[l][r]$ 表示使区间 $[l,r]$ 合法所需补充的最少括号数量，并且尝试在转移过程中维护答案 $ans[l][r]$。

初始值非常的好理解，对于单个括号 $dp[i][i]=1$ 并且 $ans[i][i]$ 是他的完全体。

合并的时候从小区间合并到大区间，有种转移方式：

  1. $s[l]$ 和 $s[r]$ 是一对的，考虑直接从区间 $[l+1,r-1]$ 转移过来。
  2. 寻找一个断点 $mid$ 表示区间 $[l,mid]$ 和 $[mid+1,r]$ 分别自成一个合法括号序列的情况。

其余应该没有太大的细节。

F - 学习课程

经典的分组背包。

题目表述有点问题，每门课程应该是只能学习一次的。

有了上面这个常识，就可以看出它是分组背包的模板。但是关于分组背包有一个疑问，它的枚举顺序应该是：

1
2
3
for(int i = 1; i <= n; i++) // 枚举组
    for(int k = m; k >= 0; k--) // 枚举容量
        for(int j = 0; j <= k; j++) // 枚举物品

但是说按照分组背包的说法，他应该是枚举组的情况下做 01 背包，而 01 背包应该是先枚举物品再枚举容量的。

如果交换了枚举的顺序，就会导致无法保证每个物品只选取了一次，从而影响正确性。

G - 选取信号

少量模型转化。

因为我们知道不相交的两条线 $a_i\rightarrow b_i,a_j\rightarrow b_j$ 满足这样的要求：$a_i<a_j$ 且 $b_i<b_j$ 。

而我们知道在这道题目中 $a_i$ 其实就是下标，先天有序，所以直接对于 $b_j$ 求最长上升子序列的长度即可。

H - 回文构造

很简单。

我们要添加最少的字符使得一个串变成回文串，实际上就是它和它反转后的串的最长公共子序列。

为什么呢？画几个图就不难得出：

1
2
3
4
5
6
7
s:    abcd
t: dcba
r: dcbabcd

s:  aab
t: baa
r: baab

一定可以这样插空得出答案，并且这样一定是最小的，因为我们充分利用了几乎所有相同的字符。

I - 最大子矩阵和

类似最大子段和。枚举一个上界和下界，对于截取的部分求最大子段和即可。