哈希表
哈希表是一种根据关键字key来访问值value的一种数据结构，本质是数组加哈希函数。数组不难理解，哈希函数的作用就是将哈希表的某个key作为输入，然后经过一系列的运算后，得到数组的某个索引。一种很朴素的思路是，先用key计算出一个很大的数，然后对数组长度取模，从而得到索引。得到索引后就可以通过索引对数组执行插入或查找的操作，因为本质上是通过索引来访问数组，所以哈希表的插入和查找的效率非常高，时间复杂度都是O(1)。
和离散化的区别是，离散化要求映射有单调性，离散化是一种及其特殊的哈希。
哈希冲突： 不难发现哈希函数是整个哈希表的关键。所以为了更好的性能，我们希望在尽可能短的时间内，相同的key经过哈希函数的计算，可以得到相同的索引，不同的key经过哈希函数的计算，可以得到不同的索引，但在实际中往往事与愿违，不同的key小概率会计算出相同的索引，这就是哈希冲突（collision），几乎所有的哈希函数都存在这个问题。
基本方法： 开放寻址法，拉链法。
如哈希函数 。一般用 mod 取，哈希表的大小最好是选择一个大的质数，并且最好不要和2的整数幂接近
拉链法：给定一个槽，槽的每个位置上是一条拉链(链表)。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003; // 取距离 10^5 接近的质数
// 开一个槽 h， h[k] 表示槽 h 中 第 k 个拉链的头结点
int h[N], e[N], ne[N], idx; // e[N], ne[N], idx 是链表
void insert(int x) {
int k = (x % N + N) % N;// 目的是让余数为正
e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}
bool find(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x) return true;
}
return false;
}
int main() {
int n; cin >> n;
memset(h, -1, sizeof h); //将槽先清空 空指针一般用 -1 来表示 // 在 cstring 中
while(n --){
char op[2];
int x; cin >> op >> x;
if(*op == 'I') insert(x);
else{
if(find(x)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
开放寻址法：
数组大小一般是输入的 2-3 倍才比较好。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2 * 1e5 + 3, null = 0x3f3f3f3f;// 比 10^9 稍大
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; cin >> n;
memset(h, 0x3f, sizeof h);// 一般只设 0 或 -1，因为是按字节分配的。
while(n --) {
char op[2];
int x; cin >> op >> x;
int k = find(x);
if(*op == 'I') h[k] = x;
else{
if(h[k] != null) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}
字符串哈希：
字符串前缀哈希法：
str = "abcd"
h[0] = 0(特殊), h[1] = "a" 的哈希, h[2] = "ab" 的哈希, h[3] = "abc" 的哈希
方法：将字符串看做 进制的数，再取余。如
预处理：h[i]=h[i-1]*p+str[i]
经验值：取 ，一般不会出现冲突。
字符串哈希的作用：已知字符串前缀哈希，可以求得任一子串的哈希 ，可以快速判断两段子字符串是否相等。
技巧，用 unsigned long long ，它会溢出，溢出就相当于取余了。
#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int N = 100010， P = 131;
char str[N];
ull h[N], p[N]; // p 用于存储 p^n
ull get(int l, int r){
return h[r] - h[l-1] * p[r - l + 1];
}
int main() {
int n, m; cin >> n >> m;
cin >> str + 1;
p[0] = 1;
for(int i = 1; i <= n; i ++){
p[i] = p[i-1] * P;
h[i] = h[i - 1] * P + str[i];
}
while(m --){
int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
if(get(l1, r1) == get(l2, r2)) puts("YES");
else puts("NO");
}
}
// 最长回文子串
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e6 + 5, P = 131;
typedef unsigned long long ull;
ull hl[N], hr[N], p[N];
char str[N];
ull get(ull h[], int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
int T = 1; // case: i
while(cin >> str + 1, strcmp(str + 1, "END")){
int len = strlen(str + 1);
for(int i = 2 * len; i >= 0; i -= 2){
str[i] = str[i / 2];
str[i - 1] = 'z' + 1; // abca -> a#b#c#a
}
len *= 2, p[0] = 1;
for(int i = 1, j = len; i <= len; i ++, j --){
p[i] = p[i - 1] * P;
hl[i] = hl[i - 1] * P + str[i];
hr[i] = hr[i - 1] * P + str[j];
}
int res = 0;
for(int i = 1; i <= len; i ++){
// 枚举每个字符作为中点, 共枚举 len 个中点
int l = 0, r = min(i - 1, len - i);
while(l < r){ // 对半径进行二分
int mid = l + r + 1 >> 1; // 如果子串 str[i-mid, i-1] 和 str[i+1, i+mid] 哈希相等, 则扩大半径
if(get(hl, i - mid, i - 1) == get(hr, len - (i + mid) + 1, len - (i + 1) + 1)) l = mid;
else r = mid - 1;
}
//查找过程中子串长度一定是奇数，因为是选中心往两边扩半径
//两种情况:如 a#b#a#a#c 中 a#b#a 和 #a#a# 半径都是 2，但实际串长一个为 3， 一个为 2。看边界字符是否是 #，不是则加 1
//边界是 # 的，中心不一定是 #，在长度为 3 的字符串中会有例外，b#a#c 中，#a# 半径为 1，实际串长为 1。长度为 3 的单独考虑后，可以只判断中心是否是 #
if(str[i - l] <= 'z') res = max(res, l + 1); // 看边界字符是否是 #，不是则加 1
else res = max(res, l);
}
printf("Case %d: %d\n",T ++ , res);
}
}
STL
// vector, 变长数组， 倍增的思想：
// size(), empty() 所有容器都有
// clear() 清空
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
vector<int> a;
a.size(); a.empty(); // 是所有 STL 均有的函数, 时间复杂度 O(1)
a.push_back(); a.pop_back();
a.clear();
a.front(); a.back();
a.begin(); a.end();
for(vector<int>::iterator i = a.begin(); i != a.end(); i ++)
cout << *i << endl;
// for(auto i = a.begin(); i != a.end(); i ++) // 可用 auto
vector<int> b(10);
vector<int> b(10, 3);
// 支持比较运算，按字典序比较
vector<int> c(4, 3), b(3, 4); // a < b == true
pair<int, string>p; // 支持比较运算，按字典序比较
p.first; p.second;
p = make_pair(10, "liang");
}
string: substr(), c_str()
size(), length(), empty(), clear()
s += 'c', s += "liang"
s.substr(begin_index, length); s.substr(begin_index);
s.c_str();
queue:
push()
front()
pop()
back()
size(), empty() // queue 没有 clear()
q = queue<int>();
priority_queue: // 默认是大根堆
push() // 没有 clear()
top()
pop()
stack:
push(), pop(), top(), empty() // 无 clear()
deque: // 加强版 vector， 效率低不建议使用
clear()
empty()
size()
front(), back(), push_back(), pop_back()
push_front(), pop_front()
begin(), end(), 随机存取
// set, map, multiset, multimap: 基于红黑树(AVL的一种)，动态维护有序序列，find() log n
增删改查复杂度 O(log n)
set: 包括 set 和 multiset
size/empty/clear/size
begin/end 支持 ++ 和 -- 前驱和后继操作
insert/erase 1. 输入 x，删除所有x；2. 输入迭代器，删除这个迭代器
find 返回迭代器，不存在返回 end())/count
lower_bound(x) // 大于等于 x 的最小数的迭代器
upper_bound(x) // 大于 x 的最小数的迭代器
map: 包扩 map 和 multimap
size/empty/clear/begin/end
insert() 插入的是一个 pair
erase() 参数是 pair 或迭代器
find(key)
像用数组一样用 map，时间复杂度 O(log n)
lower_bound(x)
upper_bound(x)
set<int> q; //以int型为例 默认按键值升序
set<int,greater<int>> p; //降序排列
int x;
q.insert(x); //将x插入q中
q.erase(x); //删除q中的x元素,返回0或1,0表示set中不存在x
q.clear(); //清空q
q.empty(); //判断q是否为空，若是返回1，否则返回0
q.size(); //返回q中元素的个数
q.find(x); //在q中查找x，返回x的迭代器，若x不存在，则返回指向q尾部的迭代器即 q.end()
q.lower_bound(x); //返回一个迭代器，指向第一个键值不小于x的元素
q.upper_bound(x); //返回一个迭代器，指向第一个键值大于x的元素
q.rend(); //返回第一个元素的的前一个元素迭代器
q.begin(); //返回指向q中第一个元素的迭代器
q.end(); //返回指向q最后一个元素下一个位置的迭代器
q.rbegin(); //返回最后一个元素
set<int,greater<int>> p; //降序排列, 默认是升序
unordered_set, unordered_map: 基于hash表
与上类似，不过增删改查复杂度 O(1)
不支持 lower_bound() 和 upper_bound()
不支持迭代器的 ++, -- (即和排序有关的操作不支持)
不支持和排序相关的操作
bitset: 压位
bitset<10000> S;
支持所有位运算，~, &, |, ^, >>, <<, ==, !=, []
size() 多少位
count() 返回 1 的个数
test(index) 判断 S[index] 处是 0 还是 1， 1 则返回 true， 0 则返回 false
any() 判断 S 是否至少有一个 1
none() 是否全为 0
set() 把所有位置 1
set(k) 第 k 位置 1
set(k, v) 将第 k 位变成 v
reset() 所有位变 0
flip() ~S: 所有位取反
flip(k) 第 k 位取反
to_string()
// bitset常用构造函数有四种：用字符串构造时，字符串只能包含 ‘0’ 或 ‘1’ ，否则会抛出异常。
bitset<4> bitset1; //无参构造，长度为４，默认每一位为０
bitset<8> bitset2(12); //长度为８，将12转换成二进制保存到后面，前面用０补充
string s = "100101";
bitset<10> bitset3(s); //长度为10，前面用０补充
char s2[] = "10101";
bitset<13> bitset4(s2); //长度为13，前面用０补充
// 注意：biset里十进制数进来以后直接用cout输出是正常的二进制。
bitset<8> bitset2(12);
cout << bitset2 << endl; //00001100
// 但是实际上里面的二进制是倒序的。如果循环从0位输出到最后一位
for (int i=0;i<8;++i) cout<<b[i]; //00110000
// 在进行有参构造时，若参数的二进制表示比bitset的size小，则在前面用０补充；若比bitsize大，参数为整数时取后面部分，参数为字符串时取前面部分
bitset<2> bitset1(12); //12的二进制为1100（长度为４），但bitset1的size=2，只取后面部分，即00
string s = "100101";
bitset<4> bitset2(s); //s的size=6，而bitset的size=4，只取前面部分，即1001
char s2[] = "11101";
bitset<4> bitset3(s2); //与bitset2同理，只取前面部分，即1110
// 类型转换
bitset<8> foo ("10011011");
string s = foo.to_string(); //将bitset转换成string类型
unsigned long a = foo.to_ulong(); //将bitset转换成unsigned long类型
unsigned long long b = foo.to_ullong(); //将bitset转换成unsigned long long类型
cout << s << endl; //10011011
cout << a << endl; //155
cout << b << endl; //155
Q.E.D.
