首页 > 其他 > 详细

AtCoder Beginner Contest 131 Task F. Must Be Rectangular

时间:2019-11-13 00:26:58      阅读:104      评论:0      收藏:0      [点我收藏+]

Score: 600 points

Approach

固定横坐标 $x$,考虑横坐标为 $x$ 的竖直线上最多可以有几个点。

Observations

若最初两条竖直线 $x_1$、$x_2$ 上都有一个纵坐标是 $y$ 的点,则

  • 这两条竖直线上的点可以“合并”
  • 最终这两条竖直线上的点必定是一样的

我们发现了竖直线之间的等价关系:两条竖直线上有纵坐标相同的点。
用并查集维护这个等价关系。将同一个等价类中的竖直线上的点合并。

AtCoder Beginner Contest 131 Task F. Must Be Rectangular

原文:https://www.cnblogs.com/Patt/p/11846215.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!