bitset介绍与使用

bitset

bitset数据类型，在\<bitset>头文件中，是一种类似于数组和字符串的数据结构。

bitset的每一个单位所占内存大小为1个位，是int类型的\frac{1}{32}，同时还支持一些位运算，比bool还好用。

可以把bitset当成一个长度可自定义的二进制数，这样位运算就能想通了。

构造函数

bitset是一个类似数组的变量，所以定义是必须是bitset\<size>的形式，即要声明数组大小，支持下标访问！（下标同数组，从0到size-1）

定义一个bitset类型变量的方法有以下几种

//不可以不声明size
bitset a;   //报错

//无参，默认值0
bitset<size> a;

//整型数b为参数，那么a的值就是b的二进制表示，靠右对齐，左边补0
bitset<size> a(int b);

//字符串string类型b为参数，b中只能有'0'和'1'，否则抛出异常，靠右对齐，左边补0
bitset<size> a(string b);

//字符串数组为参数，同string
bitset<size> a(char[] b);

//类似于字符串是因为可以把bitset当成字符串直接输出      注意bitset的输出是按a[n-1]-a[0]顺序输出的，与string和字符数组相反
cout << a << endl;

操作符

支持 ~、&、|、^、<<、>>、&=、|=、^=、<<=、>>=还有==、!=等操作符。位运算就是把bitset当成二进制数进行按位运算。

各操作符的时间复杂度暂定。。。

就不举例子了。

函数

bitset支持一些有用的函数

    bitset<size> a;

    //count()函数用来求bitset中1的位数
    cout << a.count() << endl;

    //size()函数求bitset的大小
    cout << a.size() << endl;

    //test(i)函数对下标i进行检查，下标是否合法（越界抛出异常），以及该下标出的值为0还是1
    cout << a.test(0) << endl;

    //any()函数检查是否有1
    cout << a.any() << endl;

    //none()函数检查是否没有1
    cout << a.none() << endl;

    //all()函数检查是否全为1
    cout << a.all() << endl;

类型转化

bitset只支持三种类型转化: string, unsigned long, unsigned long long. 注意bitset存的是二进制数，转化为整数时会自动进行转化。

bitset<size> a;

string s = a.to_string();

unsigned long b = a.to_ulong();

unsigned long long c = a.to_ullong();

NC17193 简单瞎搞题

一共有 n个数，第 i 个数是 xi, xi 可以取 [li , ri] 中任意的一个值。设 S = \sum{{x_i}^2}, 求 S 种类数。
分组背包问题。即每组物品里只能选出一个放入背包，且必须选一个，求最终背包的可能取值。
用一般的背包思路解题的话：
f[i][j]\ \ |= f[i-1][j-x[i]]
但是这样的话时间复杂度太大了，O(n*max(S)*n)
考虑状态压缩，用bitset来存储每一层每个数的01情况。
f[i]\ \ |=\ f[i-1]\ << x[i]^{2}
借助于bitset方便的位运算来大大减小时间复杂度！

#include <bitset>
#include <iostream>
using namespace std;
int n;
int l[105], r[105];
bitset<1000005> f[105];
int main(){
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i=1;i<=n;i++)    cin >> l[i] >> r[i];
    f[0][0] = 1;
    for (int i=1;i<=n;i++){
        for (int j=l[i];j<=r[i];j++){
            f[i] |= f[i-1]<<(j*j);
        }
    }
    cout << f[n].count();
    return 0;
}