Loading... 日期:2019-06-20 ## 上午 ### 到校 07:09到校,发现早饭只有沙琪玛和八宝粥,其他的都被抢完了,博主心里有句`mmp`不知当讲不当讲。看来下次要早点到校啊。 <img src="https://www.cdn.starroad.top/usr/themes/handsome/assets/img/emotion/aru/crying.png" class="emotion-aru"> 07:20到了机房,一片安静。博主先解决了一种特殊的上网问题,部署了环境。 然后发现讲师的PPT好像是从[网上一个博客](https://blog.csdn.net/soundwave_/article/details/52100038)上*抄*的,有趣。 <img src="https://www.cdn.starroad.top/usr/themes/handsome/assets/img/emotion/twemoji/sweat.png" class="emotion-twemoji"> ### 状态压缩 关键词:状态压缩,动态规划,位运算 #### 位运算运算符 下表显示了 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 - 博客园](https://www.cnblogs.com/Tony-Double-Sky/p/9283254.html) ## 下午 ### 到校 14:23到机房,然而绝大部分都到了。高二在毕业会考,楼道里很安静。 ### 水题 ~~我怎么知道我在干什么?~~ ## 晚上 19:00到机房 然而饭没昨天的好吃。 <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/210.html">https://www.starroad.top/archives/210.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:June 26th, 2019 at 05:35 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
5 comments
操你大爷。
。爷大你操
你大爷
1233211234567哈哈哈呵呵呵
YPJ,Go ahead.