AtCoder Beginner Contest 130 题解

AC Codes

A – Rounding

B – Bounding

C – Rectangle Cutting

只用一刀将一个矩形的面积平分，显然需要经过矩形的几何中心。

D – Enough Array

寻找数列 $A$ 中有几个和不小于 $K$ 的连续子序列。

两种方法：

固定左端点，二分搜索右端点，$O(N\log N)$ 。
双指针扫一遍。

E – Common Subsequence

给定两个长度分别为 $N,M$ 的数列 $S,T$ ，询问两个数列中有几对完全相同的子序列。

$N,M\leq 2000$ 。

假设 $dp[i][j]$ 表示两个子序列的最后一个字符分别为 $S_i,T_j$ 时的子序列对数。那么显然有：

dp[i][j]=\sum_{x=1}^{i-1}\sum_{y=1}^{j-1}dp[x][y]

显然我们可以再开一个二维数组维护dp的二维前缀和，然后上式就可以 $O(NM)$ 转移了。

F – Minimum Bounding Box

二维平面上有 $N$ 个点，每个点每一秒都会朝上、下、左、右中的一个方向移动一个单位距离。询问在某个时刻 $T$ ，用一个边平行于坐标轴的矩形框覆盖所有点，这个矩形框的最小面积？

$N\leq 10^5$ 。

要求的就是 $(x_{\max}-x_{\min})(y_{\max}-y_{\min})$ 的最小值。容易发现：$x_{\max}-x_{\min}$ 是一个随时间变化的分段一次函数，$y_{\max}-y_{\min}$ 同理。以水平方向为例，我们只需要考虑 $6$ 个点：最左侧和最右侧向右移动的点，最左侧和最右侧向左移动的点，最左侧和最右侧上下移动的点，当任意两个点在水平方向上相交时，才有可能导致函数发生变化。

因此本题可以表示为求函数：

(at+b)(ct+d)

的最小值，由于这个 $at+b$ 和 $ct+d$ 都是分段的一次函数，因此整个图像一定由一系列直线和抛物线构成。因此最暴力的做法就是将所有分段的函数求出，然后求导找极值点以及那些分段点，大力分类讨论。这个做法显然太繁，需要简化。

对 $(at+b)(ct+d)$ 进行一下简单的分析：

　$a\gt 0,b\gt 0$ ：此时两个一次函数都是递增的，并且由于 $at+b,ct+d\geq 0$ ，所以该函数必定是递增的，最小值一定是左端点。
　$a\lt 0,b\lt 0$ ：和情况1类似，但是该函数一定是递减的，最小值一定是右端点。
　$a\lt 0,b\gt 0$ ：此时，抛物线开口朝下，因此最小值要么是左端点，要么是右端点。

至此，发现一个非常重要的信息：我们要求的最小值一定在某个分段点上，因此我们需要做的就是求出所有分段点。这些分段点可以直接暴力枚举，情况数不超过 $2\times 6\times 6$ 种，对于每个点求出相交的时间，然后 $O(N)$ 求出该时间点需要多大面积的矩形框即可。

~~虽然这通分析看起来很厉害，但是代码还是写得巨长~~。