专栏文章

bitset神力

DDJ_Liu
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mie5z734
此快照首次捕获于
2025/11/25 13:57
3 个月前
此快照最后确认于
2025/12/01 21:17
3 个月前
查看原文
有一说一 bitset 真是今年算法一匹黑马吧。很多老 stl 也都写过了，不吹不黑，本人 vector 9000 小时，multiset 2000 小时，set 3000 小时，map 4000 小时，pair 3000 小时，算法库里大多数 stl 都上千个小时，真感觉不出来和 bitset 有什么细节差距。只有 bitset 能给我一种刚接触 stl 时的感动。

用法

bitset 是 c++ 的一个 stl，类似于一个 bool 数组，每一位都是 0 / 1，大小位 1bit，可以支持位运算，空间复杂度是 O(nw)O(\frac{n}{w})，ww 是计算机的位数（不是没人告诉我那是 ww 不是 ω\omega 啊）。
  1. 定义：bitset<V> b;，V 是 bitset 的位数，还可以 bitset<V> b("001011")，就可以初始化；
    （注意：这里是反向的，如果你此时调用 for (int i = 0; i < 6; i++) cout << b[i]; 那么输出的是 110100，不过似乎也没多少地方要这么用）
  2. 全局修改：b.set() / b.reset()：设为全 1 / 全 0，b.flip()：取反，时间复杂度 O(nω)O(\frac{n}{\omega})；
  3. 单点修改：b[pos] = 0/1：直接访问，b.set(pos, val = 0/1)：将某位设为 0 / 1，b.reset(pos)：将某位设为 0，b.flip(pos)：pos 位取反，时间复杂度 O(1)O(1)；
  4. 位运算：将这些 0 / 1 视为二进制数与其他 bitset 进行二元位运算（与 / 或 / 异或…），或者左移 / 右移，时间复杂度 O(nω)O(\frac{n}{\omega})；
  5. 单点访问：b[pos]，b.test(pos)：返回 pos 位的值，时间复杂度 O(1)O(1)；
  6. 全局访问：b.any()：b 中是否存在一位为 1，b.none()：b 中是否不存在一位为 1，b.count()：b 中 1 的数量，时间复杂度 O(nω)O(\frac{n}{\omega})。

应用

维护集合

Set Operation

nn 个集合，给你每个集合的元素，qq 次询问两个数是否存在于同一个集合内。
1≤n≤104,1≤q≤2×105,1≤ci≤1051\le n\le 10^4, 1\le q \le 2\times10^5,1\le c_i\le 10^5。
直接枚举 f[i][x] 表示第 ii 个集合有没有 xx 会死，O(qn)O(qn) 是 2×1092\times10^9 的，于是用 bitset 优化，带一个 1w\frac{1}{w} 的常数，就能过了。
code:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 1e3 + 10, maxm = 1e4 + 10, mod = 1e9 + 7;
bitset<maxm> f[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            f[i][x] = 1;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        bool ff = 0;
        for (int i = 1; i <= n; i++) {
            if (f[i][l] && f[i][r]) {
                ff = 1;
                cout << "Yes" << endl;
                break;
            }
        }
        if (!ff) cout << "No" << endl;
    }
    return 0;
}
还有另外一种方式，用 f[x][i] 表示 xx 数是否出现在 ii 中，那么询问就是按位与再判断是否有 1 就好了，比较好写。
code:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 1e3 + 10, int maxm = 1e4 + 10, mod = 1e9 + 7;
bitset<maxn> f[maxm];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            f[x][i] = 1;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ((f[l] & f[r]).any() ? "Yes" : "No") << endl;
    }
    return 0;
}

CF1097F Alex and a TV Show

