注：机试以解题为主，优化其次

并查集

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);  //了解核心操作
    return p[x];
}

字符串哈希

P经验值一般取131

typedef unsigned long long ULL;
ULL h[N], p[N];  //h[k]表示字符串前k个字母的哈希值，p[k]存储P^k mod 2^64

p[0] = 1;
for (int i = 1; i <= n; i ++ ){
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P ;
}

//计算字串str[l ~ r]的哈希值
ULL get(int l ,int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

STL简介

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()， 迭代器的++，--

DFS和BFS

//DFS
dfs(int u){
    st[u] = true;  //表示搜过点u

    for (int i = h[u]; i != -1; i = h[i]){  //遍历邻接表
        j = e[i];
        if (st[j] != true) dsf(j);  //深搜
    }
}

//BFS
queue<int> q;
st[1] = true;
q.push(1);

while (q.size() != 0){
    int t = q.front();  //取对头元素
    q.pop()

    for (int i = h[t]; i != -1; i = h[i]){
        int j = e[i];
        if (st[j] != true){  //若没有被访问过则访问并入队
            st[j] = true;
            q.push(j);
        }
    }
}

floyd算法

初始化;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j++ )
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;

void floyd(){
    for (int k = 1; k <= n; k ++ )  //以节点k为中转点是否能得到更小的距离
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

拓扑排序

bool topsort(){
    int hh = 0, tt = -1;

    //d[i]表示节点i的入度
    for (int i = 1; i <= n; i ++ )
        if (d[i] == 0)
            q[ ++ tt] = i;

    while (hh <= tt){
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = h[i]){
            int j = e[i];
            if ( -- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    return tt == n - 1;
}