std::bitset 用法
参考资料 OI-WIKI bitset
使用方法
头文件
#include <bitset>
初始化
bitset <1000> a;
// bitset <n> a; 这样是不可以的,只能支持常量的大小设置,因为是在编译时就开好的
bitset a = bitset(const string& str); // 一个 01 字符串 str
bitset a = bitset(unsigned long val); // 将 val 转换成对应的二进制
运算符
-
operator []
: 访问其特定的一位。 -
operator == !=
: 比较两个 bitset 内容是否完全一样。 -
operator & &= | |= ^ ^= ~
: 进行按位与/或/异或/取反操作。bitset
只能与bitset
进行位运算,若要和整型进行位运算,要先将整型转换为bitset
。 -
operator < > <<= >>=
: 进行二进制左移/右移。 -
operator < >
: 流运算符,这意味着你可以通过 cin/cout 进行输入输出。
成员函数
count()
: 返回true
的数量。-
size()
: 返回bitset
的大小。 -
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()
: 翻转每一位。$0 \leftrightarrow 1$ 相当于异或一个全是1
的bitset
-
flip(pos)
: 翻转某一位。 -
to_string()
: 返回转换成的字符串表达。 to_ulong()
: 返回转换成的unsigned long
表达to_ullong()
:C++11,返回转换成的unsigned long long
表达。
作用
一般用于将时间复杂度的常数降低。
比如原本是 $O(n)$ 的,使用了 bitset
后,可以将低为 $O\left(\dfrac{n}{w}\right)$
经典示例
朴素写法
一般很少用 vector <bool>
因为会非常的慢,而此时就可以用到 bitset
int main() {
int m, n;
cin >> m >> n;
vector <int> f(m + 1);
f[0] = 1;
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
for (int j = m; j >= x; j --) {
f[j] |= f[j - x];
}
}
for (int i = m; i >= 0; i--) if (f[i]) {
cout << m - i << endl;
return 0;
}
return 0;
}
bitset
int main() {
int m, n;
cin >> m >> n;
bitset <21000> f;
f[0] = 1;
for (int i = 0; i < n; i ++) {
int v;
cin >> v;
f |= f << v;
}
// test 函数相当于直接 [] 操作符,只不过多了个越界检查
for (int i = m; i >= 0; i --) if (f.test(i)) {
cout << m - i << endl;
return 0;
}
return 0;
}