民科心中的物理1. 状态压缩与枚举技术概述
在信息学奥林匹克竞赛（CSP/NOI）的赛场上，状态压缩（State Compression）配合枚举（Enumeration）是一对黄金组合。这种技术特别适合处理那些看似需要穷举所有可能性，但实际上可以通过巧妙的状态表示来大幅降低计算复杂度的问题。
我第一次接触状压DP是在解决一个经典的棋盘覆盖问题时。当时用传统的深度优先搜索方法，当棋盘尺寸达到8x8时就完全无法在合理时间内得出结果。而改用状态压缩后，同样的问题在16x16的棋盘上都能轻松应对。这种从"完全不可行"到"轻松解决"的转变，让我深刻体会到算法优化的重要性。
状态压缩的核心思想是将复杂的状态信息用简单的数据结构（通常是整数）来表示。在C++中，我们通常利用整数的二进制位来记录状态。比如用一个int型变量的每一位表示某个物品是否被选取，或者某个位置是否被占用。这种表示方法不仅节省空间，更重要的是能利用位运算快速进行状态转移和条件判断。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 状态压缩的基础实现
2.1 位运算基础
在C++中实现状态压缩，必须熟练掌握以下位运算操作：
cpp复制// 设置第i位为1
mask |= (1 << i);
// 设置第i位为0
mask &= ~(1 << i);
// 检查第i位是否为1
if (mask & (1 << i)) {
// 第i位是1
}
// 切换第i位的状态
mask ^= (1 << i);
// 获取最低位的1
int lowbit = mask & -mask;
// 统计1的个数（内置函数）
int cnt = __builtin_popcount(mask);
注意：在竞赛中，使用
__builtin_popcount等GCC内置函数通常是被允许的，但在某些严格环境中可能需要自己实现。建议赛前确认比赛规则。
2.2 常见状态表示方法
-
集合表示法：用二进制位表示元素是否在集合中。例如在旅行商问题(TSP)中，可以用一个n位二进制数表示哪些城市已经访问过。
-
棋盘覆盖法：处理棋盘类问题时，可以用每一位表示棋盘上一个格子的状态。比如八皇后问题中，可以用三个整数分别表示列、主对角线和副对角线的占用情况。
-
资源分配法：当需要分配有限资