bitset学习笔记

优美的暴力

参考博客：1 2 3

基本操作

参考：link

Functions		Examples
(constructor)		bitset<16> foo; bitset<20> bar(233); bitset<8> baz(std::string("01001"));
applicable operators	^ & | << >> ~ == != ^= &= |= <<= >>=
operator[]	Access bit	foo[1]
count	Count bits set	foo.count()
size	Return size	foo.size()
test	Return bit value	foo.test(i)
any	Test if any bit is set	foo.any()
none	Test if no bit is set	foo.none()
all	Test if all bits are set	foo.all()
set	Set bits	foo.set() foo.set(2,0) foo.set(2)
reset	Reset bits	foo.reset() foo.reset(1)
flip	Flip bits	foo.flip() foo.flip(2)
to_string	Convert to string	foo.to_string()
to_ulong	Convert to unsigned long interger	foo.to_ulong()
to_ullong	Convert to unsigned long long	foo.to_ullong()

练习

poj2443 Set Operation

题目链接

bitset 存储每个点属于哪些集合，询问时 & 起来不为零输出 Yes，否则输出 No.

复杂度：$O\left(\frac{QN}{32}\right)$

>folded

#include<algorithm>
#include<vector>
#include<cstdio>
#include<bitset>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int n, q;
bitset<1005> bs[10005];

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		int c, a;
		read(c);
		while(c--){
			read(a);
			bs[a].set(i);
		}
	}
	read(q);
	while(q--){
		int x, y; read(x, y);
		if((bs[x] & bs[y]) != 0)	puts("Yes");
		else	puts("No");
	}
	return 0;
}

---

hdu5036 Explosion

题目链接

整体的期望次数等于打开每扇门的期望被炸次数之和。考虑门 $i$，设所有能到达 $i$ 的点构成集合 $S_i$（包括 $i$ 本身），则在任一合法炸门序列中，若已经有一个不同于 $i$ 且可到达 $i$ 的点出现了，那么 $i$ 的被炸次数为 $0$；否则，没有任何钥匙可以打开它，$i$ 必须被炸一次。于是打开第 $i$ 扇门的期望被炸次数为 $0\cdot\frac{|S_i|-1}{|S_i|}+1\cdot\frac{1}{|S_i|}=\frac{1}{|S_i|}$，答案为 $\sum\limits_{i=1}^n\frac{1}{|S_i|}$.

为求出 $|S_i|$，我们可以利用 floyd 算法求出连通性，并利用 bitset 加速。

复杂度：$O\left(\frac{n^3}{32}\right)$

>folded

#include<cstdio>
#include<bitset>

using namespace std;

const int N = 1005;

int T, n;
bitset<N> bs[N];

inline void floyd(){
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(bs[j].test(i))
				bs[j] |= bs[i];
}

int main(){
	scanf("%d", &T);
	for(int CASES = 1; CASES <= T; CASES++){
		scanf("%d", &n);
		for(int i = 1; i <= n; i++){
			bs[i].reset();
			bs[i].set(i);
		}
		for(int i = 1; i <= n; i++){
			int c, x; scanf("%d", &c);
			while(c--){
				scanf("%d", &x);
				bs[x].set(i);
			}
		}
		floyd();
		double ans = 0;
		for(int i = 1; i <= n; i++)
			ans += 1.0 / bs[i].count();
		printf("Case #%d: %.5f\n", CASES, ans);
	}
	return 0;
}

---

Gym100342 J - Triatrip

题目链接

每个点用 bitset 记录出边连接哪些点以及入边连接哪些点，统计答案的时候与起来数 $1$ 的个数。

复杂度：$O(\frac{n^3}{32})$

>folded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>

using namespace std;

typedef long long LL;

const int N = 1505;

int n;
LL ans;
char s[N];
bitset<N> in[N], out[N];

int main(){
	freopen("triatrip.in", "r", stdin);
	freopen("triatrip.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%s", s+1);
		for(int j = 1; j <= n; j++)
			if(s[j] == '+'){
				in[j].set(i);
				out[i].set(j);
			}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(in[i].test(j))
				ans += (out[i] & in[j]).count();
	printf("%lld\n", ans / 3);
	return 0;
}

---

hdu5313 Bipartite Graph

题目链接

先 $dfs$ 染色得到一系列二分图，然后重点在 $dp$.

设 $dp[i][k]$ 表示能否通过合并前 $i$ 个二分图构成一边是 $k$ 个点的二分图。则 $dp[i][k]=dp[i-1][k-a[i]]\ \mathrm{OR}\ dp[i-1][k-b[i]]$. 这个 $dp$ 是 $O(n^2)$ 的，由于 $dp$ 数组是 $bool$ 值，所以可以用 bitset 优化——把第一维滚掉，第二维就是 bitset 的每一位。

>folded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 10005;

int T, n, m;

struct Edge{
	int nxt, to;
}edge[N*N];
int head[N], edgeNum;
void addEdge(int from, int to){
	edge[++edgeNum] = (Edge){head[from], to};
	head[from] = edgeNum;
}

bool vis[N];
int cnt[2];
vector<pii> v;
void dfs(int x, int c){
	vis[x] = true;
	cnt[c]++;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(vis[edge[i].to])	continue;
		dfs(edge[i].to, c ^ 1);
	}
}

bitset<N> dp;

inline void init(){
	memset(head, 0, sizeof head);
	memset(vis, 0, sizeof vis);
	edgeNum = 0;
	v.clear();
	dp.reset();
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		init();
		for(int i = 1; i <= m; i++){
			int u, v; scanf("%d%d", &u, &v);
			addEdge(u, v);
			addEdge(v, u);
		}
		for(int i = 1; i <= n; i++){
			if(!vis[i]){
				cnt[0] = cnt[1] = 0;
				dfs(i, 0);
				v.pb(mp(cnt[0], cnt[1]));
			}
		}
		dp.set(0);
		for(int i = 0; i < v.size(); i++)
			dp = (dp << v[i].first) | (dp << v[i].second);
		int ans = 0;
		for(int i = 0; i < n; i++)
			if(dp.test(i))
				ans = max(ans, i * (n - i) - m);
		printf("%d\n", ans);
	}
	return 0;
}

---

hdu5890 Eighty seven

题目链接

设 $dp[i][j][k]$ 表示前 $i$ 个数选取 $j$ 个数能否凑出 $k$，则不考虑去掉 $3$ 个数的话，$dp[i][j][k]=dp[i-1][j-1][k-a[i]]\ \mathrm{OR}\ dp[i-1][j][k]$. 和上一题同理，滚动数组滚掉第一维，bitset 优化第三维。每次操作都重新求一遍 $dp$ 数组，时间有点吃紧，可以记忆化一下（虽然理论上最差复杂度没变）。

>folded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, n, a[55], q;
bitset<88> dp[15];
int ok[55][55][55];

int main(){
	read(T);
	while(T--){
		read(n);
		memset(ok, -1, sizeof ok);
		for(int i = 1; i <= n; i++)	read(a[i]);
		read(q);
		while(q--){
			int x, y, z; read(x, y, z);
			if(ok[x][y][z] != -1){
				puts(ok[x][y][z] ? "Yes" : "No");
				continue;
			}
			dp[0].set(0);
			for(int j = 1; j <= 10; j++)	dp[j].reset();
			for(int i = 1; i <= n; i++)
				if(i != x && i != y && i != z)
					for(int j = 10; j >= 1; j--)
						dp[j] |= (dp[j-1] << a[i]);
			ok[x][y][z] = ok[x][z][y] = dp[10].test(87);
			ok[y][x][z] = ok[y][z][x] = dp[10].test(87);
			ok[z][x][y] = ok[z][y][x] = dp[10].test(87);
			puts(dp[10].test(87) ? "Yes" : "No");
		}
	}
	return 0;
}

---

hdu5808 Price List Strike Back

题目链接

正解是 CDQ 分治，不过可以用 bitset 加速 $dp$ 过这道题。

先将所有商店和询问按距离排序，这样我们可以用一个指针不断后移指出哪些店距离小于询问距离。开一棵树状数组记录每种价格的个数，然后做一个多重背包的可行性 $dp$，用 bitset 优化。

不过时间还是有点吃紧，还可以优化：1. 做背包的时候一旦发现可行就退出；2. 在总价格为 $s$ 时，价格为 $k$ 的点最多只用 $\frac{s}{k}$ 个；3. 多重背包用二进制优化。

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 20005;
const int M = 100005;

int T, n, m;
bitset<101> dp;
bool ans[M];

struct Shop{
	int v, d, id; // val and distance
	bool operator < (const Shop &A) const{
		return d < A.d;
	}
}shop[N];

struct Query{
	int l, r, d, s, id;
	bool operator < (const Query &A) const{
		return d < A.d;
	}
}q[M];
bool cmp(const Query &A, const Query &B){
	return A.id < B.id;
}

struct Node{
	int val[105];
}c[N];
inline int lowbit(int x){ return x & -x; }
inline void add(int x, int v){
	while(x <= n){
		c[x].val[v]++;
		x += lowbit(x);
	}
}
inline void sum(int x, int a[]){
	for(int i = 1; i <= 100; i++)
		a[i] = 0;
	while(x){
		for(int k = 1; k <= 100; k++)
			a[k] += c[x].val[k];
		x -= lowbit(x);
	}
}

