状态压缩

简介

状态压缩是一种通过二进制位操作来高效表示和处理集合或状态的方法，每一个二进制位表示一个元素的状态，二进制位的集合表示一整个集合的状态。它常用于动态规划、组合数学和图论等领域，尤其是在状态空间较小但需要高效存储和操作的场景中。

常用操作

状态压缩常用的操作：

1.批量统计i的二进制数中1的个数

1
2
3

for (int i = 0; i < totalState; ++i) {
    cnt[i] = cnt[i >> 1] + (i & 1);
}

2.统计单个数num的二进制数中1的个数，32可以为其他数，取决于num的二进制数长度

1

Integer.bitCount(num);

3.遍历state的子集，比如state是011，那么子集是{001, 010, 011}

1
2
3

for (int subMask = state; subMask; subMask = (subMask - 1) & state) {
    operate subMask...
}

4.取a的最低位1，比如a = 00110100，则lowBit = 100，这个操作在树状数组中需要用到。

1

int lowBit = a & -a

5.判断x是否是y的子集，表达式为true的话，说明x是y的子集

1

(x & y) == x 

6.判断x的二进制数中是否有连续的1，表达式为true的话，说明没有

1

(x & (x >> 1)) == 0

7.判断x的二进制数中，第i位是否是1，从左到右数

1

1 & (x >> i)

8.判断 x 是否只包含一个1，为true说明只包含一个1

1

(x & (x-1)) == 0

9.得出最低位的1位于第几位

1

Integer.bitCount((x & (-x)) - 1)

10.Gosper’s Hack，用于快速寻找含有固定数量个1的子集，题目及视频2397. 被列覆盖的最多行数 - 力扣

1
2
3
4
5
6

int mask = (1<<numSelect) - 1;	// 子集中1的数量固定为numSelect
while(mask < MASK){
    int lb = mask & (-mask);
    int x = mask + lb;
    mask = x | (((mask + lb) ^ mask) / lb) >> 2;
}

题目

LC1494.并行课程

用一个二进制位来表示某门课程是否被上过

LC1815.得到最多新鲜甜甜圈的组数

用多个二进制位来表示购买k个甜甜圈的人数

1681. 最小不兼容性 - 力扣（Leetcode）

一个二进制数来表示一个子集，注意预处理

1659. 最大化网格幸福感 - 力扣（Leetcode）

三进制状压DP，注意预处理

__END__