0Pricing
Competitive Programming Academy · 课时

将位掩码用作微型集合

用整数表示子集

将位掩码用作微型集合 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

将整数作为集合

一个整数就可以代表整个集合：第 i 位为 1，表示元素 i 在集合中。这样可以将子集压缩成一个小巧且快速的值。🎒

空集与全集

数字 0 表示空集，而当最低 n 位全部开启时，该值表示每个元素都存在。

empty = 0
full = (1 << 4) - 1  # 0b1111, four elements

添加元素

要将元素 i 添加到集合中，只需对它对应的位执行 OR。这正是设置一位的操作，现在可以将其理解为与一个元素进行并集运算。

s = 0
s |= (1 << 2)  # add element 2

移除元素

要移除元素 i，请与反转后的对应位进行 AND 运算。该元素会离开集合，而其他元素保持不变。这就是移除一个元素的集合差集操作。

s &= ~(1 << 2)  # remove element 2

测试成员关系

将集合与元素 i 对应的位进行 AND 运算，即可检查元素 i 是否属于集合。非零结果表示它是集合的成员。

if s & (1 << 2):
    print('2 is in the set')

并集与交集

对两个掩码进行 OR 运算得到它们的并集；对它们进行 AND 运算得到交集。整个集合的操作各自只需一条机器指令。

union = a | b
inter = a & b

集合大小就是置位计数

位掩码中的元素数量就是其中置位位的数量。使用 bit_count 即可立即得到集合大小。

size = mask.bit_count()

遍历所有子集

对于 n 个元素，从 0 到 2 的 n 次方减 1 的整数可以枚举每个子集。一个简单的范围循环就能覆盖它们。

for mask in range(1 << n):
    pass  # mask is one subset

快速遍历子掩码

如果只想访问给定掩码的子集，请使用经典的子掩码循环。它会按降序遍历每个子集。

sub = mask
while sub:
    sub = (sub - 1) & mask

位掩码 DP 的应用场景

位掩码是许多DP 问题的状态表示，例如旅行商问题，其中掩码记录您已经访问过哪些节点。

让 n 保持较小

由于有 2 的 n 次方个子集，这种技巧只有在 n 较小时才实用，通常最多约为 20。超过这个范围后，数量会急剧膨胀。⚠️

快速检查

最后一道关于将集合表示为掩码的问题。

回顾：位掩码集合

您可以将集合存储在一个整数中，使用掩码添加和移除元素，并遍历每个子集。这为快速的位掩码 DP 打开了大门。🎉

常见问题解答

「将位掩码用作微型集合」课时是免费的吗？

是的 — 「将位掩码用作微型集合」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「将位掩码用作微型集合」这节课中我会学到什么？

用整数表示子集 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「将位掩码用作微型集合」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. AND、OR、XOR 与移位
  2. 设置、清除与翻转位
  3. 统计位数与最低位的置位
  4. 将位掩码用作微型集合
← 返回 Competitive Programming Academy