Bitset是啥
某种神奇的容器，用于存储二进制。头文件：
#include<bitset>
定义方法：
bitset<5> Bit1("10011");
bitset<5> Bit2(4);
“<>” 中的内容代表容器的长度，相当于一个数组，但是每一位只能存储
0
0
0 或
1
1
1，所以每一位占用
1
1
1 bit 的内存。赋值方法分两种，一种像字符串一样的，会直接把这一串数字存入。一种是填入一个数值，会把这个数转成二进制存储。
喜欢作的人（比如说我）肯定会问：
那么如果我存的数超过了设定的位数会怎么样？
这个时候，我们发现两种复制方法用了不同的方式处理。第一种取了最左边的
5
5
5 位，第二种取了最右边的
5
5
5 位。但是它们都不会报错。补充一下如果存入的位数不足，会用前导零填充。
如果我输入了一个非
0
/
1
0/1
0/1 的串，会怎么样？
bitset<5> Bit1("534");
这么玩的话会报错。
Bitset的运用
我们再来玩点花的。首先要讲解一下数组用法，数组是从最右侧开始的。
bitset<5> Bit1;
Bit1[0]=1;
此时 Bit1 里面是 00001。
接下来就逐渐神奇了，先拿出一道很简单的题。
给你
n
n
n 种硬币，面值分别是
a
i
a_i
ai，每种硬币有
c
i
c_i
ci 个，问你买一个价值为
m
m
m 的物品，能否在不找零的情况下购买？
首先想到背包，用
d
p
i
,
j
dp_{i,j}
dpi,j 表示用到了第
i
i
i 种硬币，能否凑出价值为
j
j
j 的钱。由于内存可能会不够，所以我们压掉一维，但注意这里的循环要倒过来。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],c[105];
bool dp[100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i]>>c[i];
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=c[i];j++)
for(int k=m;k>=a[i];k--)
dp[k]|=dp[k-a[i]];
cout<<dp[m]<<endl;
return 0;
}
可是这跟 bitset 有啥关系？注意到
d
p
dp
dp 里的值都是
0
/
1
0/1
0/1，可以直接变成 bitset，这样还能省掉循环。
首先我们先分析一下这些
1
1
1 是从哪里来的。假设当前硬币面值为
6
6
6，有两种情况，一种是从上面对应的位置继承（不使用这个硬币），一种是从往前数第
6
6
6 个位置继承（使用这个硬币）。如果我们把第一行的 1101000100010 存入 bitset，称为 bit1，那么第二行的 bit2 就是原本的 bit1 按位或 bit1>>6。bit1>>6 就将原本的位置
3
3
3 移到了位置
6
6
6，是正确的。而且此时所有操作是同时做的，不用担心要倒着循环。关键是，它特别适合卡常，在一个长度为
n
n
n 的 bitset 上进行操作只需要
n
32
\frac{n}{32}
32n 的时间复杂度。好了，先写程序练手吧。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],c[105];
bitset<15> dp;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i]>>c[i];
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=c[i];j++)
dp=dp|(dp<<a[i]);
cout<<dp[m]<<endl;
return 0;
}
如果你真的按照上述写就完了，注意 bitset 的数组是倒着存的，所以应当是 <<a[i]。
第二种运用后续更新哦。