冒泡ioa
冒泡ioa

【考前冲刺Day1】天神下凡

题面

我们先来看看样例:

http://bubbleioa.top/wp-content/uploads/2018/11/god.jpg

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

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

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

代码

发表评论

textsms
account_circle
email

  • Naoh

    吧吧吧哩吧

    3年前 回复
  • 千奈

    3年前 回复

冒泡ioa

【考前冲刺Day1】天神下凡
题面 我们先来看看样例: 首先一开始就有一个区域; 一般来说,一个圆对答案的贡献为1,无论它是在外面还是在其他圆的里面。 但是,如果一个圆它的一条直径上所有的点都被覆盖了的话,…
扫描二维码继续阅读
2018-11-03