# bitset

# 用途

这个东西相当于一个 bool 数组,int 是 32 位表示一个数,而这个 32 位表示 32 个数,每一位只能存 1 或者 0,这就使得可以开的空间是 int 的 32 倍,时间复杂度为(位数)N/W (计算机常数一般为 32),而访问其中某一位时间复杂度为 O (1),这个的用处多用于数组开不下 1e9 以上的空间,用 unordered_map 插入时复 O (logn) 级别,就可以用 bitset 优化时间为 O (1)

# 定义与初始化

使用 bitset 类型需 #include<bitset>

bitset 类型在定义时就需要指定所占的空间,例如

bitset<233>bit;

bitset 类型可以用 string 和整数初始化(整数转化成对应的二进制)

#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;
int main()
{
    bitset<23>bit (string("11101001"));
    cout<<bit<<endl;
    bit=233;
    cout<<bit<<endl;
    return 0;
}

输出结果

00000000000000011101001
00000000000000011101001

# 基本运算

bitset 支持所有位运算

使用这个来进行位运算要比数组模拟位运算快 32 倍

bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita^bitb)<<endl;
// 输出 00000000000000000000001
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita|bitb)<<endl;
// 输出 00000000000000011101001
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita&bitb)<<endl;
// 输出 00000000000000011101000
bitset<23>bit(string("11101001"));
cout<<(bit<<5)<<endl;
// 输出 00000000001110100100000
bitset<23>bit(string("11101001"));
cout<<(bit>>5)<<endl;
// 输出 00000000000000000000111

# 常用函数

对于一个叫做 bit 的 bitset:

  • bit.size () 返回大小(位数)
  • bit.count () 返回 1 的个数
  • bit.any () 返回是否有 1
  • bit.none () 返回是否没有 1
  • bit.set () 全都变成 1
  • bit.set (p) 将第 p + 1 位变成 1(bitset 是从第 0 位开始的!)
  • bit.set (p, x) 将第 p + 1 位变成 x
  • bit.reset () 全都变成 0
  • bit.reset (p) 将第 p + 1 位变成 0
  • bit.flip () 全都取反
  • bit.flip (p) 将第 p + 1 位取反
  • bit.to_ulong () 返回它转换为 unsigned long 的结果,如果超出范围则报错
  • bit.to_ullong () 返回它转换为 unsigned long long 的结果,如果超出范围则报错
  • bit.to_string () 返回它转换为 string 的结果

# 题目

https://ac.nowcoder.com/acm/contest/11160/D

利用 bitset 可以卡过去

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=1e6+100;
const double pi=acos(-1);
const ll MOD=1e9+7;
const ll INF=0x3f3f3f3f;
const ll SUB=-0x3f3f3f3f;
const ll eps=1e-4;
ll n,m;
ll a[MAXN],b[MAXN]; 
unordered_map<ll,ll> mp;
bitset<1<<30> bt;
int main(){
	ios;
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i];
	for(ll i=1;i<=m;i++){
		cin>>b[i];
		bt.set(b[i]);
		mp[b[i]]++;
	}
	ll ans=0;
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<30;j++){
			for(ll k=j+1;k<30;k++){
				ll now=(1<<j)+(1<<k);
				if(bt[a[i]^now]) ans+=mp[a[i]^now];
			}
		}
	} 
	cout<<ans<<'\n';
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