哈希表
哈希表的作用：把一个比较大的空间，映射到一个比较小的空间。
一般做哈希运算时，取一个质数作为模，会使得冲突的概率降低
哈希表的存储
冲突解决方法
- 开放寻址法
- 拉链法
拉链法代码模板 Acwing - 840 模拟散列表
const int N = 100003;
int h[N], e[N], nxt[N], idx;
void insert (int x) {
int k = (x % N + N) % N;
e[idx] = x;
nxt[idx] = h[k];
h[k] = idx++;
}
bool find (int x) {
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = nxt[i]){
if (e[i] == x) return true;
}
return false;
}
int main (){
int n;
scanf("%d", &n);
memset(h, -1, sizeof(h));
while (n--)
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else {
if (find(x)) puts("Yes");
else puts("No");
}
}
}
开放寻址代码模板 Acwing - 840 模拟散列表
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int find (int x) {
int k = (x % N + N) % N;
while (h[k] != null && h[k] != x) {
k++;
if (k == N) k = 0;
}
return k;
}
int main (){
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof(h));
while (n--)
{
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find(x);
if (*op == 'I') h[k] = x;
else {
if (h[k] != null) puts("Yes");
else puts("No");
}
}
}
注意，memset函数，是按字节来设置值的，上面定义了null为0x3f3f3f3f，这调用memset时，只需要设置为0x3f即可。
特殊的，如果要初始化为0或者-1，则直接设置为0或-1就可以了，因为0的二进制表示是全零（00000000），-1是全1（11111111）。设置1个字节和4个字节是一样的。
字符串哈希
字符串前缀哈希法：对于字符串每个位置作为前缀，求一下其哈希值如，有字符串 s = ABCDE
则求解的哈希数组
h[1] = A 的哈希值
h[2] = AB 的哈希值
h[3] = ABC 的哈希值
…
如何求解一个字符串的哈希值？
将字符串看成一个P进制的数，比如字符串ABCD，我们把A映射为1，B映射为2，C映射为3，D映射为4。则ABCD可以看成一个P进制的数字1234。则ABCD这个字符串的哈希值为
(1 × P^{3} + 2 × P^{2} + 3 × P^{1} + 4 × P^{0 } )mod Q(1×P3+2×P2+3×P1+4×P0)modQ
通常不要把一个字母映射为0，这样会导致重复。比如把A映射为0，则A是0，AA也是0，AAA还是0。
在做字符串哈希时，我们不考虑冲突的情况。我们可以取 P = 131或13331，Q = 264 ,这样在99.99%的情况下是不会出现冲突的可以将h数组的类型取成unsigned long long（64位），这样就无需对264 取模，溢出就直接相当于取模
求解字符串前缀哈希值有什么用？
可以求解任意的子串的哈希值！ 这是使用KMP算法都不好做到的。]可以用于快速判断两个字符串是否相等。（用模式匹配需要至少O(n)，而字符串哈希只需要O(1)）
比如我们要求解字符串S中[L,R]这段子串的哈希值
我们可以先得到h[L-1]的值，以及h[R]的值
先将h[L-1]左移R-L+1位（P进制），让其与h[R]对齐，然后二者相减，便得到了[L,R]区间的子串表示的P进制的数
即 \(h[R] - h[L-1] × P^{R-L+1}\)
并且，在计算字符串S的前缀哈希值时，容易得到如下的递推式
h[i] = h[i - 1] × P + S[i]
STL
C++的STL库中提供了很多的数据结构，包括一些很复杂的数据结构。
-
vector
变长数组，基本思想是倍增（类似于java中的ArrayList）
-
pair
存储一个二元组，二元组的变量类型可以任意
-
string
字符串，常用的函数substr()，c_str()
-
queue
队列，push()，front()，back()，pop()
-
priority_queue
优先队列，本质是个堆。push()，top()，pop()
-
stack
栈。push()，top()，pop()
-
deque
双端队列。可以在队头队尾进行插入删除，并且支持随机访问
-
set，map，multiset，multimap
基于平衡二叉树（红黑树），动态维护有序序列。这些set/map支持跟排序相关的操作，如lower_bound/upper_bound方法，也支持迭代器的++和--，但是其增删改查的时间复杂度是O(logn)。
-
unordered_set，unordered_map，unordered_multiset，unordered_multimap
基于哈希表。这些set和map和上面的set/map类似。但是这些unordered的set/map的增删改查的时间复杂度是O(1)，效率比上面的更快，但不支持lower_bound()和upper_bound()，也不支持迭代器的++和--
-
bitset
压位
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反