【考前冲刺Day1】天神下凡

题面

我们先来看看样例:

首先一开始就有一个区域;
一般来说,一个圆对答案的贡献为1,无论它是在外面还是在其他圆的里面。
但是,如果一个圆它的一条直径上所有的点都被覆盖了的话,它对答案的贡献就为2了
由于只能在x轴上安放,覆盖的情况我们也只要考虑x轴上的,所以就可以把这个问题抽象为一个线段覆盖问题。
首先将所有的线段离散化一下,再根据长度排序,对于每条线段,先查询它是不是被全部覆盖了,再用它来更新覆盖的区域,可以用线段树来维护。

考试的时候思路完全一致,就是线段树空间没有开够一定要开八倍空间!!!!,建树的时候也要从1到2*n

这种想法虽然很自然,但是代码又长,空间又大,时间又长,还容易写挂,先膜一波考试时A的大佬@Enstein用的是神奇的栈,@千柰用的是搜索……代码比我短,空间比我小,还更快,tql

代码

点赞
  1. Naoh说道:
    Google Chrome Windows 7

    吧吧吧哩吧

  2. 千奈说道:
    Google Chrome Windows 7

    1. 冒泡ioa说道:

      %%% tql

发表评论

电子邮件地址不会被公开。必填项已用 * 标注