nn 个可重集，mm 次操作形如将集合设为单个数、将集合设为另外两个集的并、将集合设为另外两个集合每个元素的 gcd 的并、询问集合内 xx 的个数。
1≤n≤105,1≤x≤7000,1≤m≤1061\le n\le 10^5, 1\le x\le 7000, 1\le m\le 10^6。
模拟赛题不会哭哭。
注意到模 2，于是可以拿 bitset 维护。
于是第一个操作直接改，第二个操作是异或，第四个操作直接查。
第三个操作不太好做，考虑每个 bitset 维护所有约数，那么第三个操作就是按位与。
预处理每个数的约数，第一个也秒了，第四个怎么办……
令原可重集为 AA，约数可重集为 A′A'，查询 xx 的个数，莫比乌斯反演：
∑a∈A[a=x]=∑a∈A[ax=1]=∑a∈A∑d∣axμ(d)=∑d∈A′,x∣dμ(xd)\begin{align*} \sum_{a\in A}[a=x]&=\sum_{a\in A}[\frac{a}{x}=1]\\ &=\sum_{a\in A}\sum_{d|\frac{a}{x}}\mu(d)\\ &=\sum_{d\in A',x|d}\mu(\frac{x}{d}) \end{align*}
由于模 2，μ(x)\mu(x) 相当于 xx 有没有平方因数，预处理每个数没有平方因数的倍数，便可以 O(vlog⁡v)O(v\log v) 预处理，O(vω)O(\frac{v}{\omega}) 单个操作。
code:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 7e3 + 10, maxm = 1e5 + 10, mod = 1e9 + 7;
bitset<maxn> mu, a[maxm], pre[maxn], pre2[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);    
    int n, m;
    cin >> n >> m;
    mu.set();
    for (int i = 2; i * i < maxn; i++)
        for (int j = 1; j * i * i < maxn; j++)
            mu[i * i * j] = 0;
    for (int i = 1; i < maxn; i++)
        for (int j = 1; i * j < maxn; j++)
            pre[i * j][i] = 1, pre2[i][i * j] = mu[j];
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            a[x] = pre[y];
        }
        else if (op == 2) {
            int x, y, z;
            cin >> x >> y >> z;
            a[x] = a[y] ^ a[z];
        }
        else if (op == 3) {
            int x, y, z;
            cin >> x >> y >> z;
            a[x] = a[y] & a[z];
        }
        else {
            int x, y;
            cin >> x >> y;
            cout << ((a[x] & pre2[y]).count() & 1);
        }
    }
    return 0;
}

优化 dp

一般都是可行性 dp，或者状态是 bool 值的 dp，常见的有一系列背包问题。

简单瞎搞题、贪心只能过样例

nn 个数，每个数 xi∈[li,ri]x_i\in[l_i, r_i]，问 ∑i=1nxi2\sum_{i=1}^nx_i^2 有多少取值。
1≤n,li,ri≤1001\le n, l_i, r_i\le 100。
由于数据范围很小可以转换为可行性问题，设 fi,jf_{i, j} 表示前 ii 个数能不能达到 jj，那么考虑枚举第 ii 位的数 xx，则 f[i][j] |= f[i - 1][j - x * x]。
很明显会炸，我们考虑用 bitset 的 fif_i 表示前 ii 个数能达到哪些数，那么状态栏的 j−x2j-x^2 就相当于左移了 x2x^2 位，于是 f[i] |= (f[i - 1] << (x * x))。
code:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 1e2 + 10, maxm = 1e6 + 10, mod = 1e9 + 7;
bitset<maxm> f[maxn];
int l[maxn], r[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);    
    int n;
    cin >> n;
    f[0].set(0);
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    for (int i = 1; i <= n; i++) {
        for (int x = l[i]; x <= r[i]; x++) {
            f[i] |= (f[i - 1] << (x * x));
        }
    }
    cout << f[n].count();
    return 0;
}

P5020 [NOIP 2018 提高组] 货币系统

