HARRIS GREEN HARRIS GREEN

菜单

Harris
发布于 2026-04-06 / 17 阅读
0
0

C++ std::bitset 终极指南与竞赛技巧

bitset 就像一个极其紧凑的 bool 数组，但它最大的杀手锏是支持所有位运算，并且在底层是以 32 位或 64 位整数为一个基本单元进行并行计算的。这意味着对 bitset 的整体操作（如与、或、异或、左移、右移）的耗时只有普通数组的 \frac{1}{64}。

一、 基础语法与声明

首先需要引入头文件：

#include <bitset>
using namespace std;

⚠️ 致命禁忌：bitset 的大小 必须是编译期常量！不能用变量定义大小。

const int N = 100010;
bitset<N> b1;         // 正确：默认全为 0
bitset<1000> b2(255); // 正确：用十进制数字初始化 (255 变成二进制 11111111)
bitset<1000> b3("10110"); // 正确：用二进制字符串初始化

int n; cin >> n;
// bitset<n> b4;      // 🚨 错误！n 不是编译期常量，会报编译错误！

二、 核心成员函数 (Cheat Sheet)

假设我们有 bitset<100> b;

* 状态查询

b.count(): 返回 bitset 中 1 的个数（极其常用，相当于超级快的遍历计数）。

b.any(): 只要有任意一位是 1，返回 true。

b.none(): 如果全都是 0，返回 true。

b.all(): 如果全都是 1，返回 true (C++11)。

* 单点/全盘修改

b.set(): 把所有位都变成 1。

b.set(i): 把第 i 位变成 1。

b.set(i, v): 把第 i 位变成 v（0 或 1）。

b.reset(): 把所有位都变成 0（相当于 memset 清空）。

b.reset(i): 把第 i 位变成 0。

b.flip(): 全部位取反（0 变 1，1 变 0）。

b.flip(i): 第 i 位取反。

* 下标访问与转换

b[i]: 直接访问或修改第 i 位（b[i] = 1;），注意最低位（最右边）是第 0 位。

b.to_string(): 转换成 std::string。

b.to_ullong(): 转换成 unsigned long long (前提是 bitset 没超 64 位，否则会抛出异常)。

三、 降维打击：整体位运算

这是 bitset 存在的最大意义！两组状态数组之间的操作可以直接用运算符完成。

bitset<1000> b1, b2, b3;

b3 = b1 & b2; // 集合交集 (极其快) b3 = b1 | b2; // 集合并集 b3 = b1 ^ b2; // 集合对称差 b3 = ~b1; // 集合取反

// 最神仙的操作：整体移位 b3 = b1 << 5; // 所有状态统一左移 5 位 b3 = b1 >> 3; // 所有状态统一右移 3 位

四、 竞赛经典应用场景

* 01背包的存在性问题 (最经典的 bitset 优化)

问题：有 n 个物品，体积分别为 v_1, v_2, \dots, v_n，求能凑出哪些体积？（N \le 1000, \sum V \le 100000）
传统 DP：O(N \times \sum V) \approx 10^8，可能卡常。
bitset 优化：用 dp[i] 表示体积 i 是否能凑出。

bitset<100005> dp;
dp[0] = 1; // 初始可以凑出体积 0
for (int i = 1; i <= n; i++) {
  // 核心代码只有这一行！
  // 意思是：现在的状态 = 原来的状态并上 (原来的状态全体加上物品       v[i] 的体积)
  dp |= (dp << v[i]);
}
// 最后看 dp[S] 是否为 1 即可

这行 dp |= (dp << v[i]); 会将时间复杂度直接除以 64，0.01 秒瞬间跑完！

* 图论：传递闭包 (Warshall 算法优化)

问题：给定一个有向图，求任意两点间是否可达（连通性矩阵）。
传统 Floyed：O(N^3)。如果 N = 2000，运算量 8 \times 10^9，必然超时。
bitset 优化：用 bitset 存储每个点能到达的点集。

bitset<2005> reach[2005]; // reach[i] 表示点 i 能到达的集合// 初始：如果 i 有一条直达的有向边到 j，则 reach[i][j] = 1
for (int k = 1; k <= n; k++) {
  for (int i = 1; i <= n; i++) {
    if (reach[i][k]) { // 如果 i 能到达中转点 k
       // i 能到达的集合，加上 k 能到达的集合
       reach[i] |= reach[k];
    }
  }
}

原本最内层的循环 for(int j...) 被 |= 这一步位运算直接取代！复杂度降为 O(\frac{N^3}{64})，可以秒过 N=2000 的数据。

* 统计多个集合的交集

问题：有 M 个工人，每个工人掌握某几种技能（总技能库有 N \le 10^5 种）。求某几个工人共同掌握的技能数。
解法：直接将这几个工人的 bitset 取 &，然后 .count()。

bitset<100005> worker[10];
// ... 读入数据，掌握技能 x 则 worker[i].set(x);// 查询工人 1, 2, 3 共同掌握的技能数
int common = (worker[1] & worker[2] & worker[3]).count();

more

构造函数

  • bitset(): 每一位都是 false．
  • bitset(unsigned long val): 设为 val 的二进制形式．
  • bitset(const string& str): 设为 01 串 str．

运算符

  • operator []: 访问其特定的一位．
  • operator ==/operator !=: 比较两个 bitset 内容是否完全一样．
  • operator &/operator &=/operator |/operator |=/operator ^/operator ^=/operator ~: 进行按位与/或/异或/取反操作．
    注意：bitset 只能与 bitset 进行位运算，若要和整型进行位运算，要先将整型转换为 bitset．
  • operator <</operator >>/operator <<=/operator >>=: 进行二进制左移/右移．

此外，bitset 还提供了 C++ 流式 IO 的支持，这意味着你可以通过 cin/cout 进行输入输出．

成员函数

  • count(): 返回 true 的数量．
  • size(): 返回 bitset 的大小．
  • test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查．
  • any(): 若存在某一位是 true 则返回 true，否则返回 false．
  • none(): 若所有位都是 false 则返回 true，否则返回 false．
  • all(): 若所有位都是 true 则返回 true，否则返回 false．
    1. set(): 将整个 bitset 设置成 true．
    2. set(pos, val = true): 将某一位设置成 true/false．
    1. reset(): 将整个 bitset 设置成 false．
    2. reset(pos): 将某一位设置成 false．相当于 set(pos, false)．
    1. flip(): 翻转每一位．（0 ↔1，相当于异或一个全是 1 的 bitset）
    2. flip(pos): 翻转某一位．
  • to_string(): 返回转换成的字符串表达．
  • to_ulong(): 返回转换成的 unsigned long 表达（long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）．
  • to_ullong():（C++11 起）返回转换成的 unsigned long long 表达．

另外，libstdc++ 中有一些较为实用的内部成员函数1：

  • _Find_first(): 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小．
  • _Find_next(pos): 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小．
背包问题九讲 2.0 beta1.2
NICE PICTURE

评论