【叉姐的魔法训练第一课_初级魔法练习】poj 2443 Set Operation ( bitset加速)

poj 2443题目链接

题意:给出n个可重集…以及集合中的元素。。。现在若干查询,每个查询给出一对数x,y,询问是否存在某个集合,同时拥有x,y两个元素(x,y可以相同)

思路:由于x,y最大时10000,容易想到对每一个元素开一个集合,记录这个元素出现的集合的标号,然后用 set_intersection 来做…

就是询问的时候交一下两个集合,看是否为空,结果Tle了。。。

正解其实也是这个思路,不过用到了bitset加速一下。因为我求集合相交的时候,并不需要知道交了以后的结果,只需要知道是否为空,那么我们不妨用bitset

对每个元素开一个bitset,每个bitset上,第i位为1表示,该元素在第i个集中中出现了。

求相交的时候,只需要两个bitset 位与一下,然后看结果中是否有1出现就好了。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz