位运算及状压DP

位运算

简介

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

比赛题目中出现的位运算基本有 5 种，分别为按位与、按位或、按位异或、左移和右移。

与、或、异或

这三者都是两数间的运算。

它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

举例：
10 = ( 1010 ) 2 12 = ( 1100 ) 2 10 & 12 = ( 1000 ) 2 = 8 10 ∣ 12 = ( 1110 ) 2 = 14 10 ⊕ 12 = ( 0110 ) 2 = 6 \begin{aligned} 10 &= (1010)_2 \\ 12 &= (1100)_2 \\ 10 \ \& \ 12 &= (1000)_2 = 8 \\ 10 \ | \ 12 &= (1110)_2 = 14 \\ 10 \oplus 12 &= (0110)_2 = 6 \\ \end{aligned}101210&1210∣1210⊕12​=(1010)2​=(1100)2​=(1000)2​=8=(1110)2​=14=(0110)2​=6​
对应的 C++ 代码验证：

#include<iostream>usingnamespacestd;intmain(){inta=10;// 二进制 1010intb=12;// 二进制 1100cout<<"10 & 12 = "<<(a&b)<<endl;// 输出 8cout<<"10 | 12 = "<<(a|b)<<endl;// 输出 14cout<<"10 ^ 12 = "<<(a^b)<<endl;// 输出 6return0;}

左移和右移

num << i表示将 𝑛𝑢𝑚 的二进制表示向左移动 𝑖 位所得的值。

num >> i表示将 𝑛𝑢𝑚 的二进制表示向右移动 𝑖 位所得的值。

举例：
9 = ( 00001001 ) 2 9 ≪ 2 = ( 00100100 ) 2 = 36 9 ≫ 2 = ( 00000010 ) 2 = 2 \begin{aligned} 9 &= (00001001)_2 \\ 9 \ll 2 &= (00100100)_2 = 36 \\ 9 \gg 2 &= (00000010)_2 = 2 \end{aligned}99≪29≫2​=(00001001)2​=(00100100)2​=36=(00000010)2​=2​
移位运算中如果出现如下情况，则其行为未定义：

1. 右操作数（即移位数）为负值；
2. 右操作数大于等于左操作数的位数；

例如，对于int类型的变量a，a<<-1和a<<32都是未定义的。

对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。对一个负数执行左移操作也未定义。

对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。

关于优先级

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。

常见应用

位运算一般有三种作用：

1. 高效地进行某些运算，代替其它低效的方式。
2. 表示集合（常用于状压DP）。
3. 题目本来就要求进行位运算。

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像「乘 2 的非负整数次幂」和「除以 2 的非负整数次幂」就最好使用位运算，因为此时使用位运算可以优化复杂度。）

内置函数

GCC 中还有一些用于位运算的内建函数：

1. int __builtin_ffs(int x)：返回 𝑥 的二进制末尾最后一个 1 的位置，位置的编号从 1 开始（最低位编号为 1 ）。当 𝑥 为 0 时返回 0 。
2. int __builtin_clz(unsigned int x)：返回 𝑥 的二进制的前导 0 的个数。当 𝑥 为 0 时，结果未定义。
3. int __builtin_ctz(unsigned int x)：返回 𝑥 的二进制末尾连续 0 的个数。当 𝑥 为 0 时，结果未定义。
4. int __builtin_clrsb(int x)：当 𝑥 的符号位为 0 时返回 𝑥 的二进制的前导 0 的个数减一，否则返回 𝑥 的二进制的前导 1 的个数减一。
5. int __builtin_popcount(unsigned int x)：返回 𝑥 的二进制中 1 的个数。
6. int __builtin_parity(unsigned int x)：判断 𝑥 的二进制中 1 的个数的奇偶性。

由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。

状压DP

简介

状压 DP 是动态规划的一种，通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的。

为了达到更低的时间复杂度，通常需要寻找更低状态数的状态。大部分题目中会利用二元状态，用 𝑛 位二进制数表示 𝑛 个独立二元状态的情况。

核心

用一个N位的二进制数，每一位表示一个物品，0/1表示不同的状态。因此可以用0 → 2^(N − 1)(N二 进 制 对 应 的 十 进 制 数 ）中的所有数来枚举全部的状态。

练习题

[蓝桥杯 2019 省 A] 糖果
不难看出，此题不是爆搜就是动态规划，而爆搜需要考虑每一种搭配情况，复杂度O ( 2 n ) O(2^n)O(2n)肯定超时。

考虑动态规划，可以发现数据范围很小，并且是搭配类型的，想到状压。

首先设计状态，一共可以设计出两种：

• d p [ i ] dp[i]dp[i]表示取状态为i ii的几包糖，最多可以凑出的口味数量。这种状态比较麻烦，且结果不是很容易得出。
• d p [ i ] dp[i]dp[i]表示凑出状态为i ii的口味最少需要几包糖。

很显然第二种很合理，那么我们来推一下方程。

思考发现，如果直接枚举i ii，再找合理的上一种状态，不是很好找。但我们可以通过已经求出来的一种状态，配合另一种状态，来更新新的状态。

设v [ i ] v[i]v[i]表示第i ii包糖的口味状态，则有：

d p [ i ∣ v [ j ] ] = min ⁡ ( d p [ i ∣ v [ j ] ] , d p [ i ] + 1 ) dp[i|v[j]] = \min(dp[i|v[j]], dp[i] + 1)dp[i∣v[j]]=min(dp[i∣v[j]],dp[i]+1)

d p [ i ∣ v [ i ] ] dp[i|v[i]]dp[i∣v[i]]为更新的新状态，i ii为已知的状态 1，再找一包糖j jj，更新出d p [ i ∣ v [ i ] ] dp[i|v[i]]dp[i∣v[i]]。

考虑正确性，因为i ii状态从 0 开始枚举，因此枚举到i ∣ v [ i ] i|v[i]i∣v[i]时肯定已经求出d p [ i ] dp[i]dp[i]的值，并且是最优的。还有一个问题是否可能重复选了某包糖，如果是，那么肯定这个值不是最优的，因为你买两包同样的糖和只买一包口味不会有新的。

#include<bits/stdc++.h>usingnamespacestd;constintN=110,M=22;intn,m,k,v[N],dp[1<<M];voidsolve(){cin>>n>>m>>k;for(inti=0;i<(1<<m);i++){dp[i]=1e9;}for(inti=1;i<=n;i++){intstate=0;for(intj=1;j<=k;j++){intx;cin>>x;x--;state|=(1<<x);}v[i]=state;dp[state]=1;}for(inti=0;i<(1<<m);i++){for(intj=1;j<=n;j++){dp[i|v[j]]=min(dp[i|v[j]],dp[i]+1);}}cout<<(dp[(1<<m)-1]==1e9?-1:dp[(1<<m)-1])<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT=1;// cin>>T;while(T--)solve();return0;}