给你 nn 种货币的面值，成为 AA 货币系统，让你求出一个货币系统 BB，使得 BB 系统的货币种类不超过 AA 系统，并且 AA 系统能凑出的面值 BB 系统也能凑出，AA 系统不能凑出的面值 BB 系统也不能凑出。
1≤t≤20,1≤n≤100,1≤ai≤250001\le t\le20,1\le n\le100,1\le a_i\le25000。
bitset 优化完全背包，式子就不推了，令 f[x] 表示 xx 能不能表示出来，则 f[x] |= f[x - k * a[i]]，枚举 kk 即可。
注意到 k=3k = 3 时相当于 k=1,k=2k = 1, k = 2 的情况叠加，k=5k = 5 相当于 k=1,k=4k=1, k=4 的叠加，所以只需要枚举 k=2jk=2^j 即可。
code:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxn = 1e5 + 10, maxm = 2.5e4 + 10,mod = 1e9 + 7; 
int a[maxn];
bitset<maxm> s;
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int t;
    cin >> t;
    while (t--) {
        s.reset();
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        s[0] = 1;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!s[a[i]]) {
                ans++;
                int x = a[i];
                while (x <= a[n]) s |= s << x, x <<= 1;
            }
        }
        cout << ans << endl;
    }
    return 0; 
}
其实不优化也能过（

高维偏序

用 bitset 做高维偏序是 O(n2mw)O(\frac{n^2m}{w})，mm 是维数。
具体来说你的 bitset<N> b[N] 记录的是 jj 是否完全偏序 ii，那么先按照每一维排序，得到每一维的 pip_i，满足对于所有 j<kj < k，a[p[i][j]][i] <= a[p[i][k]][i]，即每一维的升序的指针序列。
然后再记录一个 bitset<N> tmp，就可以在那个指针序列上，对每一位，用一个指针扫每一个小于等于那一位上数的位置，每扫过一个点就 tmp.set(pos)，直到扫不动了就让那一位 & 上 tmp，就得到了某一维上小于等于那一位的所有位置。
对每一维都扫一遍，最终为 1 的就是每一维都偏序的，所以每一位的偏序数就是 1 的个数。
没看懂的看代码（kk 是维数）:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxn = 1e5 + 10, mod = 1e9 + 7; 
bitset<maxn> b[maxn], tmp;
int a[maxn][10], p[10][maxn];
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> a[i][j];
            p[j][i] = i;
        }
    }
    for (int d = 1; d <= k; d++) sort(p[d] + 1, p[d] + n + 1, [=](int x, int y) { return a[x][d] < a[y][d]; });
    for (int i = 1; i <= n; i++) b[i].set();
    for (int d = 1; d <= k; d++) {
        tmp.reset();
        int id = 1;
        for (int i = 1; i <= n; i++) {
            while (id <= n && a[p[d][id]][d] <= a[p[d][i]][d]) tmp[p[d][id]] = 1, id++;
            if (1 <= p[d][i] && p[d][i] <= n) b[p[d][i]] &= tmp;
        }
    }
    for (int i = 1; i <= n; i++) cout << b[i].count() - 1 << endl;
    return 0; 
}

P3810 【模板】三维偏序（陌上花开）

注意到是 n≤105n\le10^5，bitset 开不下，需要分组 bitset，就是将 nn 分成多个长为 BB 的段，对每一段做上面的操作，所以 bitset 只需要开 BB 的大小。
code:
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxb = 1e4 + 10, maxn = 1e5 + 10, mod = 1e9 + 7; 
bitset<maxn> b[maxb], tmp;
int a[maxn][5], ans[maxn], p[5][maxn], cnt[maxn];
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int n, k, len = 10000;
    cin >> n >> k;
    k = 3;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> a[i][j];
            p[j][i] = i;
        }
    }
    for (int d = 1; d <= k; d++) sort(p[d] + 1, p[d] + n + 1, [=](int x, int y) { return a[x][d] < a[y][d]; });
    for (int l = 1; l <= n; l += len) {
        int r = min(l + len - 1, n);
        for (int i = 1; i <= r - l + 1; i++) b[i].set();
        for (int d = 1; d <= k; d++) {
            tmp.reset();
            int id = 1;
            for (int i = 1; i <= n; i++) {
                while (id <= n && a[p[d][id]][d] <= a[p[d][i]][d]) tmp[p[d][id]] = 1, id++;
                if (l <= p[d][i] && p[d][i] <= r) b[p[d][i] - l + 1] &= tmp;
            }
        }
        for (int i = 1; i <= r - l + 1; i++) ans[l + i - 1] = b[i].count() - 1;
    }
    for (int i = 1; i <= n; i++) cnt[ans[i]]++;
    for (int i = 0; i < n; i++) cout << cnt[i] << endl;
    return 0; 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...