洛谷5617 [MtOI2019]不可视境界线
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
Luogu LOJ 分析 问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大，这里 $1$ 个点也算一条路径。 先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和，转移讨论各种情况把子树合并进来即可。 设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和，通过打表或...
Luogu LOJ 分析 先考虑没有 $o$ 的限制怎么做。可以想到贪心，把房间按容量小到大排序、订单按人数从小到大排序，然后依次枚举每个房间，选择能容纳的租金最高的那个订单。正确性比较显然。 现在加入这个限制，可以考虑 WQS 二分。设 $f(x)$ 表示接受 $x$ 个订单的最大收入，感性理解可以知道 $f(x)$ 是凸的。二分斜率 $m$，则我们要求最大的 $b=f(x)-mx$，而这...
Luogu 分析 设 $f(x)$ 为恰好选 $x$ 条白边的答案。容易发现 $f(x)$ 是凹的。 考虑 WQS 二分。二分斜率 $m$，则我们需要最小化截距 $b=f(x)-mx$。 把每条白边的权值减去 $m$ 即可求出 $b$ 的最小值，再根据此时最多选出的白边数调整二分上下界即可。 代码 // ==================================== // au...
Luogu 分析 设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。 考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。 这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。 考虑用堆解决这个问题。 维护一个小根堆，每次将 $a_i$...