codeforces # 440 div2 E. Points, Lines and Ready-made Titles (和图有关的计数,思维题)

题目链接

题意:有n个整点,每个点处可以什么都不画,或者画一条垂直方向的直线,或者画一条水平方向的直线。

现在给出n个点的坐标,问最多右多少种不同的图案。(只要有一处不同,就认为两个不同)

思路:

参考题解

好菜啊不会做,转载一段题解。

bzoj 1854的并查集思路蜜汁契合 // 看完了题解的我这样想道

首先显然可以将图分为若干个联通块。

且慢,哪里来的图? 那就先考虑建图? 不急不急,先来想想看每一个联通块的性质。

如果该联通块中有环的话,肯定每条边都能取到;如果联通块是一棵树,那么必有一条边取不到(具体阐述见上bzoj 1854),所以只需要知道

  1. 这个联通块中有多少条边
  2. 这个联通块是不是环

这两个信息就可以了

那么可以直接上并查集。

什么样的点可以并到一起呢?横坐标相同的或者纵坐标相同的。

有没有环怎么维护呢?看有没有加进去的边的端点本身就在一个集合里。

联通块中边的数目又怎么知道呢?这倒还挺有意思的,其实只要直接看出现过多少个横坐标或者纵坐标就可以了,因为一个横坐标或者一个纵坐标就代表一条可以选的直线,所以这块联通块的贡献就是2^(x+y)者2^(x+y)-1

然后呢?就做完了。

然而呢?比赛结束。一天了。

相关并且有趣的题目:bzoj1854
codeforces #346 div2

说点什么

您将是第一位评论人!

提醒
wpDiscuz