日期：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)
- 要检查 x 转二进制数后的第 i 位是否为1：
按位或运算的一个主要作用是设置指定位置为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
- 求$2^x$：
右位移的主要作用是求$\frac{x}{2^x}$
- 求$2^{-x}$：
1>>x
- 求$2^{-x}$：
状压dp
用DP解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。但是有这样的一些题目，它们具有DP问题的特性，但是状态中所包含的信息过多，如果要用数组来保存状态的话需要四维以上的数组。于是，我们就需要通过状态压缩来保存状态，而使用状态压缩来保存状态的DP就叫做状态压缩DP。
写了一些题，题解稍后。
参考资料
状态压缩动态规划 状压DP - Tony_Double_Sky - 博客园
下午
到校
14:23到机房，然而绝大部分都到了。高二在毕业会考，楼道里很安静。
水题
我怎么知道我在干什么？
晚上
19:00到机房
然而饭没昨天的好吃。
版权声明：本文是原创文章，版权归 星雾月雨 所有。
本文链接：https://www.ariels.xyz/archives/210.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。
5 comments
操你大爷。
。爷大你操
你大爷
1233211234567哈哈哈呵呵呵
YPJ,Go ahead.