日期:2019-06-20

上午

到校

07:09到校,发现早饭只有沙琪玛和八宝粥,其他的都被抢完了,博主心里有句mmp不知当讲不当讲。看来下次要早点到校啊。

07:20到了机房,一片安静。博主先解决了一种特殊的上网问题,部署了环境。

然后发现讲师的PPT好像是从网上一个博客的,有趣。

状态压缩

关键词:状态压缩,动态规划,位运算

位运算运算符

下表显示了 C++ 支持的位运算符。假设变量 A 的值为 60,变量 B 的值为 13,则:

运算符描述实例
&如果同时存在于两个操作数中,二进制 AND 运算符复制一位到结果中。(A & B) 将得到 12,即为 0000 1100
^如果存在于其中一个操作数中但不同时存在于两个操作数中,二进制异或运算符复制一位到结果中。(A ^ B) 将得到 49,即为 0011 0001
~二进制补码运算符是一元运算符,具有"翻转"位效果,即0变成1,1变成0。(~A ) 将得到 -61,即为 1100 0011,一个有符号二进制数的补码形式。
<<二进制左移运算符。左操作数的值向左移动右操作数指定的位数。A << 2 将得到 240,即为 1111 0000
>>二进制右移运算符。左操作数的值向右移动右操作数指定的位数。A >> 2 将得到 15,即为 0000 1111
  • 按位与运算的一个主要作用是检查指定位是否为1和判断奇偶性

    • 要检查 x 转二进制数后的第 i 位是否为1: (x & (1 << i - 1)
    • 例如判断一个数x是偶数 : if(x & 1 == 0)
  • 按位或运算的一个主要作用是设置指定位置为1

    • x转二进制数后的第i位置为1 : x |= 1 << i - 1
    • x转二进制数后的第i位置为0 :x=(x&(~(0X1<<i)))
  • 按位异或运算的主要作用是使指定位置取反

    • x转二进制后的第i位取反:x ^= 1 << i – 1
  • 左位移的主要作用是求$2^x \times x$

    • 求$2^x$:1<<x
  • 右位移的主要作用是求$\frac{x}{2^x}$

    • 求$2^{-x}$:1>>x

状压dp

用DP解决一个问题的时候很重要的一环就是状态的表示,一般来说,一个数组即可保存状态。但是有这样的一些题目,它们具有DP问题的特性,但是状态中所包含的信息过多,如果要用数组来保存状态的话需要四维以上的数组。于是,我们就需要通过状态压缩来保存状态,而使用状态压缩来保存状态的DP就叫做状态压缩DP。

写了一些题,题解稍后。

参考资料

状态压缩动态规划 状压DP - Tony_Double_Sky - 博客园

下午

到校

14:23到机房,然而绝大部分都到了。高二在毕业会考,楼道里很安静。

水题

我怎么知道我在干什么?

晚上

19:00到机房

然而饭没昨天的好吃。

Last modification:June 26, 2019
如果您觉得我的文章有用,给颗糖糖吧~