std::bitset
前言
感觉 ZGY 讲得不是很清楚(例题讲得有点少,而且感觉有一点乱),所以来写了这一篇文章。但是最好结合着他的文章一起学习。
可能有错别字 错公式 错表达 大佬们请请多包涵 Orz。
点赞 投币 收藏(三连键)。
std::bitset
其实在很多情况下都可以使用,这个容器因为利用状态压缩所以拥有优秀的时间复杂度(常数 \(\dfrac{1}{32}\))和空间复杂度(空间 \(\dfrac{1}{8}\)),所以它可以用来骗分以及过一些奇妙的题目。
有一些是 C++11 的特有函数和语法,本人会用斜体特别标注。
使用方式
定义
在标头 <bitset>
中定义:
template< std::size_t N >
class bitset;
例子:
std::bitset<114514> cjh;//定义一个长度为 114514 的 bool 数组,空间约为 1500 Byte。
需要注意的一点是:长度必须为一个固定的正整数,如需动态可以使用特化的 std::vector<bool>
。
构造
可以使用数字和字符串进行构造。
例子:
std::bitset<8> cjh1(0xff);//二进制位 11111111.
std::bitset<8> cjh2(255);//同上。
std::bitset<8> cjh3("11111111");//字符串构造。
运算符
可以进行比较(==
和 !=
),进行元素访问([]
),进行两个 std::bitset
(有时候也可以是一个整数)之间的按位运算(& | ^ &= |= ^= ~ <<= >>= << >>
)。
使用可以看例题,不过多举例。
函数
元素访问
函数 | 作用 |
---|---|
test |
访问特定位(true or false ,同样可以使用 [] 运算符)。 |
all |
检查是否所有位为 true 。 |
any |
检查是否存在一位为 true 。 |
none |
检查是否没有一位设为 true 。(即均为 false ) |
count |
返回设置为 true 位的数量。 |
容量
函数 | 作用 |
---|---|
size |
返回位集保有的位数。(请注意和 count 进行区分) |
修改器
函数 | 作用 |
---|---|
set |
设置所有位为 true (无需给定参数) 或设置某一位为指定值(需要给定一至二个参数,也可以使用 [] 运算符进行访问赋值)。 |
reset |
设置所有位为 false (无需给定参数) 或设置某一位为 false (需要给定一个参数,也可以使用 [] 运算符进行访问赋值)。 |
filp |
将所有位翻转(也可以通过取反运算符 ~ ),或翻转指定位置(需要给定一个参数)。 |
转换
函数 | 作用 |
---|---|
to_string |
返回数据的字符串表示。 |
to_ulong |
返回数据的 unsigned long 整数(即 \(32\) 位无符号整数)表示。 |
to_ullong (C++11) |
返回数据的 unsigned long long 整数(即 \(64\) 位无符号整数)表示。 |
内置函数
内置函数并不在 C++ 标准中,但是考试时可用。
函数 | 作用 |
---|---|
_Find_first |
找到第一个为 true 的下标。 |
_Find_next |
找到下标为 pos 以后(不含 pos )第一个为 true 的下标。(需要给定一个参数 pos ) |
以上两个函数寻找失败均会返回 std::bitset
的大小。
非成员函数
可以使用 <<
和 >>
进行流输入输出。
例题
下面将用几道例题详细讲述它的用法,可以从中感受到 bitset
的强大。
【正常用法】#930. 烤箱
前言(本来是单独的一篇题解的,这一部分可以不看)
以此篇题解,怀念我初一时期的启蒙教练 KJF,也纪念我水平最为鼎盛的时期。
这是一道很好的动态规划题目,很推荐大家去练习一下。
在去年的时候,我们考试考到了这一题,当时没有一个人做出来了这一道题。
去年的我,因为太弱了,并没有做出来,乱写了一个 DFS,遗憾收场。
从此,我将这道题收藏了起来,而很久都没有看过一眼。
当我再次找出这一道远古题时,已经过去了一年多了。
知道今天,在中午睡觉时,灵机一动就推出来了这一道题。
这证明了 CZC 的一句话:如果一道题你很久都没有做出来,说明你实力不够强,先放着,等你实力 Up 了再来做。
以上的内容皆为抒情,可以不看。
分析
2022 年的我,不知道怎么做,暴力搜索直接干。当时也思考了很久到底这个跟背包有什么关系。
2023 年的我,啊!终于懂了!原来真的是一个很板的 DP。
首先把这个问题拆解一下,即把一堆数字拆为两堆,让两堆数字和的最大值最小。
很容易观察到数据范围 \(\sum\limits_{i=1}^na_i \le 10^6\),也就意味着数字和不超过 \(10^6\)。
然后直接就可以设 \(f_{i,j}\) 为考虑前 \(i\) 个,数字和为 \(j\) 是否可行。
直接进行背包转移即可,然后使用 std::bitset
可以将常数乘上 \(\dfrac{1}{32}\),效率很高!
因为使用了 std::bitset
也不存在倒着转移和正着转移,方程有点类似于#771. 「LibreOJ β Round #2」贪心只能过样例,于是可以压掉 \(i\) 这一维。
故时间复杂度 \(O(\dfrac{1}{32}n\sum a_i)\)。
直接爆杀成为最优解(我上面的那些人是因为订正比赛没有转成 IOI 赛制导致没有评测,故请求重测)。
代码
//the code is from chenjh
#include<cstdio>
#include<algorithm>
#include<bitset>
std::bitset<100001>f;//动态规划数组。
int main(){
int n,s=0;scanf("%d",&n);
f[0]=1;
for(int i=1,a;i<=n;i++) scanf("%d",&a),s+=a,f|=f<<a;//直接进行转移。
int a=s;
for(int i=f._Find_first();i<=s;i=f._Find_next(i))a=std::min(a,std::max(i,s-i));//使用 _Find_first() 和 _Find_next() 函数可以减少无效的枚举,提高效率。
printf("%d\n",a);
return 0;
}
【正常用法】#283. 「NOIP2009」靶形数独
分析
这一题做法很简单,这里不过多讲分析(如果真的要看可以看陈弈含的「NOIP2009」靶形数独 题解),这里侧重于讲 std::bitset
的使用。
一个题目底下 \(4\) 篇题解,竟然没有一个人使用 std::bitset
,这好歹也还是一个位运算的题目啊。
代码
//the code is from chenjh
#include<cstdio>//输入输出头文件。
#include<algorithm>//std::sort 排序以及 std::max 函数。
#include<bitset>//std::bitset。
#include<functional>//std::greater 重载运算符函数。
#include<utility>//std::pair 二元组。
#define G(x,y) ((x/3)*3+y/3)//当前所属的宫格位置。
typedef std::bitset<10> B;
typedef std::pair<int,int> PII;
const int n=9;
B h[n],l[n],g[n];
int a[n][n];
const int s[n][n]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};//预处理得分表。
int c[11];//得分为 i 的方格剩余数量为 c[i]。
int ans=0;
bool F=0;//是否有解。
int f(){return 9*(c[6]*6+c[7]*7+c[8]*8+c[9]*9+c[10]*10);}//估价函数,但是这个剪枝没啥大用,意思即把剩下的每个方格填上 9 以后的分数。
PII H[20];//二元组,first 存当前有多少个值确定,second 存行号。
void dfs(int pos,int y,const int w){
int x=H[pos].second;
if(y>=n) x=H[++pos].second,y=0;
if(pos>=n || x>=n){F=1,ans=std::max(ans,w);return;}//更新答案。
if(w+f()<=ans) return;//剪枝优化。
if(a[x][y]){dfs(pos,y+1,w+a[x][y]*s[x][y]);return;}
B f=h[x]&l[y]&g[G(x,y)];
if(f.none()) return;//none 函数的意思是此 bitset 是否每一位都为 false。
for(int i=f._Find_first();i<=n;i=f._Find_next(i))//_Find_first() 和 _Find_next 均为内置函数,前者的意思为找到第一个为 1 的下标,后者的意思为找到第 i 个以后的第一个为 1 的下标,以上函数如果查找失败均返回 std::bitset 的大小(这里即为 10)。
h[x][i]=l[y][i]=g[G(x,y)][i]=0,//标记当前位置已使用。
dfs(pos,y+1,w+i*s[x][y]),
h[x][i]=l[y][i]=g[G(x,y)][i]=1;//消除标记。
}
int main(){
c[6]=32,c[7]=24,c[8]=16,c[9]=8,c[10]=1;
for(int i=0;i<n;i++) h[i]=l[i]=g[i]=0x3fe,H[i].second=i;//初始化,3fe 的二进制形式即为 1111111110,标记 1 为未使用,0 为已使用。
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
if(!(h[i][a[i][j]]&l[j][a[i][j]]&g[G(i,j)][a[i][j]])) return puts("-1"),0;//如果数独不合规直接无解。
h[i][a[i][j]]=l[j][a[i][j]]=g[G(i,j)][a[i][j]]=0,--c[s[i][j]],ans+=a[i][j]*s[i][j],++H[i].first;//标记当前行、列、宫格。
}
}
std::sort(H,H+n,std::greater<PII>());//greater 即重载,这里排序的意思是将 first 为第一关键字,second 为第二关键字,降序排列。
dfs(0,0,0);
printf("%d\n",F?ans:-1);
return 0;
}
【奇怪用法】#1452. 「BZOJ2393」Cirno 的完美算数教室
前言
⚠Warning:这是非正解做法,请勿学习,仅当了解 std::bitset
。
分析
这种区间求满足某种条件数的个数的问题,直接用 std::bitset
啊!能暴力的事情谁去想正解容斥。
直接按照题意,搜索即可,最后用 count
函数求就行了。
卡着时限过,荣获最慢解和最大内存解,但是在 O2 的加持下最大数据仅用了 894ms!
代码
//the code is from chenjh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[2002],b[100001];
int n=0;
bitset <10000000001ll> s;
void dfs(int pos,const int w,LL now){
if(pos>w){
a[++n]=now;
return;
}
dfs(pos+1,w,now*10+2);
dfs(pos+1,w,now*10+9);
}
bool is_b(LL x){
for(int i=1;i<=n;i++) if(x%a[i]==0) return 1;
return 0;
}
LL solve(LL l,LL r){
LL ret=0;
for(;l<=r;++l)
ret+=is_b(l);
return ret;
}
int main(){
for(int i=1;i<10;++i) dfs(1,i,0);//枚举位数,进行搜索。
LL l,r;
scanf("%lld%lld",&l,&r);
for(int i=1;i<=n;i++){
LL L=l/a[i],R=r/a[i];
for(LL j=L*a[i]<l?L+1:L;j<=R;++j)
s[j*a[i]]=1;//标记当前位。
}
printf("%lld\n",s.count());//输出有多少个为 1。
return 0;
}
【奇怪做法】#1454. 「SCOI2010」幸运数字
前言
⚠Warning:这是非正解做法,请勿学习,仅当了解 std::bitset
。
分析
这一题的数据貌似要比上一题强“亿点点”,那么就需要用到一些小技巧。
这种区间求满足某种条件数的个数的问题如果被卡了,很容易想到分块打表。
将每 \(10^8\) 分作一块,在本地事先预处理好(可能会需要一段时间),接着直接加中间的整段,计算两边的小段,加和统计即可。
//the code is from chenjh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[2050];
int n=0;
bitset <10000000001ll> s;
int b[]={26367832,26367734,26367442,26367629,26367812,26367617,26367927,26367701,26367894,26367822,26367654,26367735,26367803,26367794,26367559,26367726,26367750,26367792,26367674,26367746,26367638,26367697,26367596,26367707,26367764,26367734,26367678,26367714,26367601,26367494,26367657,26367706,26367747,26367778,26367761,26367733,26367761,26367630,26367541,26367672,26367754,26367672,26367713,26367761,26367807,26367659,26367749,26367779,26367847,26367681,26367701,26367687,26367728,26367686,26367740,26367683,26367677,26367638,26367715,26367669,26367758,26367742,26367822,26367737,26367773,26367725,26367831,26367682,26367895,26367670,26367770,26367681,26367695,26367788,26367613,26367802,26367646,26367729,26367696,26367743,26367697,26367720,26367652,26367762,26367758,26367614,26367941,26367729,26367817,26367830,26367679,26367788,26367737,26367685,26367735,26367847,26367682,26367814,26367737,26367755,1};//直接打表出答案。
const int block=1e8;
void dfs(int pos,const int w,LL now){
if(pos>w){
a[++n]=now;
return;
}
dfs(pos+1,w,now*10+6);
dfs(pos+1,w,now*10+8);
}
LL solve(LL l,LL r){//计算小段。
// s.reset();//不要清空!清空的复杂度是 O(n) 的!会被卡常!
for(int i=1;i<=n;i++){
LL L=l/a[i],R=r/a[i];
for(LL j=L*a[i]<l?L+1:L;j<=R;++j)
s[j*a[i]]=1;
}
return s.count();
}
int main(){
for(int i=1;i<=10;++i) dfs(1,i,0);
LL l,r;
scanf("%lld%lld",&l,&r);
if(l==1 && r==1e10){//特判两个边界。
LL ans=0;
for(int i=0;i<=r/block;++i) ans+=b[i];
printf("%lld\n",ans);
return 0;
}
if(l/block==r/block){//如果是整块,直接输出即可。
printf("%lld\n",solve(l,r));
}
else{
LL ans=0;solve(l,(l/block+1)*block-1);
for(int i=l/block+1;i<r/block;i++)
ans+=b[i];//直接加整块。
ans+=solve(r/block*block,r);//分别计算小块。
printf("%lld\n",ans);
}
return 0;
}
结语
由上可见,std::bitset
是如此的强大!为什么不用这种效率如此高的容器呢?
参考文献
- std::bitset - cppreference.com
- cplusplus.com/reference/bitset/bitset/
- 《算法竞赛进阶指南》0x71 STL。