int L[105], R[105];
inline bool solve(int i){
	sum(q[i].r, R), sum(q[i].l-1, L);
	if(R[q[i].s] - L[q[i].s])	return true;
	dp.reset(), dp.set(0);
	for(int k = 1; k <= q[i].s; k++){
		int cnt = min(R[k] - L[k], q[i].s / k);
		for(int j = 1; j <= cnt; cnt -= j, j <<= 1){
			dp |= (dp << (k * j));
			if(dp.test(q[i].s))	return true;
		}
		if(cnt > 0)	dp |= (dp << (k * cnt));
		if(dp.test(q[i].s))	return true;
	}
	return dp.test(q[i].s);
}

int main(){
	read(T);
	while(T--){
		read(n, m);
		memset(c, 0, sizeof c);
		for(int i = 1; i <= n; i++)	read(shop[i].v), shop[i].id = i;
		for(int i = 1; i <= n; i++)	read(shop[i].d);
		sort(shop+1, shop+n+1);
		for(int i = 1; i <= m; i++)
			read(q[i].l, q[i].r, q[i].d, q[i].s), q[i].id = i;
		sort(q+1, q+m+1);
		int pts = 0;
		for(int i = 1; i <= m; i++){
			while(pts < n && shop[pts+1].d <= q[i].d){
				pts++;
				add(shop[pts].id, shop[pts].v);
			}
			ans[q[i].id] = !solve(i);
		}
		for(int i = 1; i <= m; i++)
			printf("%d", ans[i]);
		puts("");
	}
	return 0;
}

---

CF981E Addition on Segments

题目链接

把所有操作放到线段树上，$dfs$ 这颗线段树，当到达叶节点时，我们得到了包含这个叶节点的一系列操作。如果只进行这些操作而不进行不包含该节点的操作的话，这个节点的值就一定是最大值，所以此时做一个 $01$ 背包的可行性 $dp$，用 bitset 优化。为降低复杂度，一路搜索下来时边走边 $dp$，同时记录上一层的 $dp$ 值便于回溯时撤销。

复杂度：$O(\frac{qn\lg n}{32})$

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 10005;

int n, q;
bitset<N> ans;

struct segTree{
	int l, r;
	vector<int> v;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].v.clear();
	if(tr[id].l == tr[id].r)	return;
	build(lid, l, mid);
	build(rid, mid+1, r);
}
void add(int id, int l, int r, int val){
	if(tr[id].l == l && tr[id].r == r){
		tr[id].v.emplace_back(val);
		return;
	}
	if(r <= mid)	add(lid, l, r, val);
	else if(l > mid)	add(rid, l, r, val);
	else	add(lid, l, mid, val), add(rid, mid+1, r, val);
}

bitset<N> dp;
void dfs(int id){
	bitset<N> rec = dp;
	for(auto k: tr[id].v)
		dp |= dp << k;
	if(tr[id].l == tr[id].r){
		for(int i = 1; i <= n; i++)
			if(dp.test(i))
				ans.set(i);
		dp = rec;
		return;
	}
	dfs(lid), dfs(rid);
	dp = rec;
}

int main(){
	scanf("%d%d", &n, &q);
	build(1, 1, n);
	while(q--){
		int l, r, x; scanf("%d%d%d", &l, &r, &x);
		add(1, l, r, x);
	}
	dp.reset(), dp.set(0);
	dfs(1);
	printf("%d\n", (int)ans.count());
	for(int i = 1; i <= n; i++)
		if(ans.test(i))
			printf("%d ", i);
	puts("");
	return 0;
}

---

poj1742 Coins

题目链接

多重背包的可行性问题，bitset + 二进制优化。

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 105;
const int M = 100005;

int n, m, a[N], c[N];
bitset<M> dp;
bitset<M> mask;

int main(){
	while(1){
		read(n, m);
		if(!n && !m)	break;
		for(int i = 1; i <= n; i++)	read(a[i]);
		for(int i = 1; i <= n; i++)	read(c[i]);
		dp.reset(), dp.set(0);
		for(int i = 1; i <= n; i++){
			for(int p = 1; p <= c[i]; c[i] -= p, p <<= 1)
				dp |= dp << (p * a[i]);
			dp |= dp << (c[i] * a[i]);
		}
		mask.reset();
		for(int i = 0; i <= m; i++)	mask.set(i);
		dp &= mask;
		printf("%d\n", (int)dp.count() - 1);
	}
	return 0;
}

---

CSU2005 Nearest Maintenance Point

题目链接

如果不要求输出最近点，那么以所有的特殊点为源跑一遍 $dijkstra$ 即可。现在为了记录哪些点是最近点，采用 bitset，在松弛操作时更新即可。

