发表算法 / 数论4 分钟读完 (大约572个字)

数论：逆元

什么是逆元？

若 $ax \equiv 1 \pmod b$，则称 $x$ 是 $a$ 关于模 $b$ 的逆元，常记做 $a^{-1}$。

上式等价于 $ax + by = 1$，因此，一种求逆元的方法就是利用扩欧解方程 $ax + by = 1$。

显然，逆元不一定存在：其存在的充要条件为 $(a, b) = 1$。

推论：$p$ 是质数，$p$ 不整除 $a$，则 $a$ 模 $p$ 的逆元存在。

阅读更多
发表算法 / 数论6 分钟读完 (大约932个字)

数论：不定方程整数解

欧几里得算法

又称辗转相除法，迭代求两数 gcd。

由 $(a, b) = (a, ka + b)$ 的性质，$\gcd(a, b) = \gcd(b, a\bmod b)$。容易证明这么做的复杂度是 $O(\log n)$。

注意：$\gcd(0, a) = a$。

阅读更多
发表算法2 分钟读完 (大约322个字)

图论：LCA

LCA: Lowest common ancestor 最近公共祖先

倍增求 LCA

预处理向上跳 $2^k$ 步的结果数组 f[k][x]。

求的时候先把两个点跳到一个深度。这里有一个特判，如果重合直接返回这个点。

然后log值从大往小枚举，两个点一起不断向上跳，直至父亲相同，直接返回父节点。

可以 $O(n)$ 预处理log值，把单次查询复杂度降到 $O(常数)$。

复杂度：预处理 $O(n \log n)$，查询 $O(1)$

阅读更多
发表算法8 分钟读完 (大约1135个字)

图论：Tarjan

前置概念

时间戳：搜索时第几个搜索到这个点。如搜索顺序是1->2->3->6，则6的时间戳为4

对于无向图

连通分量：对于图G来的一个子图中，任意两个点都可以彼此到达，这个子图就被称为图G的连通分量（一个点就是最小的连通分量）

最大连通分量：对于图G的一个子图，这个子图为图G的连通分量，且是图G所有连通分量中包含节点数最多的那个，即为G的最大联通分量

阅读更多
发表算法 / 动态规划16 分钟读完 (大约2364个字)

初级动态规划：LIS、LCS、背包

LIS & LCS

P1020 导弹拦截

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n = 0;

int a[N], b[N], s[N], ls[N];
void add(int x, int v) {
    for(; x<=n; x+=x&(-x)) s[x] = max(s[x], v); 
}

int query(int x) {
    int ans = 0;
    for(; x>0; x-=x&(-x)) ans = max(ans, s[x]);
    return ans;
}
int main() {
    //freopen("p1020_1.in", "r", stdin);
    for(; scanf("%d", a+n+1) != EOF; ++n, b[n] = a[n]);
    
    sort(b+1, b+n+1);
    int t = unique(b+1, b+n+1) - (b+1);
    
    for(int i=1; i<=n; ++i) 
        a[i] = lower_bound(b+1, b+t+1, a[i]) - b;
    
    int ans = 0;
    for(int i=n; i>0; --i) {
        int q = query(a[i]) + 1;
        add(a[i], q);
        ans = max(ans, q);
    }
    printf("%d\n", ans);
    
    ans = 0;
    memset(s, 0, sizeof s);
    for(int i=1; i<=n; ++i) {
        int q = query(a[i]-1) + 1;
        add(a[i], q);
        ans = max(ans, q);
    }
    printf("%d\n", ans);
    return 0;
}

P1439 【模板】最长公共子序列

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
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 100010;

int n, b[N], p1[N], p2[N], s[N];

