题解 P6376

w33z8kqrqk8zzzx33 · 2020-04-20 20:36:36 · 题解

第一次首 A 一个黑题，要发题解纪念

毒瘤题，有卡精度有卡常数。。。

这道题目一看上来彻底没有思想，应为圆形不能用扫描线处理。然后，另一个可能想到的想法是随机挑一堆点，然后把这些点的覆盖概率加起来，但是这样不仅暴精度还是 O(n^3)，明显过不了。

正解：

假设对与一个线 x=L，这个线期望覆盖的长度为 f(L)。应为期望线性，如果我们可以计算 f(L)，那么答案为

这个可以用自适应辛普森法计算，代价是大概 O(N\log N) 个 f 计算。

怎么计算 f 呢？对与任意一个平面上的点，如果这个点被 i 个圆形覆盖了，这个点的被选的圆形覆盖了的概率为 1-(\frac{N-1}{N})^K。这是应为这个点没有被最终覆盖上需要在 N-i 个剩下圆形重复选 k 个，或者 (N-i)^k 个方案；总共有 N^k 个方案，点被覆盖了的概率就是 1-(\frac{N-1}{N})^K 了。

（又）应为概率线性，如果统计一下这个线段上面有多长被恰好 i 个圆形覆盖了，叫 t_i，那么有

这样，直接用扫描线处理 t_i 就可以 O(N) 计算 f，总共复杂度在 O(N^2\log N) 左右，大力卡常就过了。