企业官网建设流程全解析

前几天整理提交记录时又翻到了 UVa 12447 Pieces and Bits 这道题。说实话，这道题在 UVa 题库里不算热门，甚至有些冷门，但如果你在练状态压缩 DP 和位运算，它绝对是一块很好的磨刀石。名字里又是 Pieces 又是 Bits，乍一看像一道字符串或者大数题，实际上题面绕来绕去，核心就是一个 bitmask 覆盖 DP。当年我刷这道题的时候，第一眼差点被名字骗过去，后来把模型理清楚之后才发现，里面值得讲的东西比想象中多很多。

如果你现在正准备 ICPC 区域赛、或者刚学完基础 DP 想往状态压缩方向进阶，我建议你别急着去啃那些动辄 2^n 个状态的论文题，先把这道题吃透。它能让你真正理解三件事：为什么用 bit 表示集合、怎么用位运算快速枚举子集、以及状态转移顺序为什么不能乱来。文章最后我还会拿一道近期总被一起讨论的 UVa 11742 Social Constraints 做对照练习，两道题一个用“覆盖”一个用“排列”，正好把位运算的两个典型场景都覆盖掉。

1. 先把 Pieces and Bits 这道题讲清楚

1.1 题目到底在求什么

UVa 12447 的原文描述比较绕，不同来源对细节的表述也有差异。我练习时习惯把题面简化成一个等价模型，思路完全不受影响。题目给了 n 个碎片（Pieces），每个碎片有一个代价 cost，以及一个二进制掩码 cover。这个掩码里的每一位 1 代表这个碎片能“覆盖”一个比特位（Bits）。现在给你一个目标掩码 target，你要从这些碎片里选出若干块，把它们覆盖的位全部合并起来，使得最终结果包含 target 的所有 1 位。问最小总代价是多少。

这里我按最常见的一个版本来处理：碎片可以重复选择。也就是说商店里每块碎片无限量供应，你可以反复买同一块。这个假设会直接影响 DP 状态设计，后面你会看到为什么它能让代码简洁很多。如果你手里的题目版本要求每块碎片只能用一次，本质就变成了集合覆盖问题，状态要增加一维或者直接搜索，但位运算的基本功依然完全适用。先把这个可重复版本吃透，再去处理不可重复的变体要容易得多。

1.2 为什么一组 bit 能压缩成一个整数

状态压缩最核心的思想，就是用整数表示集合。假设一共有 m 个 bit 位，那么一个二进制数 mask 就代表一个集合：如果 mask 的第 i 位是 1，说明这个集合包含了第 i 个元素。两个集合做并集，对应位运算就是按位或 mask1 | mask2；交集就是按位与 mask1 & mask2；判断 A 是不是 B 的子集，只需要检查 (A & B) == A。

生活里很好找类比。你可以把 m 个 bit 看成一条公交线路上的 m 个站点，每个碎片是一辆公交车，cover 这个掩码就是这辆车停靠的站点列表。选择若干辆车之后，问哪些站点被至少停过一次，这就是把所有 cover 做按位或。操作单独一辆车时，你不需要关心它内部的具体路线有多复杂，只需要知道它覆盖了哪些站点，这张“站点表”塞进一个 int 里就能带来带去。这就是状态压缩最大的价值：一个看起来规模很大的“哪些位置被覆盖了”的问题，变成一个不超过 2^m 的整数状态空间。

1.3 设计 DP 状态：为什么是 dp[mask]

搞清楚题目模型之后，第一个要回答的问题是：DP 状态里存什么？我见过很多人第一反应是 dp[i][mask]，表示“考虑了前 i 个碎片，覆盖状态为 mask 的最优代价”。这个状态不是不能用，但既然碎片可以重复选，考虑前 i 个碎片这个维度其实是多余的。真正能影响后续决策的，只有你当前已经覆盖了哪些 bit，以及你已经花了多少钱。至于这些位是来自哪一块碎片、碎片出现过几次，都不重要。

所以状态只需要一维：dp[mask] 表示“覆盖状态恰好为 mask（允许有多余覆盖）时的最小总代价”。初始状态 dp[0] = 0，表示一张碎片都没买，一个位都没有覆盖。最终答案也不是 dp[target]，而是所有满足 condition 的超集状态里的最小值，因为允许碎片覆盖到 target 之外的位。这个点很关键，后面会专门拿出来讲。

2. 位运算与子集枚举：吃透这几个操作就够用了

2.1 OR 状态转移的单调性

状态压缩 DP 里最容易被忽视、却最影响正确性的一个性质是：按位或操作只会增加 1 位，永远不会把已有的 1 变成 0。给定一个当前覆盖状态 mask，加入一块碎片 cover[i] 之后，新状态 nxt = mask | cover[i]，这个 nxt 一定满足 nxt >= mask（按数值大小比较）。

