小花生

study & life record.

算法知识合集

发表于 分类于 ，

记录目前接触过的算法。

基础算法+数据结构

二分

1
2
3
4
5
6
7
8
9
10
11
12
int b_find(int l, int r, int x){
    if(l == r){
        if(a[l] == x) return l;
        return -1;
    }

    int mid = l + r >> 1;
    if(a[mid] >= x) r = mid;
    else l = mid + 1;

    return b_find(l, r, x);
}

查找的是大于等于x的最小数的位置。

离散化

  • 去重离散化C++

    1
    2
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    1
    2
    3
    int to_find(int x) {
        return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
    } // 映射到1，2，3...

  • 映射离散化

ST表

​ 倍增思想。

​ ST 表是用于解决 可重复贡献问题 的数据结构。，预处理时间复杂度O(nlogn)，查询O(1)。

​ st[i][j]表示第 i 个数开始 $2^j$​ 个数中的最值。

1
2
3
4
5
6
7
8
9
10
void initlog() {
    for (int i = 2; i < N; i++)log_2[i] = log_2[i >> 1] + 1;
}
void initst() {
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
        }
    }
}
1
2
3
4
int query(int l, int r){
    int x = log_2[r - l + 1];
    return max(st[l][x], st[r - (1 << x) + 1][x]);
}

树状数组

单点修改 区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
int lowbit(int x) { return x & -x; }

void add(int u, int k) {
    for (int i = u; i <= n; i += lowbit(i))
        c[i] += k;
}

int query(int u) {
    int res = 0;
    for (int i = u; i > 0; i -= lowbit(i))
        res += c[i];
    return res;
}

区间修改 单点询问

1
2
3
// 前置函数如上 利用差分原理
add(l, x), add(r + 1, -x);
query(x);

线段树（求和模板）

初始准备（注意开四倍的数组）

1
2
const int N = 1e5 + 10;
int tr[N << 2], mark[N << 2];

上传与下传

1
2
3
4
5
6
7
8
9
10
11
12
void push_up(int u) {
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
}

void push_down(int u, int len) {
    if (len <= 1) return;
    tr[u << 1] += mark[u] * (len - len / 2);
    mark[u << 1] += mark[u];
    tr[u << 1 | 1] += mark[u] * (len / 2);
    mark[u << 1 | 1] += mark[u];
    mark[u] = 0;
}

建树

1
2
3
4
5
6
7
void build(int u = 1, int cl = 1, int cr = n) {
    if (cl == cr) return void(tr[u] = a[cl]);
    int mid = cl + cr >> 1;
    build(u << 1, cl, mid);
    build(u << 1 | 1, mid + 1, cr);
    push_up(u);
}

区间修改

1
2
3
4
5
6
7
8
9
10
11
void update(int l, int r, int k, int u = 1, int cl = 1, int cr = n) {
    if (l <= cl && cr <= r) {
        tr[u] += k * (cr - cl + 1);
        return void (mark[u] += k);
    }
    push_down(u, cr - cl + 1);
    int mid = cl + cr >> 1;
    if (mid >= l) update(l, r, k, u << 1, cl, mid);
    if (mid < r) update(l, r, k, u << 1 | 1, mid + 1, cr);
    push_up(u);
}

区间查询

1
2
3
4
5
6
7
8
int query(int l, int r, int u = 1, int cl = 1, int cr = n) {
    if (l <= cl && cr <= r) return tr[u];
    push_down(u, cr - cl + 1);
    int mid = cl + cr >> 1, ans = 0;
    if (mid >= l) ans += query(l, r, u << 1, cl, mid);
    if (mid < r) ans += query(l, r, u << 1 | 1, mid + 1, cr);
    return ans;
}

并查集

​ 查询操作

1
2
3
int find(int x){ // 返回 x 的祖宗节点 + 路径压缩
    return p[x] == x ? x : p[x] = find(p[x]);
}

​ 合并操作

1
p[find(a)] = find(b);

（可同时维护集合元素个数，距离祖宗距离等信息）

图论

最短路

1. Dijkstra（堆优化版）

“每次更新距离起点dist最短的点作更新”。 $O(mlogm)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// vis数组 标记已经确定的点
// 每加入一个点, 更新所有与其相连的点的dist，若被更新，加入优先队列

priority_queue<PII, vector<PII>, greater<PII>>q;

