almost 3 years ago

前言

我的做法相当暴力。。。

题目大意

给出二维平面上个点,要求画条不同的直线,其中两条平行于轴,两条平行于轴,这条直线将平面分成了个部分,使得每个部分内点的个数是给定的一个排列。直线不能经过给定的点。
满足

分析

首先我们枚举每个部分有多少个点,枚举了之后我们可以直接确定,顺便判断一下所有的连续三个的和是否满足条件。然后问题就变成了如何区间求和。
第一反应,二维树状数组,空间Bomb!,第二反应,二维线段树,不想写。。。
我们观察一下就可以发现,我们只需要求几个二维前缀和便可以解决问题。我们对块先编号:
3 6 9
2 5 8
1 4 7
由于1+2+3之类的已经确定,我们先求出1是否满足要求,然后再求出1+2,1+4,1+2+4+5,便可以判断全图是否满足要求。离散化后,对于前缀和,我们就是要求的点的个数,可持久化线段树即可。
因此总时间复杂度就是
CF260E.cpp

← CF235E 集训的一道组合计数的题 →
 
comments powered by Disqus