状压DP/位运算 学习笔记

模板及讲解

状态压缩动态规划就是用于某种时候DP的状态难以表示时,使用二进制进行存储状态的一种动态规划。通常会用位运算进行操作:

位运算

1、对$x$取反:~x
2、$x+1(x为偶数)$:x|1
3、$2^x$:1<<x
4、$2^{-x}$:1>>x
5、$x的对应值$(例如$0$对$1$,$2$对$3$,$8$对$9$):x^1
6、构造0~n-1位二进制数全部为1:(1<<n)-1
7、构造形如10,100,100000即[0, k-1]全部为0,[k,k]为1,这样的二进制数:1<<(k-1)

状压DP常用

1、将a的第k位修改为1:a |= 1<<k;
2、将a的第k位修改为0:a &= ~(1<<k);
3、取第k位:a >> k & 1;
4、判定序列里有没有连续出现的1:a&(a>>1)a&(a<<1)
5、枚举子集:i = (i - 1) & S
6、取最后一个1:i &= (i - 1)
7、lowbit(x) = x & (-x)

三(多)进制状压

Loj 10172

我们相当于把一个整数当做三进制数来看,也就是说$(25)_{10}={221}_3$,我们就维护这个$221$。
我们开一个数组sjc[状态][位]=位上的值 (0, 1, 2),用来找一个状态每一个位上是什么
这个数组可以用十进制转三进制的方法求得,具体看代码。
然后注意本题要特判$k=1,k=n$,并且只有一行的情况。

异或性质

1、$a \oplus a=0$
2、$a \oplus b \oplus c=a \oplus (b \oplus c)$ (右结合律)
3、$a \oplus 0 = a $

异或题:(核心:按位贪心)
1、两个之间的异或值:Trie树 (最大异或和,CF 888G,十二省联考异或粽子)
2、多个之间的异或值:线性基 (Bzoj 4568)

常见题型

------ 本文结束 ------