洛谷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$ 个圆...
LOJ 分析 对于一张课桌，如果其区间被另外的课桌包含，那么它是没用的，可以去掉。那么剩下的课桌满足左右端点都递增。 对于每个班的学生，将其按身高排序，显然每两个人坐同一张课桌更优，且一定是身高小的坐 $l$ 小的桌子。 那么每对学生选择的桌子满足决策单调性，可以分治处理。在计算代价时，把所有班当前组的 $2m$ 个人拿出来按照身高排序，然后维护一个前缀和，这样子只需要二分一下就可以计算了。...
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...