周中训练笔记21-白红宇的个人博客

周中训练笔记21

发布日期：2021-05-14 13:34:25 浏览次数：15 分类：精选文章

本文共 513 字，大约阅读时间需要 1 分钟。

数据库考试结束了，我开始全身心投入学习状态压缩（DP）的学习中。然而，我发现状态压缩（DP）的大多数实现都依赖于位运算，这一点让我感到有些困惑。

有些人可能会将每个状态选取与否对应到二进制位上，这样可以压缩状态数据为一个整数，从而便于计算和维护。

大部分人使用位运算来处理状态压缩的问题，这使得状态数据保存更加高效。每个单元状态通常只有两种可能性，可以用0或1来表示。例如，棋盘上的格子可以是放棋子或不放棋子，硬币可以是正反两面。这些状态可以被压缩到一个二进制整数中。

在学习状压DP的过程中，我收集了几种常用的位运算技巧：

~x：取反操作

对于偶数x，执行x | 1

左移操作：1 << x

右移操作：1 >> x

XOR操作可以用来获取对应的值（例如0对应1，2对应3，8对应9）

生成一个所有位都为1的n位数：1 << n - 1

消造一个形如10、100、100000的二进制数（如[0, k-1]为0，[k,k]为1）：1 << (k-1)

状态压缩DP中的常用操作包括：

将a的第k位设置为1：a |= 1 << k

将a的第k位设置为0：a &= ~(1 << k)

检查a的第k位是否为1：a >> k & 1

上一篇：并查集

下一篇：状压DP

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！