int dijkstra(int s){
    dist.assign(N, INF);    
    memset(vis, 0, sizeof(vis));
    dist[s] = 0;
    
    q.emplace(0, s);
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        
        if(vis[u]) continue;
        vis[u] = 1;
        
        for(auto &v : g[u]){
            if(dist[v.second] > dist[u] + v.first){
                dist[v.second] = dist[u] + v.first;
                q.emplace(dist[v.second], v.second);
            }
        }
    }
    if(dist[n] == INF) return -1;
    return dist[n];
}

2. Bellman-ford

可处理负权边。最适用于，有边数限制的最短路。(时间复杂度较大，少见) $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int bellman_ford(int s) {
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;

    for (int i = 0; i < k; i++) { // k 为边数的限制
        memcpy(backup, dist, sizeof(dist));
        for (int j = 0; j < m; j++) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            dist[v] = min(dist[v], backup[u] + w);
        }
    }

    if (dist[n] > INF / 2) return -INF;
    return dist[n];
}

3. SPFA

可处理负权边（不含负环）。也可以处理正权边（可能会被卡）

vis记录在队列内的元素。一般$O(m)$ 最大$O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int spfa(int s){
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    
    q.emplace(0, s);
    vis[s] = 1;
    while(!q.empty()){
        auto u = q.front().second;
        q.pop();
        vis[u] = 0;
        
        for(auto &v: g[u]){
            if(dist[v.second] > dist[u] + v.first){
                dist[v.second] = dist[u] + v.first;
             
                if(!vis[v.second]){
                    q.emplace(dist[v.second], v.second);
                    vis[v.second] = 1;
                }
                
            }
        }
    }
    return dist[n];
}

4. Floyd

邻接表存图，可处理负权边，时间复杂度$O(n^3)$

1
2
3
4
5
6
7
8
9
10
11
// 依次将每个点作为中间点作更新

void floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

最小生成树

1.Prim

  • 朴素版$O(n^2)$，一般用于稠密图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int g[N][N]; // 邻接矩阵存图
