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（有时候也可以是一个整数）之间的按位运算（& | ^ &= |= ^= ~ <<= >>= << >>）。

使用可以看例题，不过多举例。

函数

元素访问

容量

修改器

转换

内置函数

内置函数并不在 C++ 标准中，但是考试时可用。

以上两个函数寻找失败均会返回 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。

本栏目推荐文章
• package dbutil is not in std
• std::advance学习
• std::sort()
• bitset优化传递闭包
• std::max、std::min error C2589: “(”:“::”右边的非法标记，error C2059: 语法错误:“::” （转）
• 洛谷B3611 【模板】传递闭包 floyd/bitset
• std::remove_if用法学习
• [how does it work series] std::bind
• C++标准库std::string的find_first_not_of 方法介绍：
• CentOS7 gcc：unrecognized command line option ‘-std=c++14’

bitset std函数 常用bitset std bitset std bitset 笔记bitset 数组bitset 背包bitset 板子bitset 闭包bitset codeforces unlock bitset round acm-knowledge knowledge bitset acm