bitset介绍 std::bitset 是标准库中的一个存储 0/1 的大小不可变容器。严格来讲，它并不属于 STL。 bitset 并不属于 STL，而是一种标准库中的 "Special Container"。事实上，它作为一种容器，也并不满足 STL 容器的要求。说它是适配器，它也并不依赖于其它 STL 容器作为底层实现。——摘自《The C++ Standard Library 2nd Edition》 由于内存地址是按字节即 byte 寻址，而非比特 bit，一个 bool 类型的变量，虽然只能表示 0/1, 但是也占了 1 byte 的内存。 bitset 就是通过固定的优化，使得一个字节的八个比特能分别储存 8 位的 0/1。 对于一个 4 字节的 int 变量，在只存 0/1 的意义下，bitset 占用空间只是其 ，计算一些信息时，所需时间也是其 。 在某些情况下通过 bitset 可以优化程序的运行效率。至于其优化的是复杂度还是常数，要看计算复杂度的角度。一般 bitset 的复杂度有以下几种记法：（设原复杂度为 ）$O(n)$，这种记法认为 bitset 完全没有优化复杂度。$O(n/32)$，这种记法不太严谨（复杂度中不应出现常数），但体现了 bitset 能将所需时间优化至 $1/32$。$O(n/w)$，其中 $w=32$（计算机的位数），这种记法较为普遍接受。$O(n/logw)$，其中 $w$ 为计算机一个整型变量的大小。 当然，vector 的一个特化 vector<bool> 的储存方式同 bitset 一样，区别在于其支持动态开空间，bitset 则和我们一般的静态数组一样，是在编译时就开好了的。 然而，bitset 有一些好用的库函数，不仅方便，而且有时可以避免使用 for 循环而没有实质的速度优化。因此，一般不使用 vector<bool>。使用¶头文件¶ #include <bitset>指定大小¶ bitset<1000> bs; // a bitset with 1000 bits 构造函数¶bitset(): 每一位都是 false。bitset(unsigned long val): 设为 val 的二进制形式。bitset(const string& str): 设为 串 str。运算符¶operator []: 访问其特定的一位。operator ==/!=: 比较两个 bitset 内容是否完全一样。operator &/&=/|/| =/^/^=/~: 进行按位与/或/异或/取反操作。bitset 只能与 bitset 进行位运算，若要和整型进行位运算，要先将整型转换为 bitset。operator <>/<<=/>>=: 进行二进制左移/右移。operator <>: 流运算符，这意味着你可以通过 cin/cout 进行输入输出。成员函数¶count(): 返回 true 的数量。size(): 返回 bitset 的大小。test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。any(): 若存在某一位是 true 则返回 true，否则返回 false。none(): 若所有位都是 false 则返回 true，否则返回 false。all():C++11，若所有位都是 true 则返回 true，否则返回 false。set(): 将整个 bitset 设置成 true。set(pos, val = true): 将某一位设置成 true/false。reset(): 将整个 bitset 设置成 false。reset(pos): 将某一位设置成 false。相当于 set(pos, false)。flip(): 翻转每一位。（相当于异或一个全是 1 的 bitset）flip(pos): 翻转某一位。to_string(): 返回转换成的字符串表达。to_ulong(): 返回转换成的 unsigned long 表达 (long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）。to_ullong():C++11，返回转换成的 unsigned long long 表达。 一些文档中没有的成员函数：_Find_first(): 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小。_Find_next(pos): 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小。应用¶「LibreOJ β Round #…