一、什么时候想到状压
零基础提示：220 ≈ 100 万、224 ≈ 1600 万——指数级看着吓人，但只要 n ≤ 20 再乘个小多项式，总量仍在每秒 10⁸ 次运算的预算内。先学会用数据范围反推复杂度：预备知识 · 复杂度估算。
题目里有一类对象，每个只有"选 / 不选""用过 / 没用过"两种状态，且个数 k ≤ 20 左右——这几乎是在明示状压。用一个 k 位二进制数 S 表示集合：第 i 位为 1 表示第 i 个对象已选。所有可能的集合只有 2k 个（k=20 时约 100 万），可以全部枚举。
生活类比：宿舍 4 人决定谁去倒垃圾，所有方案 2⁴=16 种。用 4 个开关灯表示"谁去"，灯亮=去。枚举所有方案 = 把 0000 到 1111 全部试一遍。计算机枚举二进制数，就像把开关组合全部拨一遍一样自然。
k = 3 时，所有集合只有 8 个
| S（二进制） | 十进制 | 含义 |
|---|---|---|
| 000 | 0 | 一个对象都没选 |
| 001 | 1 | 只选了 0 号 |
| 010 | 2 | 只选了 1 号 |
| 011 | 3 | 选了 0、1 号 |
| … | … | … |
| 111 | 7 | 全部选上 |
必备位运算
| 操作 | 写法 | 含义 |
|---|---|---|
| 判断第 i 位 | S >> i & 1 | 对象 i 是否在集合中 |
| 加入第 i 位 | S | (1 << i) | 把对象 i 放进集合 |
| 去掉第 i 位 | S ^ (1 << i)（已知该位为 1） | 从集合移除 |
| 最低位的 1 | S & -S（lowbit） | 取集合中编号最小元素，常用于枚举 |
| 枚举子集 | for (t = S; t; t = (t-1) & S) | 遍历 S 的所有非空子集，总复杂度 O(3k) |
二、入门模型：TSP 旅行商问题（P1171）
问题：n ≤ 20 个村庄，两两之间距离已知，从 1 号村出发，每个村庄恰好经过一次再回到 1 号村，求最短回路。
f[S][i] = 已经走过的村庄集合为 S、当前停在村庄 i 的最短路程
转移：f[S | 1<<j][j] = min( f[S][i] + dist[i][j] )，其中 j ∉ S
转移：f[S | 1<<j][j] = min( f[S][i] + dist[i][j] )，其中 j ∉ S
- 初始化 f[1][0] = 0（只走过起点；代码中的 0 号村即题目的 1 号村），其余为正无穷。
- 按 S 从小到大枚举，再枚举当前位置 i ∈ S、下一步 j ∉ S 进行转移。
- 答案 = 对所有终点 i 取 f[(1<<n)−1][i] + d[i][0]——别忘了加上返回起点的最后一段。
三、进阶建模：k 个关键点 + 大图 = 状压 × MST
识别信号：图很大（n ≤ 105），但其中"特殊的点"只有 k ≤ 10~16 个，答案与"选哪些特殊点"有关。
- 2k 枚举特殊点的选取子集 S。
- 对每个 S，用多项式算法（最小生成树 Kruskal、最短路 Dijkstra 等）算出该子集下的代价。
- 对所有 S 取最优。总复杂度 2k × (m log m)，k=10 时约 103 × 105 = 可接受。
建模口诀："小的枚举，大的算法"。规模小的维度用暴力枚举吃掉，规模大的部分交给经典多项式算法——这是近年 CSP-S 综合建模题最流行的命题套路。
配套复习：Kruskal 最小生成树
边按权排序 → 并查集逐条合并，两端已连通则跳过，选满 n−1 条边结束。复杂度 O(m log m)，瓶颈在排序。注意：NOI 大纲 2025 修订版删除了"次小生成树"，备考重心放回 MST 本身及其与其他算法的组合。
四、模板代码（TSP 骨架）
const int N = 20, INF = 0x3f3f3f3f;
int f[1 << N][N];
memset(f, 0x3f, sizeof f);
f[1][0] = 0; // 只走过村庄 0
for (int S = 1; S < (1 << n); S++)
for (int i = 0; i < n; i++) if (S >> i & 1)
for (int j = 0; j < n; j++) if (!(S >> j & 1))
f[S | (1 << j)][j] = min(f[S | (1 << j)][j], f[S][i] + d[i][j]);
int ans = INF;
for (int i = 0; i < n; i++) ans = min(ans, f[(1 << n) - 1][i] + d[i][0]); // 回到起点五、易错点清单
1 << i中 i ≥ 31 会溢出：k > 20 的题要用1ll << i或换 long long 状态。- 位运算优先级极低：
S >> i & 1要写(S >> i) & 1，比较时更要加括号。 - f 数组大小 2k × n：k=20 时 f 占 220×20 个 int ≈ 80 MB，注意内存上限，必要时滚动或改 map。
- 枚举子集
t = (t-1) & S的写法包含空集与否要清楚，循环边界别写错。
六、练习
- P1171 售货员的难题（TSP 状压模板）
- bitset 练手：P2709 小 B 的询问（体会位运算压集合）
- 真题对照：CSP-S 2025 T2 道路修复（状压 + MST）、2022 T3 假期计划