acwing笔记

基础知识

快速排序

/**
 * @brief: 快速排序: 递归，分治
 * @time cpl: O(nlog n)
 * @space cpl: O(1)
 * @trouble：
 **/
template <typename type>
void quick_sort_helper(type *arr, int start, int end);

template <typename type>
int partition(type *arr, int start, int end);

template <typename type>
void quick_sort(type *arr, int size)
{
    quick_sort_helper(arr, 0, size-1);
}

template <typename type>
void quick_sort_helper(type *arr, int start, int end)
{
    if (start > end) return;

    int pivotIndex = partition(arr, start, end);
    quick_sort_helper(arr, start, pivotIndex - 1);
    quick_sort_helper(arr, pivotIndex + 1, end);
}

template <typename type>
int partition(type *arr, int start, int end)
{
    int l = start, r = end, pivot = arr[start];
    type tmp;

    while (true)
    {
        while (arr[l] <= pivot)
        {
            l ++;
            if(l == r) {break;}
        }

        while (arr[r] > pivot)
        {
            r--;
            if(l == r) {break;}
        }

        if(l >= r)
        {
            break;
        }
        else
        {
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }
    }

    tmp = arr[start];
    arr[start] = arr[r];
    arr[r] = tmp;
    return r;
}

归并排序

/**
 * @brief: 归并排序: 递归，分治
 * @time cpl: O(nlog n)
 * @space cpl: O(n)
 * @trouble：
 **/
template <typename type>
void merge_helper(type *arr, type *tmp, int start, int mid, int end);

template <typename type>
void merge_sort_helper(type *arr, type *tmp, int start, int end);

//容易出错传入end = size
template <typename type>
void merging_sort(type *arr, int size)
{
    type tmp[size];
    merge_sort_helper(arr, tmp, 0, size-1);
}

template <typename type>
void merge_two_array(type *arr, type *tmp, int start, int mid, int end)
{
    int i = start, j = mid + 1;
    int m = mid, n = end;
    int k = 0;
    while(i<=m && j<=n)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i<=m)    tmp[k++] = arr[i++];
    while (j<=n)    tmp[k++] = arr[j++];
    for(i = 0; i<k; i++)    arr[start+i] = tmp[i];
}

template <typename type>
void merge_sort_helper(type *arr, type *tmp, int start, int end)
{
    if(end <= start) return;
    int mid = start + (end -start)/2;
    merge_sort_helper(arr, tmp, start, mid);
    merge_sort_helper(arr, tmp, mid+1, end);
    merge_two_array(arr, tmp, start, mid, end);
}

二分查找

template<typename type>
int bip_find(const type num[], const type& target, int start, int end){
    int l = start, r = end;
    while(l <= r){
        int mid = l + (r - l) / 2;
        if(num[mid] > target){
            r = mid - 1;
        }else if(num[mid] < target){
            l = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

基础数据结构

数组模拟单链表

// head存储链表头，idx表示当前用到了哪个节点, e[]存储节点的值，ne[]存储节点的next指针
const int N = 10010;

int head = -1, idx = 0, e[N], ne[N];

// 头部插入节点
void insert(int a){
    e[idx] = a; ne[idx] = head; head = idx; idx++;
}

// 删除头节点
void remove(){
    head = ne[head];
}

// 遍历
for(int i = head; i != -1; i = ne[i]){
    cout << e[i] << " ";
}

trie字符串统计

const int N = 10010; // > 最长字符串长度
int son[N][26], cnt[N], idx;

void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p]++;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

堆模板

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

// 添加： 尾插， 尾上升。
// 删除堆顶：首尾互换，尾删除，首下沉

搜索和图论

邻接表数组实现

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], idx, e[N], ne[N];

idx = 0; memset(h, -1, sizeof h);

void add(int a, int b){z
    e[idx] = b, ne[idx] = h[a], h[a] = idx, idx++;
}

dfs

void dfs(int u){
    used[u] = true;
    for(int i=h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!used[j]) dfs([j]);
    }
}

bfs

queue<int> q;
used[1] = true; q.push(1);

while(!q.empty()){
    int t = q.front(); q.pop();
    for(int i = h[t]; i != -1; i = ne[i]){
        int j = e[i];
        if(!used[j]){
            used[j] = true;
            q.push(j);
        }
    }
}

kmp

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

最短路

• 最短路

  • 单源最短路

    • 边权全正

      • 稠密图: 朴素Dijkstra（n^2）, 每次从【未求出最短路径的点】中去除距离起点距离最小的点，并用这个点去更新【未求出最短路径的点】的距离。
      • 稀疏图: 堆优化Dijkstra（mlogn），【未求出最短路径的点】用小根堆存储

    • 存在负边：

      • Bellman-Ford（nm）：对所有的边进行n-1轮松弛操作
      • SPFA（m - nm）: 由于松弛操作中只有上一节点有变化，当前节点才需要更新，所以用队列记录有变化的节点而无需遍历所有节点。
        • 求最短路径：
        • 判负环：增加一个修改次数计数数组，如果某个节点计数 > n,则说明存在负环。

  • 多源最短路

    • Floyd

最小生成树

• Prim：循环n-1次，每次从 【未并入生成树中的点集】中找出一条距离 【已并入生成树中的点集】的最小边

  • 稠密图(n^2)：朴素版,
  • 稀疏图(mlogn)：堆优化版, 麻烦，基本不用，不如直接用Kruskal.

• Kruskal(mlogm)

二分图

• 染色法（m+n）：对每个点进行一次dfs并交替染色，直至有矛盾出现
• 匈牙利算法( < mn)：

数学知识

质数， 约数， 欧拉函数，

动态规划dp

背包问题

背包体积V， n个物体，体积v_i, 价值w_i， 求背包最大价值

1. 01背包： 每个物品仅能取一次
2. 完全背包：每个物品可取无限次
3. 多重背包：每个物品可用限制次数不一样
4. 分组背包：物品分组，每一组中只能取一个物品

贪心

1. 区间选点: 求最少点，落遍所有区间 | 右端点排序，取右端点，每次新的区间左端点在上一区间右端点右侧（即上一点够不着当前区间），则计数++
2. 最大不相交区间数量：求最大区间数，彼此不相交 | 和上一问题完全一致
3. 区间分组：求最少分组数，组内区间彼此不相交 | 左端点排序，借助小根堆，新区间每次查询能否放在已有的组里面，不能则成为新的组
4. 区间覆盖：求最少区间数，覆盖指定区间 | 左端点排序， 每次取最长区间
5. 合并果子：类似合并石子（相邻合并），但可任取两两合并 | 每次取最小的两堆合并