三校集训Part2 NBCX Day8 Cloud 题解

题意

给出每个云的位置及大小以及移动方向,它们的移动速度均为$1$个单位长度每单位时间,在时刻0,所有的云没有重叠,问在所有时刻中(从负无穷到正无穷)中,云重叠层数最多是多少?

思路

非常显然,答案只有可能是$1$或$2$。
所以,直接$rand()\text{%}2$(逃:
咳咳,进入正题。
所以只要能判断是不是能有一片横着走的云和一片竖着走的云重合就行了。
令$ a_i = \text{第}i \text{朵云的上边缘} + \text{第}i \text{朵云的左边缘}, b_i = \text{第}i \text{朵云的右边缘}+ \text{第}i \text{朵云的下边缘}$,如果$i,j$两朵云重叠在一起,那么$a_i<b_j$且$a_j<b_i$。
也就是这两个区间有相交,那么乱搞一个数据结构来维护即可。

暂无评论

发送评论


				
上一篇
下一篇