>folded

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 10005;
const int M = 50005;
const int INF = 1e9;

int n, m, s, q, func[N];
vector<int> spec;

struct Edge{
    int nxt, to, dis;
}edge[M<<1];
int head[N], edgeNum;
void addEdge(int from, int to, int dis){
    edge[++edgeNum].nxt = head[from];
    edge[edgeNum].to = to;
    edge[edgeNum].dis = dis;
    head[from] = edgeNum;
}

struct Node{
    int dis, num;
    bool operator < (const Node &a) const{
        return a.dis < dis;
    }
};
int dis[N];
bool inS[N];
bitset<1005> bs[N];
void dijkstra(){
    priority_queue<Node> q;
    for(int i = 1; i <= n; i++)	dis[i] = INF, inS[i] = 0;
    for(auto k: spec){
    	dis[k] = 0;
    	q.push( (Node){0, k} );
    	bs[k].set(func[k]);
    }
    while(!q.empty()){
        Node cur = q.top();	q.pop();
        if(inS[cur.num])	continue;
        inS[cur.num] = 1;
        for(int i = head[cur.num]; i; i = edge[i].nxt){
            if((LL)dis[edge[i].to] > (LL)dis[cur.num] + edge[i].dis){
            	bs[edge[i].to] = bs[cur.num];
                dis[edge[i].to] = dis[cur.num] + edge[i].dis;
                q.push( (Node){dis[edge[i].to], edge[i].to} );
            }
            if((LL)dis[edge[i].to] == (LL)dis[cur.num] + edge[i].dis)
            	bs[edge[i].to] |= bs[cur.num];
        }
    }
}

inline void init(){
	for(int i = 1; i <= n; i++){
		bs[i].reset();
		head[i] = 0;
		func[i] = 0;
	}
	edgeNum = 0;
	spec.clear();
}

int main(){
	while(scanf("%d%d%d%d", &n, &m, &s, &q) != EOF){
		init();
		for(int i = 1; i <= m; i++){
			int u, v, w; scanf("%d%d%d", &u, &v, &w);
			addEdge(u, v, w), addEdge(v, u, w);
		}
		for(int i = 1; i <= s; i++){
			int x; scanf("%d", &x);
			spec.emplace_back(x);
			func[x] = i;
		}
		dijkstra();
		while(q--){
			int x; scanf("%d", &x);
			for(int i = 1; i <= s; i++)
				if(bs[x].test(i))
					printf("%d ", spec[i-1]);
			puts("");
		}
	}
	return 0;
}

---

hdu6085 Rikka with Candies

题目链接

用 bitset 记录 $A,B$ 数组中出现的数字（的奇偶性），倒序枚举 $k$，则 $B$ 中所有比 $k$ 大的数可能对答案有贡献，对这些数，统计它们的倍数，加上 $k$ 后与 $A$ 重叠部分就是对答案的贡献。

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

const int N = 50005;

int T, n, m, q, a[N], b[N], mxb, ans[N];
bitset<N> A, B, MB;

int main(){
	read(T);
	while(T--){
		read(n, m, q);
		A.reset(), B.reset(), MB.reset();
		mxb = 0;
		for(int i = 1; i <= n; i++){
			read(a[i]);
			A.flip(a[i]);
		}
		for(int i = 1; i <= m; i++){
			read(b[i]);
			B.flip(b[i]);
			mxb = max(mxb, b[i]);
		}
		for(int k = mxb; k >= 0; k--){
			ans[k] = ((MB << k) & A).count() & 1;
			if(B.test(k))
				for(int j = 0; j <= mxb; j += k)
					MB.flip(j);
		}
		while(q--){
			int k; read(k);
			printf("%d\n", ans[k]);
		}
	}
	return 0;
}

---

CF687C The Values You Can Make

题目链接

设 $dp[j][k]$ 表示凑出总数为 $j$ 的时候能否凑出 $k$，那么 $dp[j][k] = dp[j-a[i]][k]\ \mathrm{OR}\ dp[j-a[i]][k-a[i]]$. 用 bitset 优化。

复杂度：$O\left(\frac{nk^2}{32}\right)$

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 505;

int n, k, a[N], id;
bitset<N> dp[N<<1];

int main(){
	read(n, k);
	for(int i = 1; i <= n; i++)	read(a[i]);
	dp[0].set(0);
	for(int i = 1; i <= n; i++)
		for(int j = k; j >= a[i]; j--)
			dp[j] |= dp[j-a[i]] | (dp[j-a[i]] << a[i]);
	printf("%d\n", (int)dp[k].count());
	for(int i = 0; i <= k; i++)
		if(dp[k].test(i))
			printf("%d ", i);
	puts("");
	return 0;
}