int lowbit(int x) {
    return x&(-x);
}
void add(int x, int v) {
    for(; x <= n; x += lowbit(x)) s[x] = max(s[x], v);
}
int query(int x) {
    int ans = 0;
    for(; x > 0; x -= lowbit(x)) ans = max(ans, s[x]);
    return ans;
}
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%d", p1+i);
    for(int i=1; i<=n; ++i) scanf("%d", p2+i);
    
    for(int i=1; i<=n; ++i) b[p1[i]] = i;
    for(int i=1; i<=n; ++i) p2[i] = b[p2[i]];
    
    int ans = 0;
    for(int i=1; i<=n; ++i) {
        int q = query(p2[i]-1) + 1;
        add(p2[i], q);
        ans = max(ans, q);
    }
    
    printf("%d", ans);
    return 0;
}

0-1 背包

$$
F(i,j)=
\begin{cases}
F(i-1,j)& j \leq w_i\\
\max{F(i-1,j),F(i-1,j-w_i)+v_i}& j > w_i
\end{cases}
$$

注意二维转换成一维的时候，$j$ 要从后向前枚举，因为每次的新结果都是根据上一个结果来求得的，从后向前可避免重复取同一物品。

阅读更多
发表算法7 分钟读完 (大约1092个字)

D2T1：贪心、二分、并查集

一些技巧

常见的贪心技巧

货币使用问题：
尽可能少用，那么我们就先拿面值最大的，依次往下走，最后拿光了即可。

区间调度问题：
工作时间不能重叠，在可选工作中，每次都选取结束时间最早的作为选择，可以使工作量最大。

阅读更多
发表算法 / 动态规划10 分钟读完 (大约1483个字)

搜索与状压 DP

DFS

搜索和DP不分家，几乎所有的DP都能用搜索解决（虽然复杂度可能较劣）。不过，如果实在想不出正解，DFS不失为骗分的好手段。

主要的搜索算法有：

  1. DFS/BFS爆搜
  2. 双向BFS
  3. 启发式搜索（又称A*）
  4. 迭代加深搜索
  5. IDA*（迭代加深+启发式）
  6. 记忆化搜索
  7. 剪枝

重要程度：1,7,6 > 4,3 > 5,2。

阅读更多
发表算法 / 动态规划3 分钟读完 (大约411个字)

高级动态规划：区间、树形

区间 DP

P1880 [NOI1995]石子合并

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 220;

int ans, dp[N][N], n, a[N], s[N];

int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        s[i] = s[i-1] + a[i];
    }
    for(int i=1; i<=n; ++i) {
        s[i+n] = s[i+n-1] + a[i];
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    ans = 0x3f3f3f3f;
    for(int i=1; i<=n; ++i) {
        //printf("%d ", dp[i][i+n-1]);
        ans = min(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    
    memset(dp, 0, sizeof dp);
    for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    ans = 0;
    for(int i=1; i<=n; ++i) {
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    return 0;
}

P1063 能量项链

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
31
32
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 220;

int n, h[N], t[N], dp[N][N];
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &h[i]);
        h[i+n] = h[i];
    }
    for(int i=1; i<2*n; ++i) t[i] = h[i+1];
    
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + h[i] * t[k] * t[j]);
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; ++i) {
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    return 0;
}


P3146 [USACO16OPEN]248 G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int n, dp[300][300], ans = 0;
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &dp[i][i]);
    }
    
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=n; ++i, ++j){
            for(int k=i; k<j; ++k) {
                if(dp[i][k] == dp[k+1][j]) 
                    dp[i][j] = max(dp[i][j], dp[i][k]+1);
            }
            ans = max(ans, dp[i][j]);
        }
    } printf("%d\n", ans);
    return 0;
}

树形 DP

树形DP三大问题：树的最大独立集 树的重心 树的最长路径

阅读更多
关注我

分类

标签

Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Gulp1
Hexo4
LCA1
PB_DS1
PWA1
SSH1
STL2
Vercel1
二分图2
动态规划3
匹配2
单调队列2
博客4
双指针1
图书馆4
图论4
小说8
尺取法1
平衡树1
应用程序1
排序2
数学1
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法23
网络流5
记忆化搜索4
部署3
随笔1

最新文章

归档

×