日期：2019-06-20

上午

到校

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

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

然后发现讲师的PPT好像是从网上一个博客上抄的，有趣。 ::twemoji:sweat::

状态压缩

关键词：状态压缩，动态规划，位运算

位运算运算符

下表显示了 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到机房

然而饭没昨天的好吃。

版权属于：淡淡的路瑶

本文链接：https://www.starroad.top/archives/210.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！

Last modification：June 26th, 2019 at 05:35 pm
© 允许规范转载
如果您觉得我的文章有用，给颗糖糖吧。