UOJ Logo zrnlkc的博客

博客

标签
暂无

可能是很妙的题。。

2017-04-09 20:42:55 By zrnlkc

__debug一说,好像可以出这么一道题,好像挺妙的。。于是特别想分享分享:b

给你平面上的n个点,并保证如果存在点(x,y),则必定存在点(y,x),求这些点组成了多少个矩形(矩形的边必须平行于坐标轴(感谢ruanxingzhi指出))

n<=100000

如果大家有什么做法可以告诉我

我们的做法后面再放:D


好吧这题原来是一道原题的弱化版,这就很尴尬了。。。(感谢Claris指出)

这题是这么来的,我们不久前考试有这么一道题:

给出一个无向图,求点不重复的四元环个数。

然后我发现这个可以变成现在这道题。。

然后发现反过来推的话好像并不好推。

然后就感觉挺妙的,毕竟我到目前为止都没有见过把平面上的计数题转成图上的。。(可能有,但反正我没见过(好吧我是laji))

当时发的题解贼恶心,复杂度也很(xuan)学$\Theta(mn^\frac{2}{3})$这样子。(好像是CF上的一道题)

然后有人去网上找到了别人的题解,做法很劲orz

传送门:轮回-不来也不去的一只失忆蝴蝶

这名字我都不知道该从哪开始吐槽了。。


具体是怎么变的就是如果在原图中有边(x,y)那么就在图中标上两个点(x,y),(y,x)。

然后一个四元环在平面上就是两个矩形了。

然后还有如果这个矩形有点(x,x)作为顶点的话,就是三元环或者就是一条边什么的。。

就是这样

共 1 篇博客