Bitset#

类模板 bitset 表示一个 $N$ 位的固定大小序列。可以用标准逻辑运算符操作 bitset，并将它与字符串和整数相互转换。对于字符串表示和移位操作的列举方向来说，这个序列被当做最低索引元素位于右侧，类似于整数的二进制表示。

$bitset$ 满足可复制构造 ( $CopyConstructible$ ) 及可复制赋值 ( $CopyAssignable$ ) 的要求。

1
template< std::size_t N > class bitset;

模板形参#

$N$ - 要为 $bitset$ 分配存储的位数

eg: bitset<N> ac; 声明一个大小为 $N$ 的bitset，名称为 $ac$

std::bitset 的全部成员函数均为 $constexpr$ ：在常量表达式求值中创建并使用 std::bitset 对象是可能的。(C++23 起) 所以不要试图使用这种方式!!!

常用操作#

count() 返回 $1$ 的个数，时间复杂度为 $O(\frac{n}{w})$ ，其中 $w$ 为机器字长，一般为 $64$ 位，评测机一般为 $32$ 位；有一类似操作__builtin_popcount(val)/__builtin_popcountll(val)，时间复杂度相同（应该是）。
operator<<= operator>>= operator<< operator>> 进行二进制左移和右移
operator= 赋值
operator[] 访问指定的位
operator&= operator|= operator^= operator~ 进行二进制与、或、异或及非

注解#

若某个位集合在编译时大小未知，或者必须在运行时改变其大小，则可代之以使用 std::vector<bool> 或 boost::dynamic_bitset 之类的动态类型。

功能特性测试宏	值	标准	功能特性
__cpp_lib_constexpr_bitset	202207L	(C++23)	使 std::bitset 更 constexpr
__cpp_lib_bitset	202306L	(C++26)	std::bitset 的 std::string_view 接口

示例#

1
#include <bitset>
2
#include <cassert>
3
#include <cstddef>
4
#include <iostream>
5

6
int main()
7
{
8
    typedef std::size_t length_t, position_t; // 提示
9

10
    // 构造函数：
11
    constexpr std::bitset<4> b1;
12
    constexpr std::bitset<4> b2{0xA}; // == 0B1010
13
    std::bitset<4> b3{"0011"}; // C++23 起也可以为 constexpr
14
    std::bitset<8> b4{"ABBA", length_t(4), /*0:*/'A', /*1:*/'B'}; // == 0B0000'0110
15

16
    // 能打印出 bitset 到流：
17
    std::cout << "b1:" << b1 << "; b2:" << b2 << "; b3:" << b3 << "; b4:" << b4 << '\n';
18

19
    // bitset 支持逐位运算：
20
    b3 |= 0b0100; assert(b3 == 0b0111);
21
    b3 &= 0b0011; assert(b3 == 0b0011);
22
    b3 ^= std::bitset<4>{0b1100}; assert(b3 == 0b1111);
23

24
    // 整个集合上的操作：
25
    b3.reset(); assert(b3 == 0);
26
    b3.set(); assert(b3 == 0b1111);
27
    assert(b3.all() && b3.any() && !b3.none());
28
    b3.flip(); assert(b3 == 0);
29

30
    // 单独位上的操作：
31
    b3.set(position_t(1), true); assert(b3 == 0b0010);
32
    b3.set(position_t(1), false); assert(b3 == 0);
33
    b3.flip(position_t(2)); assert(b3 == 0b0100);
34
    b3.reset(position_t(2)); assert(b3 == 0);
35

36
    // 支持下标 operator[]：
37
    b3[2] = true; assert(true == b3[2]);
38

39
    // 其他操作：
40
    assert(b3.count() == 1);
41
    assert(b3.size() == 4);
42
    assert(b3.to_ullong() == 0b0100ULL);
43
    assert(b3.to_string() == "0100");
44
}

Output:

1
b1:0000; b2:1010; b3:0011; b4:00000110

Hash#

普通哈希的优化#

1
template<typename tp1,typename tp2,int N>
2
struct Htb{
3
    static constexpr int M=1e7+19;
4
    int hd[M+3],to[N],ct;
5
    tp1 ed[N];tp2 w[N];
6
    static int hc(ul v){
7
        v^=v<<13,v^=v>>7;
8
        return (v^(v<<17))%M;
9
    }
10
    void ins(tp1 x,tp2 y){
11
        int &p=hd[hc(x)];
12
        ed[++ct]=x,to[ct]=p;
13
        w[p=ct]=y;
14
    }
15
    int count(tp1 x){
16
        for(int i=hd[hc(x)];i;i=to[i])
17
            if(ed[i]==x)return 1;
18
        return 0;
19
    }
20
    pair<tp2,bool>find(tp1 x){
21
        for(int i=hd[hc(x)];i;i=to[i])
22
            if(ed[i]==x)return mkp(w[i],true);
23
        return mkp(tp2(),false);
24
    }
25
    int operator[](tp1 x){
26
        int &p=hd[hc(x)];
27
        for(int i=p;i;i=to[i])
28
            if(ed[i]==x)return i;
29
        ed[++ct]=x,to[ct]=p;
30
        return p=ct;
31
    }
32
    void clear(){while(ct)hd[hc(ed[ct--])]=0;}
33
};

这种多维哈希相对于普通哈希的优点：

内存局部性更好，有助于缓存友好。
$clear$ 操作可以非常高效，只需遍历已有的节点更新 $hd$ 数组
代码中手动维护链表，便于对冲突处理和自定义哈希函数调优

使用方法：

