1. 最核心的一行
cpp
p |= (p << x);
它表示：
text
不选 x 的状态
∪
选 x 的状态
也就是：
text
原来的可达和
∪
原来的可达和全部加 x
2. 表示什么
cpp
bitset<100> p;
把它看成一个布尔数组：
text
p[0], p[1], p[2], ...
规定：
cpp
p[i] = 1;
表示：
和 可以被凑出来。
例如：
cpp
p[0] = 1;
p[3] = 1;
p[7] = 1;
表示当前可以得到：
text
{0, 3, 7}
所以， 可以直接看成：
text
所有为 1 的下标组成的集合
3. 左移到底是什么
假设：
text
p = {0, 3, 7}
执行：
cpp
p << 2
原来的每个下标都加 ：
text
0 → 2
3 → 5
7 → 9
所以：
text
p << 2 = {2, 5, 9}
主线：
text
原位置 s
→ 左移 x
→ 新位置 s+x
站在目标位置 看：
cpp
(p << x)[i] = p[i-x];
因此两种说法是同一件事：
text
原状态向后移动 x
目标状态从 i-x 转移过来
4. 为什么能表示背包
假设当前：
text
p = {0, 2}
现在加入数字：
text
x = 3
不选 ：
text
{0, 2}
选择 ：
text
{0+3, 2+3}
=
{3, 5}
也就是：
cpp
p << 3
最后合并：
text
{0, 2} ∪ {3, 5}
=
{0, 2, 3, 5}
代码：
cpp
p |= (p << 3);
5. 完整例子
数字为：
text
2, 3
代码：
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
bitset<20> p;
p[0] = 1;
p |= (p << 2);
p |= (p << 3);
for (int i = 0; i < 20; i++) {
if (p[i]) {
cout << i << ' ';
}
}
}
输出：
text
0 2 3 5
过程：
text
开始： {0}
加入 2： {0} ∪ {2}
= {0, 2}
加入 3： {0, 2} ∪ {3, 5}
= {0, 2, 3, 5}
6. 它等价于什么循环
普通 01 背包：
cpp
for (int s = MAX_SUM; s >= x; s--) {
if (p[s-x]) {
p[s] = 1;
}
}
使用 ：
cpp
p |= (p << x);
二者完全对应：
text
普通循环：逐个移动状态
bitset：整体移动状态
7. 为什么是或，不是异或
假设：
text
p = {0, 2}
x = 2
那么：
text
p = {0, 2}
p << 2 = {2, 4}
正确答案应该是并集：
text
{0, 2, 4}
所以使用：
cpp
p | (p << 2)
不能使用异或：
cpp
p ^ (p << 2)
因为位置 同时出现：
text
1 ^ 1 = 0
异或会错误地把 删除。
主线：
text
能通过任意一种方式得到
→ 保留
→ 使用 |
而异或表示：
text
只能通过其中一种方式得到
不是背包需要的含义。
8. 常用运算
并集
cpp
A | B
表示：
text
在 A 中或在 B 中
交集
cpp
A & B
表示：
text
同时在 A 和 B 中
例如判断是否存在两个数相差 ：
cpp
if (((p << x) & p).any()) {
cout << "存在";
}
异或
cpp
A ^ B
表示：
text
只出现在其中一个集合中
同时出现的位会被删除。
左移
cpp
p << x
表示：
text
所有下标加 x
右移
cpp
p >> x
表示：
text
所有下标减 x
统计状态数量
cpp
p.count()
是否存在状态
cpp
p.any()
是否为空
cpp
p.none()
9. 和 不一样
cpp
p << x
只生成移动后的结果，不修改 。
cpp
p <<= x
直接修改 ，原状态会丢失。
背包要保留“不选”的情况，所以写：
cpp
p |= (p << x);
不能只写：
cpp
p <<= x;
10. 固定模板
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_SUM = 2000000;
bitset<MAX_SUM + 1> p;
int main() {
int n;
cin >> n;
p[0] = 1;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
p |= (p << x);
}
cout << p.count() << '\n';
}
如果不想统计空集合对应的和 ：
cpp
cout << p.count() - 1 << '\n';
11. 注意范围
cpp
bitset<100> p;
只能保存下标：
text
0 ~ 99
如果：
text
某一位左移后超过 99
它会直接消失。
因此背包中要保证：
cpp
bitset<最大可能总和 + 1>
12. 最终理解
text
bitset
→ 一整排 0/1 状态
→ 为 1 的下标组成集合
text
p << x
→ 所有下标加 x
→ 所有可达和加 x
text
p | (p << x)
→ 原集合 ∪ 平移后的集合
→ 不选 x ∪ 选择 x
所以：
cpp
p |= (p << x);
本质就是：
text
状态集合
→ 整体平移
→ 合并
评论