Bitset

基本功能

类似一个二进制的数字，$bitsit$只能存储$1$或者$0$（$true$或者$false$），比如下面这一条：

定义

bitset<长度>名字;

当没有写using namespace std时，需要在前面加上std::的前缀。

操作

count()：返回true的数量。
size()：返回的大小。
any()：若存在某一位是 true 则返回 true，否则返回 false。
none()：若所有位都是 false 则返回 true，否则返回 false。
all()：若所有位都是 true 则返回 true，否则返回 false。
set()：将整个 bitset 设置成 true。
set(位置,true/false）)：将某一位设置成 true/false。
reset()：将整个 bitset 设置成 false。
reset(位置)：将某一位设置成 false。相当于set(位置, false)。
flip()：翻转每一位(相当于异或一个全是1的bitset)。
flip(pos)：翻转某一位。
to_string()：返回转换成的字符串表达。
to_ulong()：返回转换成的 unsigned long 表达。
to_ullong()：返回转换成的 unsigned long long 表达。

注意

$bitset$只能和同类型的变量进行$\&$，$|$，$!$的位运算。

例题1

Switches and Lamps
由于$n\le 2000$，所以可以考虑直接暴力。
每次选一个开关不管，看最后能不能打开所有灯。

//https://vjudge.net/problem/CodeForces-985B
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
void putstr(string s){for(int i=0;i<s.size();i++)putchar(s[i]);
}
int n,m;
bitset<2005>a[N];
signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char x;cin>>x;if(x=='1')a[i].set(j,1);//初始化bitset}}for(int i=1;i<=n;i++){bitset<2005>t;for(int j=1;j<=n;j++){if(i==j)continue;t|=a[j];}if(t.count()==m){//判断是否所有灯都打开putstr("YES");return 0;}}putstr("NO");
}

例题2

AT_abc258_g [ABC258G] Triangle
特水的一道$G$题。
思路：首先，先找到两个有边相连的点，这两个点连接的共同的点就是两点贡献的答案。

//https://vjudge.net/problem/AtCoder-abc258_g
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
void print(int x){if(x<0)putchar('-'),x=-x;if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');
}
int n;
bitset<3005>a[N];
signed main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){char x;cin>>x;if(j<=i)continue;//防止重复计算if(x=='1')a[i].set(j,1);//初始化}}int ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(a[i][j]){//有边相连bitset<3005>x=a[i]&a[j];//两点贡献ans+=x.count();}}}print(ans);
}