struct hc: $xorshift$ 随机映射，把一个ul类型随机映射到 $0$ ~ $M-1$ 中的一个随机数
struct ins类似邻接表插入
count是否找到
pair<tp2,bool> 第一位查询得到的值，bool是否找到了
operator[] 用于寻找第一维的标号，未找到则创建一个

缺点:

由于是 $xorshift$ ，在 $cf$ 上写依然会被叉
第一维不能传 $string$ ，可以另写static ul hc(string s) {}

Hash的再优化#

为了解决上述 $Hash$ 的缺点，我们可以引入随机 $Hash$ ，同时引入 $Pbds$ 库中封装好的gp_hash_table。

1
struct myhash {
2
  static uint64_t hash(uint64_t x) {
3
    x += 0x9e3779b97f4a7c15;
4
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
5
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
6
    return x ^ (x >> 31);
7
  }
8
  size_t operator()(uint64_t x) const {
9
    static const uint64_t SEED =
10
        chrono::steady_clock::now().time_since_epoch().count();
11
    return hash(x + SEED);
12
  }
13
  size_t operator()(pair<uint64_t, uint64_t> x) const {
14
    static const uint64_t SEED =
15
        chrono::steady_clock::now().time_since_epoch().count();
16
    return hash(x.first + SEED) ^ (hash(x.second + SEED) >> 1);
17
  }
18
};
19
uint64_t string_hash(const string &s) {
20
  const uint64_t BASE = 131;
21
  uint64_t h = 0;
22
  for (char c : s) {
23
    h = h * BASE + c;
24
  }
25
  return h;
26
}
27
#define mymap __gnu_pbds::gp_hash_table

定义方法#

mymap<int, int, myhash> dic;

mymap<int, null_type, myhash> dic;

unordered_map<int, int, myhash> dic;

第二维表示存或者不存，若为null_type则不关心是否存值。

Pbds#

介绍#

什么是__gnu_pbds? $Policy$ $based$ $data$ $structures$ ！简称~~平板电视~~ $pbds$ 。在使用 $pbds$ 前，你需要：

1
#include<ext/pb_ds/assoc_container.hpp>
2
#include<ext/pb_ds/tree_policy.hpp>//用tree
3
#include<ext/pb_ds/hash_policy.hpp>//用hash
4
#include<ext/pb_ds/trie_policy.hpp>//用trie
5
#include<ext/pb_ds/priority_queue.hpp>//用priority_queue
6
using namespace __gnu_pbds;

这么长？没事，有更简单的：

1
#include<bits/extc++.h>
2
using namespace __gnu_pbds;

$Pbds$ 中的所有内容均不在头文件#include <bits/stdc++.h>中，也不再 $std$ 命名空间中。

pbds::hash#

上面已经介绍过。

P1333 瑞瑞的木棍

该题使用 $Pbds$ 中自带的 $Hash$ ，时间复杂度仅为 $O(n)$ 。

tree#

平衡树：使得集中的元素始终保持有序，并且支持快速插入和删除某个数，和快速索引排名为 $x$ 的数，作增删改查操作。

显然， $set$ 无法实现快速索引某个数的排名和快速索引第 $k$ 位数。

通俗且不严谨的说， $set$ 不像数组一样拥有“下标”，而 $pbds$ 库中的平衡树既有 $set$ 的功能，也有数组的下标。

平衡树的tag#

rb_tree_tag：红黑树
splay_tree_tag：伸展树
ov_tree_tag：有序向量树（不建议使用）

一般推荐使用rb_tree_tag

定义方式#

1
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tr;

重要函数#

tr.find_by_order(k) 返回下标为 $k$ 的对象的指针
tr.order_of_key(val) 返回小于等于 $val$ 的对象的个数
tr.lower(upper)_bound(val) 返回大于等于（大于） $val$ 的数的对象的指针
tr.insert(val) 向 $tr$ 中插入 $val$
A.join(B) 将 $B$ 整个并入 $A$
tr.size 查询 $tr$ 的大小
tr.erase(tr.lower_bound(val)) 删除 $tr$ 中大于等于 $val$ 的值
tr.erase(val) 删除 $tr$ 中值为 $val$ 的元素

创建multiset#

一般来说有如下两种方法：

插入时左移 $20$ 位，并加上一个独一无二的值，删除时右移 $20$ 位取出
在创建时，将 less<int> 改为 less_equal<int> 方便但非常不推荐!!!

priority_queue#

堆的tag#

pairing_heap_tag：使用配对堆（ $Pairing Heap$ ）实现。配对堆是一种具有良好理论性能和实际性能的堆结构，通常在实践中表现优异。
binary_heap_tag：使用二叉堆（ $Binary Heap$ ）实现。二叉堆是一种经典的堆结构，通常用于实现优先队列。
binomial_heap_tag：使用二项堆（ $Binomial Heap$ ）实现。二项堆是一种支持高效合并操作的堆结构。
rc_binomial_heap_tag：使用放宽的二项堆（ $Relaxed Binomial Heap$ ）实现。这种堆结构在二项堆的基础上进行了优化，以提高某些操作的性能。
thin_heap_tag：使用瘦堆（ $Thin Heap$ ）实现。瘦堆是一种专门为 $Dijkstra$ 算法设计的堆结构，适用于图算法中的优先队列。

一般推荐使用pairing_heap_tag

定义方式#

priority_queue<int, less<int>, pairing_heap_tag> q1, q2;

重要函数#

q1.push(val)
a1.size()
q1.pop()
q1.join(q2);
q1.empty();

提示#

使用 $Pbds$ 库中的priority_queue时，由于和 $std$ 库中的priority_queue重名，会报错，应当主动声明命名空间。