Bitset常用操作：

bitset s; //定义一个大小为size的bitset
s.count(); //统计s中1的个数
s.set(); //将s的所有位变成1
s.set(p); //将s的第p位变成1
s.reset(); //将s的所有位变成0
s.reset(p); //将s的第p位变成0
s.flip(); //将s的所有位取反
s.flip(p); //将s的第p位取反
s.to_string(); //将s转换成string

两个$bitset$运算的时间复杂度大概是$O(\frac{n}{32})$，所以能卡进去的话可以不写这个东西。

例题：

1.HDU5313-Bipartite Graph

有若干个二分图，现在你要添加一些边形成一个完全二分图，求最多可以添加多少边。

考虑对于每个二分图统计两部分的节点数$a_{i},b_i$，问题变为有两个集合，对于每个i，将$a_i$或$b_i$加入集合，使得两个集合的和尽量接近。

只需要模拟退火做一个背包，令$dp[i]$表示i是否能凑出来，最后取最接近$n/2$的能凑出来的数作为答案。用$bitset$优化该dp即可。

#include
#include
#include
#include
#include
#define maxn 10005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long

using namespace std;
int N,M,hd[maxn],to[maxm],nxt[maxm],cnt;
int l[maxn],r[maxn],tot;
bool vis[maxn];
bitset dp;

inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}

inline void addedge(int u,int v){to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt;}

inline void dfs(int u,bool f){
vis[u]=;
if(!f) l[tot]++; else r[tot]++;
for(int i=hd[u];i;i=nxt[i]){
int v=to[i];
if(!vis[v]) dfs(v,(f^));
}
return;
}

int main(){
int T=read();
while(T--){
N=read(),M=read();
tot=;cnt=;
memset(hd,,sizeof(hd));
memset(vis,,sizeof(vis));
memset(l,,sizeof(l));
memset(r,,sizeof(r));
for(int i=;i<=M;i++){
int u=read(),v=read();
addedge(u,v),addedge(v,u);
}
for(int i=;i<=N;i++) if(!vis[i]) tot++,dfs(i,);
dp.reset(); dp.set(,);
for(int i=;i<=tot;i++)
dp=(dp<<l[i])|(dp<<r[i]);
int ans=;
for(int i=;i<=N;i++)
if(dp[i]) ans=max(ans,i*(N-i)-M);
printf("%d\n",ans);
}
return ;
}

hdu5313

2.BZOJ2208-[Jsoi2010]连通数

给你一个有向图，求图中可达顶点对的个数。

考虑Floyd求最短路的过程是枚举中转点k后用k更新每对i，j，现在不需要求最短路而只需要判断能不能到达。

所以设$dp[k]$表示k能到达的点集的二进制表示，枚举k，i后用$dp[k]$更新$dp[i]$即可。

#include
#include
#include
#include
#include
#define maxn 2005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long

using namespace std;
int N; char str[maxn][maxn];
bitset dis[maxn];

inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}

int main(){
N=read();
for(int i=;i<=N;i++){
scanf("%s",str[i]+);
for(int j=;j<=N;j++)
if(str[i][j]-''||i==j)
dis[i].set(j);
}
for(int k=;k<=N;k++)
for(int i=;i<=N;i++)
if(dis[i][k])
dis[i]|=dis[k];
int ans=;
for(int i=;i<=N;i++) ans+=dis[i].count();
printf("%d\n",ans);
return ;
}

bzoj2208

3.Hihocoder1236-Scores

在线求五维偏序的对数。

考虑可以对于每一维分别计算出满足要求的人的二进制表示后把5个二进制数与起来即为答案。

但这样空间时间两爆炸，所以考虑分块bitset，令$dp[k][i]$表示第k维前i个块的人的二进制表示。

对于每个询问的每一维二分查找出它所在的块，即可求出答案。

切忌在多重循环内使用两个$bitset$相互运算。

#include
#include
#include
#include
#include
#include
#define maxn 50005
#define maxm 305
#define inf 0x7fffffff
#define ll long long

using namespace std;
bitset dp[][maxm],tp,ans;
int N,M,bel[maxn],db[][maxn];
struct node{int val,ind;}h[][maxn];

inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}

inline bool cmp(node a,node b){return a.val>;
if(db[k][mid]<=x) l=mid+,aans=mid;
else r=mid-;
}
return aans;
}

int main(){
//freopen("1.in","r",stdin);
//freopen("1.txt","w",stdout);
int T=read();
while(T--){
N=read(),M=read();
int len=sqrt(N);
memset(bel,,sizeof(bel));
memset(db,,sizeof(db));
for(int i=;i<=N;i++) for(int j=;j<;j++) h[j][i].val=read(),h[j][i].ind=i; for(int i=;i<=N;i++) bel[i]=(i-)/len+; for(int k=;k<;k++){ tp.reset(); sort(h[k]+,h[k]++N,cmp); for(int i=;i<=N;i++) db[k][i]=h[k][i].val; for(int i=;i<=N;i++){ tp.set(h[k][i].ind); if(bel[i]!=bel[i+]) dp[k][bel[i]]=tp; } } int Q=read(),lasans=; for(int nu=;nu<=Q;nu++){ for(int k=;k<;k++){ int x=read()^lasans,pos=upb(k,x),id=bel[pos]; if(pos==) {ans.reset();continue;} tp.reset(); if(id>=) tp|=dp[k][id-];
for(int i=(id-)*len+;i<=pos;i++) tp.set(h[k][i].ind);
if(k==) ans=tp; else ans&=tp;
}
lasans=ans.count();
printf("%d\n",lasans);
}
}
return ;
}

hihocoder1236