状态压缩详细讲解
状态压缩是用二进制位表示状态，用位运算操作状态的算法技巧，核心是把复杂的集合/状态，压缩成一个整数（二进制），用极快的位运算替代循环/递归处理状态，是竞赛、面试（动态规划、DFS）的高频考点。
一、为什么需要状态压缩？
先看一个经典场景：
> 有 nnn 个物品（n≤20n \le 20n≤20），每个物品有选/不选两种状态，要记录哪些物品被选中。
* 普通做法：用数组 bool vis[20] 记录，判断、修改都要循环遍历
* 状态压缩：用一个整数表示，比如 5（二进制 101）代表第0、2个物品被选
优势：
1. 状态存储省空间（一个整数存下所有状态）
2. 位运算速度是 O(1)O(1)O(1)
3. 适配动态规划的状态定义（dp[状态]）
不同情况下状态压缩的时间复杂度都比较大，因此建议数据 ≤20\le 20≤20时使用（也得分情况考虑）
适用场景：小范围状态枚举（n≤30n \le 30n≤30 用 int，n≤60n \le 60n≤60 用long long）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、前置知识：必须掌握的位运算
状态压缩的所有操作，都基于这6种核心位运算，熟记符号、含义、用法：
运算 符号 规则 状态压缩中的作用 按位与 & 同为1才为1 判断位、保留位 按位或 | 有1就为1 设置位、合并状态 按位异或 ^ 相同为0，不同为1 翻转位 左移 << 整体左移，右侧补0 构造第k位的掩码 右移 >> 整体右移，左侧补0 获取第k位的值 按位取反 ~ 0变1，1变0 清空指定位
构造「掩码」（最基础操作）
掩码：只有第k位是1，其余都是0的二进制数，用于定位操作某一位。
注意：位运算下标从0开始（和数组一致）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、状态压缩的5个核心操作
假设：
* state：压缩后的状态整数
* k：要操作的第k位（从0开始）
1. 判断第K位是否为1
原理：与掩码做与运算，结果非0 → 该位为1。
2. 将第K位设为1
原理：或运算有1置1，不影响其他位。
3. 将第K位设为0
原理：掩码取反后，第k位是0，其余是1，与运算后清空第k位。
4. 翻转第K位（0变1，1变0）
原理：异或运算相同为0，不同为1。
5. 统计状态中1的个数（选中的数量）
作用：快速知道有多少个物品被选中、多少个城市被访问过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、状态枚举：遍历所有可能的状态
当有n个元素时，总状态数 = 2ⁿ（每个元素0/1）。
遍历所有状态的模板：
* state=0 → 全0（都不选）
* state=(1<<n)-1 → 全1（都选）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、实战：3个经典案例（由浅入深）
案例1：子集枚举（打印N个元素的所有子集）
需求：n=3，元素{a,b,c}，用状态压缩打印所有子集。
输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
案例2：旅行商问题（TSP，状态压缩DP）
这是状态压缩最经典的应用：
> 有n个城市，从城市0出发，遍历所有城市恰好一次，求最短路径（n≤20）。
思路
1. 状态定义：dp[state][u]
* state：压缩的已访问城市集合（二进制第k位=1表示访问过城市k）
* u：当前所在城市
* 含义：访问完state中的城市，且停在u的最短路径
2. 初始状态：dp[1<<0][0] = 0（只访问城市0，在城市0，距离0）
3. 转移方程：
从城市u走到未访问的城市v：
dp[state | (1<<v)][v] = min(dp[state | (1<<v)][v], dp[state][u] + cost[u][v])
4. 答案：dp[(1<<n)-1][u]（遍历所有城市，停在任意u的最小值）
核心代码模板
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
案例3：集合判断（A是B的子集？）
* A是B的子集：(A & B) == A
* A和B无交集：(A & B) == 0
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、状态压缩核心规则与技巧
1. 核心规则
1. 下标从0开始：位运算默认第0位对应第一个元素
2. 状态范围：0≤state<(1<<n)0 ≤ state < (1 << n)0≤state<(1<<n)
3. 数据类型：
* n ≤ 20 → int（32位足够）
* 20 < n ≤ 30 → long long（64位）
4. 时间复杂度：O(n·2ⁿ)，n=20时 20*1e6=2e7，完全能跑过
2. 高频技巧
1. 去掉最低位的1：state & (state - 1)
例：6(110) & 5(101) = 4(100)
2. 获取最低位的1：state & -state
例：6(110) & -6 = 2(010)
3. 全1状态：(1 << n) - 1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、常见误区
1. 下标搞错：把第1位当成第一个元素（必须从0开始）
2. 数据溢出：n>20还用int（必须换long long）
3. 初始化错误：DP数组没初始化为无穷大，导致结果错误
4. 状态遍历顺序错：必须从小到大遍历状态（依赖前序状态）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
1. 状态压缩 = 二进制表示状态 + 位运算操作状态，专门解决小规模状态枚举问题
2. 5个核心操作：判断、置1、置0、翻转、统计1的个数
3. 核心应用：子集枚举、状态压缩DP（TSP、棋盘DP）
4. 关键：位运算下标从0开始，状态范围0~(1<<n)-1
而且，状态压缩是 GESP 7级 爱考的知识点！