int dist[N]; // 该点到集合的距离
bool vis[N]; // 标记是否已经在集合中

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    int res = 0; // 存权值之和
    for(int i = 0; i < n; i++)
    {
        int t = -1; // 记录到集合距离最小的点
        for(int j = 1; j <= n; j++)
            if(!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if(dist[t] == INF) return INF;
        res += dist[t];
        vis[t] = 1;

        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}
  • 堆优化版$O(mlogn)$，一般用于稀疏图（X）

（此时用$Kruskal$更方便）

2.Kruskal

$O(mlogm)$，一般用于稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct Edge{
    int a, b, w;
}edges[M];

bool cmp(Edge &x, Edge &y){
    return x.w < y.w;
}

int kruskal(){
    sort(edges, edges + m, cmp);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b) // 如果两点不在同一集合中，加入该边
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

拓扑排序

​ 拓扑排序：将集合内已知的偏序关系整合成全序

具体流程如下：

  • 将所有入度为0的点加入处理队列
  • 将处于队头的点x取出，遍历所有x能到达的点y
  • 对每一个y，处理入度-1
  • y入度为0时，将y加入处理队列
  • 重复以上过程直到队列为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool topo(){
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(!ind[i]) q.emplace(i);
    
    while(!q.empty()){
        int u = q.front();
        q.pop(); cnt++;
        res.emplace_back(u);
        
        for(auto &v : g[u]){
            ind[v]--;
            if(!ind[v])q.emplace(v);
        }
    }
    return cnt == n;
}

LCA

​ Least Common Ancestors 最近公共祖先

树上倍增法：预处理O(nlogn) 每次查询O(logn)

​ f[i][j]表示 i 节点向上走 $2^j$ 层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int u, int fa) {
    for (auto& v : g[u]) if(v != fa) {
        dep[v] = dep[u] + 1;
        f[v][0] = u;
        for (int i = 1; i < M; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        dfs(v, u);
    }
    return;
}

int lca(int x, int y) {
    if (dep[x] < dep[y])swap(x, y);
    // 保证x不高于y
    for (int i = M - 1; i >= 0; i--) if (dep[f[x][i]] >= dep[y])x = f[x][i];
    if (x == y)return x;
    for (int i = M - 1; i >= 0; i--) if (f[x][i] != f[y][i])x = f[x][i], y = f[y][i];
    return f[x][0];
}

Tarjan缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> g[N];
int dfn[N], low[N], timestamp;
int stk[N], top; bool in_stk[N];
int id[N], scc_cnt, siz[N];

void tarjan(int u){
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = 1;
    for(auto &v : g[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(in_stk[v]) low[u] = min(low[u], dfn[v]);
    }
    
    if(dfn[u] == low[u]){
        ++scc_cnt;
        int y;
        do{
            y = stk[top--];
            in_stk[y] = 0;
            id[y] = scc_cnt;
            siz[scc_cnt]++;
        }while(y != u);
    }
}

数学

素数判定

1
2
3
4
5
6
bool is_Prime(int n){
    if(n < 2) return 0;
    for(int i = 2; i <= n / i; i++)
        if(!(n % i)) return 0;
    return 1;
}

埃氏筛

1
2
3
4
5
6
7
8
void Eratosthenes(int n){
    for(int i = 2; i <= n; i++){
        if(!comp[i]){
            primes[cnt++] = i;
            for(int j = i + i; j <= n; j += i)comp[j] = 1;
        }
    }
}
  • 若是质数，加入质数表， 所有倍数判为合数。$O(nloglogn)$

欧拉筛（线性筛）

1
2
3
4
5
6
7
8
9
void Euler(int n){
    for(int i = 2; i <= n; i++){
        if(!comp[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            comp[i * primes[j]] = 1;
            if(!(i % primes[j])) break;
        }
    }
}
  • 若是质数，加入质数表
  • 筛去i的质数倍，直到i成为某质数的倍数

（n只会被最小质因子筛掉）

求所有约数

1
2
3
4
5
6
7
8
9
10
11
vector<int>get_divisors(int n){
    vector<int> res;
    for(int i = 1; i <= n / i; i++){
        if(!(n % i)){
            res.emplace_back(i);
            if(i != n / i) res.emplace_back(n / i);
        }   
    }
    sort(res.begin(), res.end());
    return res;
}

算数基本定理

任意自然数可唯一分解$N=\prod\limits_{i=1}^ka_i^k$

约数个数$\prod\limits_{i=1}^k(a_i+1)$ 约数之和$\prod\limits_{i=1}^k\sum\limits_{j=0}^{a_i}a^j$​

欧几里得算法

1
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}

欧拉函数

欧拉函数：1到n中与n互质的数的个数

$\phi(n)=N(1-\prod\frac 1{p_i})$

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void get_phi(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!comp[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; primes[j] <= n / i; j++){
            comp[i * primes[j]] = 1;
            if(!(i % primes[j])){
                phi[i * primes[j]] = primes[j] * phi[i];
                break;
            }
            phi[i * primes[j]] = (primes[j] - 1) * phi[i];
        }
    }    
}

三个转移情况：

  • i 为质数时$\phi(i)=i-1$
  • i 整除primes[ j ]时，$\phi(i*primes[j]) = primes[j] \times \phi(i)$
  • i 不整除primes[ j ]时，$\phi(i*primes[j]) = (primes[j]-1) \times \phi(i)$

欧拉定理

$$
若a与n互质，则有a^{\phi(n)}\equiv 1(mod\ n)
$$

快速幂

1
2
3
4
5
6
7
8
9
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        k >>= 1; 
        a = a * a % p;
    }   
    return res;
}

$O(\log(k))$ 的时间复杂度计算$a^k\ %p$

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

动态规划

以下v表示volume， w表示worth

01背包

1
2
3
4
5
for(int i = 1; i <= n ;i++){
    for(int j = V; j >= v[i]; j--){ // 逆序遍历
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

完全背包

1
2
3
4
5
for(int i = 1; i <= N; i++){
    for(int j = v[i]; j <= V; j++){ // 顺序遍历
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 二进制优化 + 01背包的处理*/
int cnt = 0;
for(int i = 1; i <= n; i++){
    int a, b, s;
    cin >> a >> b >> s;
    int k = 1;
    while(k <= s){
        cnt++;
        v[cnt] = a * k;
        w[cnt] = b * k;
        s -= k;
        k *= 2;
    }
    if(s > 0){
        cnt++;
        v[cnt] = a * s;
        w[cnt] = b * s;
    }
}

n = cnt;

for(int i = 1; i <= n; i++){
    for(int j = V; j >= v[i]; j--){
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

分组背包

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++){
    for(int j = V; j >= 0; j--){
        for(int k = 0; k < s[i]; k++){
            if(v[i][k] <= j){
                dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
            }
        }
    }
}

多维费用背包问题

简单加循环即可。