一、概念
bitset可以说是一个多位二进制数，每八位占用一个字节，因为支持基本的位运算，所以可用于状态压缩，n位bitset执行一次位运算的时间复杂度可视为n/32.
二、基本操作
1.定义：
bitset< n > s;
表示一个n位的二进制数，<>中填写位数；
2.位运算操作符：
~s: 返回对s每一位取反后的结果；
&，|，^：返回对两个位数相同的bitset执行按位与、或、异或运算的结果；
<<, >>:返回把一个bitset左移，右移若干位的结果.（补零）；
==，！=：比较两个位数相同的bitset代表的二进制数是否相等；
3.[ ]操作符：
s[k] :表示s的第k位，即可取值也可赋值，编号从0开始；
4.count:
s.count() 返回二进制串中有多少个1；
5.any/none
若s所有位都为0，则s.any()返回false，s.none()返回true；
若s至少有一位为1，则s.any()返回true，s.none()返回false；
6.set/rest/flip
s.set()把s所有位变为1；
s.set(k,v)把s的第k位改为v,即s[k]=v；
s.reset()把s的所有位变为0.
s.reset(k)把s的第k位改为0,即s[k]=0；
s.flip()把s所有位取反.即s=~s；
s.flip(k)把s的第k位取反，即s[k]^=1；
三、题目
可达性统计（AcWing164）
思路：
遍历一遍图，在回溯时将子节点状态加入节点状态中，用一个n长度的二进制bitset串记录状态第i位为1表示i节点从该节点可达，最后输出每个节点状态中1的个数即可。遍历时从入度为1的节点开始.
代码：
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
typedef unsigned long long ull;const ll inf=1e9+7;bitset<30005> s[30005];vector<int> g[30005];int in[30005], vis[30005];queue<int> q;void dfs(int v)
{//printf("v=%d\n",v);if(vis[v]){return ;}s[v][v]=1;for(int i=0;i<g[v].size();i++){int u=g[v][i];dfs(u);s[v]|=s[u];}vis[v]=1;
}int main()
{int n, m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u, v;scanf("%d%d",&u,&v);g[u].push_back(v);in[v]++;}for(int i=1;i<=n;i++){if(in[i]==0){q.push(i);}}while(!q.empty()){int v=q.front();q.pop();dfs(v);}for(int i=1;i<=n;i++){printf("%d\n",s[i].count());}
}本文链接：https://my.lmcjl.com/post/3817.html
4 评论