1 solutions
-
0
A. 田字格
题目描述
给定平面上与坐标轴平行的 条黑色线段,求出它们构成多少田字格。一个田字格由三元组 表示,一个三元组是田字格当且仅当正方形 与平面上黑色部分的交恰好等于 六条直线与这个正方形的交。
题目解法
注意到一个田字格由三条等距的、中间没有插入其他横线的横线组,和三条等距的、中间没有插入其他竖线的竖线组构成。考虑先把这样的横线组和竖线组处理出来,然后计算所有横线组和竖线组可以合并出多少的田字格。
考虑第一步,维护出所有的竖线组,横线组类似。按照纵坐标扫描线,每次维护与 有交的竖线集合,按照横坐标排序。那么可能的竖线组在这个序列上一定是连续排列的(因为中间不能有其他竖线)。总共会形成 次插入,每次插入只会改变 个竖线组的存在情况,使用
set维护。这样我们可以得到 个四元组 ,表示从 到 ,三条竖线 存在且中间没有其他竖线。处理出所有的横线组和竖线组之后,枚举 ,此时竖线组的 和横线组的 是确定的。一个横线组 和一个竖线组 是一个合法的田字格当且仅当
- ;
- 。
这是一个二维偏序,对一维扫描线另一维树状数组统计即可。复杂度
- 1
Information
- ID
- 41
- Time
- 3000ms
- Memory
- 256MiB
- Difficulty
- (None)
- Tags
- (None)
- # Submissions
- 0
- Accepted
- 0
- Uploaded By