【叉姐的魔法训练第一课_初级魔法练习】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出现就好了。

 

 

hdu 5036 Explosion||2014 北京区域赛网络赛 (概率+bitset优化的状态压缩+floyd传递闭包)

题目链接

题意:有n扇门,n种钥匙,一一对应。每扇门打开后可能得到k把钥匙(k可能为0)。一扇门还可以用一颗炸弹炸开。现在问要开所有门,使用炸弹的期望个数。

思路:状态压缩。用一个二进制串表示每扇门能打开的门的信息,对应的位上为1表示能打开,为0表示不能打开。

状态是可以传递的。。

如果第i扇门能打开门k,那么能打开第i扇门的第j扇门也可以打开门k。

状态压缩以及传递的过程可以很容易用bitset来维护,这才是bitset的正确打开姿势

相当于用floyd做了一个传递闭包。(floyd的有一层循环隐藏在了bitset中,复杂度没有改变,但是常数小)

最后对于期望的计算方法:统计能打开第i扇门的方案数计为cnt,这cnt的方案中,只有一种是用炸弹炸掉,因此用的炸弹数的期望数为1/cnt

由于期望的独立性,因此打开所有门所有的炸弹数的期望就是每个门的期望累加。

 

 

 

 

 

 

 

 

hdu 2051 bitset (水)

题目链接

题意:把一个数n(n<1000)转化成二进制输出。。。

思路:。。。搜acm bitset 搜到这题。。。所以其实这并不是“bitset”优化的题。。。只是题目名字交这个了2333。

还是用bitset过掉了。。。不过不知道怎么处理高位0.。。

所以这是一次bitset的错误示范(逃

 

 

 

acm 奇技淫巧 bitset

1.定义与初始化
在定义 bitset 时,要明确 bitset 有多少位,这个位数是整形常量

(tips:如果长度和输入的数m有关,在做翻转操作以后再统计时候会多算,一个可以的做法是设置一个长度为m,所有位上都是1的位串,然后翻转之后先与一下。类似的技巧还有很多。)

()
bitset<n> b;                          //b 有 n 位,每位都是 0
bitset<n> b(u);                     //b 是 unsigned long 型 u 的一个副本
bitset<n> b(s);                      //b 是 string 对象 s 中含有的位串的副本,这个s 必须是位串,也就是二进制码串
bitset<n> b(s, pos, n);        //b 是 s 中 从位置 pos 开始的 n 个位的副本

2.bitset 的操作
b.any()              //b 中是否存在置为 1 的二进制位?
b.none()             // 和b.any() 效果一样
b.count()            //b 中不存在置为 1 的二进制位吗?

b.any()             //b中存在置为1的二进制位吗?
b.size()              //b 中置为 1 的二进制位的个数
b[pos]               //访问 b 中在 pos 处二进制位
b.test(pos)        //b 中在 pos 处的二进制位置为 1
b.set()              // 把 b 中所有二进制位都置为 1
b.set(pos)        //把 b 中在 pos 处的二进制位置为 1
b.reset()          //把 b 中所有二进制位都置为 0
b.reset(pos)  //把 b 中在 pos 处的二进制位置为 0
b.flip()            //把 b 中所有二进制位逐位取反
b.flip(pos)       //把 b 中在 pos 处的二进制位取反
b.to_ulong()   //用 b 中同样的二进制位返回一个 unsigned long 值
os << b          //把 b 中的位集输出到 os 流
示例:

cout << b << endl;