111qqz的小窝

老年咸鱼冲锋!

codeforces div 1 443 A. Short Program (位运算的理解)

题目链接:

题目链接

题意:

一段程序,最多5E5个操作,每个操作的格式为 <opt,x> ,opt表示位或,位异或,位与 三种位运算的一种,x表示范围0..1023的数。现在要求将该程序化简至最多 5个操作,使得对于0..1023的输入,输出与该程序同样的结果。

思路 :

关键在于想起,位运算还是按照二进制位的运算。我们考虑每位即可。

如果初始是0,现在变成了1,那么实际上我们并不确定,这个操作是xor 1 还是 or 1

因此我们需要两个初始的数,一个所有二进制位上都是0,另一个所有二进制位上都是1.

也就是0和1023

对于某个二进制位

如果初始的 (0,1)变成了 (1,1),那么说明这个位置上的位运算是or

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上的位运算是xor

如果初始的 (0,1)变成了(0,0) 那么说明这个位置上的位运算是and

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上没有进行位运算操作。

 

 

 

 

 

 

 

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

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

 

 

 

 

 

 

 

 

cf 611 B ||codeforces goodbye 2015 B. New Year and Old Property (数学或者数位dp)

http://codeforces.com/contest/611/problem/B
题意:问a到b(1E18),二进制表示中只有一个0的数有多少个。
思路:这么大的数。。。不是有循环节就是math problems.    UD:20160318讲道理还有可能是数位dp好不好。。。
我们发现可以很容易得算出1到x的二进制表示中只有一个0 的数有多少个。

problem solved.

 

20160318update:学了数位dp后又看到这题。。。这题显然是数位dp啊。。。亏我找规律搞了出来2333.

后面附上数位dp方法AC的代码

 

数位dp的方法:

codeforces #320 div 2A – Raising Bacteria (位运算)

x的二进制表示中1的个数即为答案.

原因是,每天晚上糖果数量翻倍,相当于左移1位,这时候二进制表示中1的数量不变

也就是说,二进制表示中的所有的1,一定都是添加进去的

而且也只有二进制表示中的1是添加进去的

所以二进制表示中1的数量,就是添加的糖果数.