为什么数值上一定不会变小？因为 nxt 的每一个二进制位都至少和 mask 一样，最高非零位不可能比 mask 低，所以 nxt 作为整数一定不小于 mask。这个性质决定了刷表法可以安全地按照 mask 从小到大进行：每个状态的前驱状态数值上都小于等于它，因此处理到当前 mask 时，它的最优值已经确定，不会再被后面更大的状态回头更新。这也是很多位运算 DP 能放心写一重循环的原因。

这个单调性还有个实际好处：如果 cover[i] 是当前 mask 的一个子集，那么 nxt == mask，说明买这块碎片不会带来任何新覆盖。这种更新虽然没有改变状态，但可能用更低代价刷新同一个状态，对于求最小值来说是有意义的，代码里不需要特判，只要用 min 更新即可。

2.2 枚举子集的标准写法

位运算 DP 里有一个高频操作：给定一个掩码 mask，枚举它的所有子集。最常见也最漂亮的写法是这个：

for (int sub = mask; ; sub = (sub - 1) & mask) { // 处理 sub if (sub == 0) break; }

这行代码的精妙之处在于：(sub - 1) 会把最低位的 1 变成 0，同时把右边所有 0 变成 1，再按位与 mask 之后，正好保留了属于 mask 的部分。于是 sub 会按二进制从大到小不重不漏地扫过 mask 的每一个子集，最后停在 0。因为 sub 和 mask 的与操作保证了下一次枚举一定还是 mask 的子集。

举个例子，mask = 0b1011（十进制 11），这个循环会依次得到：1011、1010、1001、1000、0011、0010、0001、0000，一共 8 个子集，全部覆盖。特别注意：空集 0 也是子集，循环体里要单独处理它的逻辑，不能在进入循环前直接 break，否则会把空集漏掉。

枚举单个二进制位是另一组常用操作。取最低位的 1：int lb = x & (-x)。去掉最低位的 1：x &= x - 1。配合 __builtin_ctz(x) 可以拿到最低位 1 的位置。这三个组合起来，就是遍历集合中每个元素的固定套路。在第五章的 UVa 11742 里我们还会再用到它，到时你就能发现，原来“枚举一个集合里还有哪些人”和“枚举 mask 的所有子集”背后是同一套思路。

2.3 刷表法和填表法的取舍

状态转移有两种写法：填表法是枚举所有可能的前驱状态，计算当前状态 dp[mask]；刷表法是知道了当前状态 dp[mask]，直接把它向后推，更新所有能到达的后继状态。本题我更推荐刷表法。

原因有两条：第一，当前状态 mask 的转移目标 nxt = mask | cover[i]，这个目标非常明确，遍历一遍每种碎片就能全部计算出来；反过来填表的话，你要枚举 mask 的子集，然后判断哪些碎片能让子集变成 mask，逻辑会绕很多。第二，若使用填表法，很容易不自觉地把“可重复选择”写成 0/1 背包。刷表法从 dp[mask] 直接推 dp[nxt]，天然允许同一个碎片被反复加入，完全符合题意。当然，刷表法也有代价：外层循环需要访问那些暂时还不是最优值的状态。但因为 OR 操作是单调的，我们从小到大刷表时，dp[mask] 在最坏情况下会被多次更新，不过最终一轮循环结束时所有值都会收敛到正确结果，复杂度仍然是 O(2^m * n)。

3. 从暴力到正解：完整实现与复杂度解析

3.1 暴力枚举组合为什么活不下去

拿到这种题，第一反应往往是枚举所有碎片的组合，算每个组合的并集和总代价。也就是用一个整数 s 表示选了哪些碎片，s 的范围是 0 到 2^n - 1，然后对每个 s 求并集。

int ans = INF; for (int s = 0; s < (1 << n); s++) { int curMask = 0, curCost = 0; for (int i = 0; i < n; i++) if (s >> i & 1) { curMask |= cover[i]; curCost += cost[i]; } if ((curMask & target) == target) ans = min(ans, curCost); }

这段代码在 n = 10 的时候跑得飞快，但 n = 25 的时候光枚举组合就是 3355 万次，再乘内层 n，已经到 8 亿级别，基本必死。就算加一点剪枝，也不值得赌数据。更关键的是，这个做法完全没有利用题目的重复可选特性，也没有把“覆盖了哪些 bit”这个核心状态提炼出来，换个数据范围稍大的变式就完全站不住。位运算 DP 的思路不是“枚举所有选择”，而是“把覆盖结果本身当作状态”，把问题规模从 2^n 降到了 2^m。当 m 只有 16 或者 20 时，2^m 就是几十万到一百万级别，这才是正解的复杂度来源。

3.2 DP 主代码

下面是完整实现，使用刷表法，碎片可以重复选择。如果用 C++17 提交，代码可以直接跑；老一点的 OJ 编译器不支持 C++17，把 vector 和循环写法往下挪到 C++11 也没问题。

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int main() { int n, m; cin >> n >> m; vector<int> cost(n), cover(n); for (int i = 0; i < n; i++) { cin >> cost[i] >> cover[i]; } int target; cin >> target; int total = 1 << m; vector<int> dp(total, INF); dp[0] = 0; for (int mask = 0; mask < total; mask++) { if (dp[mask] == INF) continue; for (int i = 0; i < n; i++) { int nxt = mask | cover[i]; dp[nxt] = min(dp[nxt], dp[mask] + cost[i]); } } int ans = INF; int rest = (total - 1) ^ target; for (int sub = rest; ; sub = (sub - 1) & rest) { int mask = target | sub; ans = min(ans, dp[mask]); if (sub == 0) break; } if (ans == INF) cout << "impossible" << endl; else cout << ans << endl; return 0; }

最后统计答案那一段，感兴趣的读者可以仔细品味一下。rest 是 target 的全集补集，也就是那些不在 target 里的、可以被额外覆盖的位。枚举 rest 的每个子集 sub，把它和 target 合并起来，就得到了 target 的每一个超集。这样遍历所有超集比直接从 target 到 total 一个个扫要精准得多，也顺便复习了一次子集枚举写法。如果 m 很小，直接用 for (int mask = target; mask < total; mask++) 加判断也是没问题的，但在 m 偏大时，超集枚举能帮你省掉很多无效状态的访问。

3.3 复杂度分析与边界测试

这个 DP 的时间复杂度是 O(2^m * n)，空间复杂度是 O(2^m)。m = 20 时，状态数大约 104 万，乘以 n 就算多一点，也就两三千万次循环，C++ 在 OJ 上轻松跑完。关键是这个复杂度只和 m 有关，不再担心 n 变成 30 或者 40。

提交之前一定要测几个边界数据。第一组：目标本身是 0。如果 target = 0，任何碎片都不需要买，答案直接是 0。代码里 rest = total - 1，枚举所有超集时会算到 dp[0]，所以答案正确，但初学者很容易在这里被卡掉。第二组：两块碎片分别覆盖 target 的一半，比如 target = 3，一块 cover = 1 cost = 5，另一块 cover = 2 cost = 4，正确答案是 9。第三组：一块碎片直接覆盖超集，比如 target = 3，cover = 7 cost = 4，答案应该取 supermask 7 的代价 4，而不是认为 dp[3] 是 INF 就输出 impossible。第四组：覆盖不足，比如 target = 3，但所有碎片 cover 并起来都只有 1，答案应该是 impossible，也就是 INF 分支。

4. 位运算 DP 最常见的几个坑

4.1 运算符优先级和整数溢出

位运算的优先级常年坑人。C++ 里 == 的优先级高于 &，所以如果想判断 mask 的第 i 位是否为 1，不能直接写 if (mask & (1 << i) == 0)，因为编译器会先算 (1 << i) == 0，这个表达式几乎永远是 false，然后再做按位与，结果完全不是你想要的意思。正确写法是 if ((mask & (1 << i)) == 0) 或者 if ((mask >> i) & 1)。这种错误编译能通过、运行也不崩，但结果就是玄学，排查起来非常痛苦。

整数溢出是另一个高频雷区。当 m 达到 31 时，1 << m 直接溢出成负数，vector 的大小会变成一个巨大的数然后崩溃。这时候要么把状态总数写成 (1LL << m)，要么在读入数据时直接限制 m <= 25。INF 的取值也要小心，0x3f3f3f3f 大约是 10 亿，两个相加可能超过 int 上限。求最小值时如果用 long long 存 dp，INF 就用 0x3f3f3f3f3f3f3f3f，避免中间值溢出。

4.2 状态更新顺序为什么不能乱

很多 DP 对循环顺序有要求，位运算 DP 也不例外。上一节说了，nxt = mask | cover[i] 一定不小于 mask，所以刷表顺序按 mask 递增是安全的。但如果因为某个优化手段把外层循环改成 mask 递减，那就完蛋了：你可能在处理大状态时，它的更优前驱是从一个尚未处理的小状态推过来的，结果错过正确答案。

还有一类更隐蔽的问题出现在“同层更新”里。由于 cover[i] 可能是 mask 的子集，nxt 可能等于 mask，这时候 dp[mask] 在循环内部被更新。如果你用的是 vector，并且外层还在扫描当前 mask，新的更优值会继续向后推，这其实是正确的，甚至会让答案收敛得更快。但如果你在循环里做了一个“如果 dp[nxt] 已经更优就跳过”的剪枝，就要小心别把本来应该继续扩散的更优路径剪没了。

4.3 答案统计漏掉超集

这是 WA 重灾区。很多人写完转移之后，直接用 ans = dp[target] 作为答案提交，结果样例过了、提交就挂。原因很简单：碎片可能覆盖到 target 之外的位，而这些额外的覆盖不会出现在 dp[target] 里。你要找的不是“恰好覆盖 target”的最小代价，而是“覆盖包含 target”的最小代价。这也解释了为什么我在第 3.2 节里要专门枚举所有超集。你可以写循环扫一遍，也可以用补集子集枚举，但千万不要忘了这一步。

5. 用一道热题 11742 对照练习：同一套位运算的另一个战场

5.1 Social Constraints 在做什么

UVa 11742 Social Constraints 最近经常和 12447 放在一起讨论。题面是这样的：有 n 个人要坐成一排，编号从 0 到 n-1，另外给若干条约束，每条约束是一个三元组 (a, b, c)，表示 a 和 b 之间必须恰好隔 c 个人（按最常见的题目表述，c + 1 就是他们的座位距离差）。问有多少种排列方式满足所有约束。这道题 n 最大只有 8，很多人直接全排列暴力检查就过了，但正是这种小规模题最适合拿来练“用位运算表示集合”的思路。

它和 12447 最大的区别在于：12447 关心的是“选了哪些碎片合在一起”，本质是组合问题；11742 关心的是“按什么顺序把人放进去”，本质是排列问题。但两者都可以用二进制掩码刻画集合状态，区别只在于掩码的语义是“已覆盖的位”还是“已安排的人”。理解了这一点，以后遇到任何带约束的排列题，你都会下意识先想想能不能用 mask 表达“已决策的子集”。

5.2 回溯代码与位运算优化

11742 因为 n 太小，直接用 DFS 回溯所有排列是最稳的。但回溯枚举下一个人时也可以用位运算写得非常优雅。fullMask = (1 << n) - 1 表示所有人，usedMask 表示已经安排坐下的人，那么还没有安排的人就是 int left = fullMask ^ usedMask。接下来只要不停从 left 里取出最低位、去掉最低位，就能枚举出所有还没坐下的人，完全不需要开一个 bool 数组。

#include <bits/stdc++.h> using namespace std; int n, ans; vector<tuple<int,int,int>> cons; int pos[10]; bool ok() { for (auto &e : cons) { int a, b, c; tie(a, b, c) = e; if (abs(pos[a] - pos[b]) != c + 1) return false; } return true; } void dfs(int idx, int usedMask) { if (idx == n) { if (ok()) ans++; return; } int left = ((1 << n) - 1) ^ usedMask; while (left) { int p = __builtin_ctz(left); left &= left - 1; pos[p] = idx; dfs(idx + 1, usedMask | (1 << p)); } }

这段代码里 left &= left - 1 和 12447 里 sub = (sub - 1) & mask 是同源操作，都是在枚举一个集合中的元素。不同之处在于：12447 是枚举一个掩码的所有子集，11742 是枚举一个集合的所有元素。这是位运算入门必须掌握的两类枚举，放在一起练能明显加深印象。注意如果你在旧 OJ 上提交，C++11 可能不支持直接读 tuple 结构化绑定，代码里我用了 tie 来兼容。

5.3 两题连刷的节奏建议

我建议的练习顺序是：先把 12447 的 DP 独立写出来，提交通过之后，不要马上换题，而是自己改几个条件，比如把“可重复选择”改成“每块只能用一次”，看看状态设计要怎么变；然后再去写 11742 的暴力回溯，并试着把所有数组判断都改成位运算判断。两题都过掉之后，你对 bitmask 的敏感度会有一个肉眼可见的提升。我当年就是连续刷了几道类似题目之后，才开始真正觉得“状态压缩”不过如此。

最后分享一个我个人提交前必做的动作：构造一组极端的边界数据，比如目标位全 1、所有碎片都只能覆盖一位、以及 target 为 0 的情况，全部跑一遍再提交。这个习惯帮我省了很多次无意义的 WA，也让我对状态空间的理解更扎实。算法竞赛里，WA 不可怕，可怕的是你连为什么 WA 都猜不到，而位运算相关题恰恰是最容易让人“猜不到”的那一类。希望这篇文章能帮你少走一点弯路。