NOIP 2017系列解题报告 – [题组/NOIP]


Day2 T1 奶酪 并查集/搜索

你可以点击这个链接下载全部的AC代码

题目传送门(LOJ)

题解

我们可以 O(N^2) 来枚举所有点对,如果他们可以互相到达,则放到一个并查集里,另外单独计算一下可以到达上表面的点,并与上表面并到一起,下表面同理

最后看一下上下表面在不在同一个集合里即可。

对于搜索,我们可以 O(N^2) 预处理某个点可以到达那些点并挂链(当然直接暴力枚举也是可以的), 然后对于每个可以接触到下表面的点搜索一遍可以到达的所有点, 看是否有能接触到上表面的,记录一个 Flag 即可

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注