bitset入门 学习笔记
2026-08-25 17:48:29
发布于：新疆
26阅读
0回复
0点赞
bitset容器有点类似于vector<bool>，但整体性能远优于vector和bool
它可以有效地优化 背包 的运行效率
此外，bitset也可以直接使用常规位运算符进行操作
bitset<8> a; // 8位，所有位默认值为0
bitset<8> a;
bitset<8> b;
bitset<8> c=a&b; // 按位与
bitset<8> c=a|b; // 按位或
bitset<8> c=a^b; // 按位异或
bitset<8> c=~a; // 取反
bitset<8> c=a<<1; // 左移1位
bitset<8> c=b>>1; // 右移1位
注意细节：初始化时，最右侧字符，会对应bitset的最低位（下标为0的位）
例题.卡片之和（官方题库无此题）
题目描述
小明有 张数字卡片，第 i 张卡片上的数字为 。
对于每次询问，小明可以从这些卡片中任意选择若干张，每张卡片最多选择一次。请判断所选卡片上的数字之和能否恰好等于给定的目标值 。
每次询问相互独立，不会消耗卡片。
特别地，可以一张卡片都不选，因此目标值 一定可以得到。
输入格式
第一行输入一个整数 ，表示数字卡片的数量。
第二行输入 个正整数 ，表示每张卡片上的数。
第三行输入一个整数 ，表示询问次数。
接下来 行，每行输入一个整数 ，表示本次询问的目标值。
输出格式
对于每次询问：
- 如果能够选择若干张卡片，使数字之和恰好为 ，输出
Yes； - 否则输出
No。
每个询问的答案单独占一行。
输入输出样例
输入#1
5
2 3 7 8 10
6
0
5
6
11
14
20
输出#1
Yes
Yes
No
Yes
No
Yes
数据范围
对于全部测试数据：
。
所有输入均为整数。
-
bitset代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N];
bitset<N>dp;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
m=2e5;
dp[0]=1;
for(int i=1;i<=n;i++)dp=dp|(dp<<a[i]);
int q;cin>>q;
while(q--){
int x;cin>>x;
if(dp[x]) cout<<"Yes\n";
else cout<<"No\n";
}
}
-
背包代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,m,a[N],dp[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
m = 2e5;
dp[0] = 1;
for(int i = 1; i <= n; i ++){
for(int j = m; j >= a[i]; j --){
if(dp[j-a[i]]>0) dp[j] = 1;
}
}
int q; cin >>q;
while(q--){
int x; cin >>x;
if(dp[x]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
不喜勿喷~
有帮助，赞一个