发表算法 / 数论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)$

阅读更多
发表小说 & 随笔 / 未来24 分钟读完 (大约3638个字)

凝眉

他和她走下车。站台上熙熙攘攘的人守望在那里。没有人向他们看上一眼。

他们停下脚步，看着列车消失在金色的反光里，只留下无底的空白。

“所以……新见和五反田他们呢？”高桥问道。

“他们？他们不会来了。”他想了想道。“他们来过这里。”

她点了点头。

“走吧。”

他握住她的手。

阅读更多
发表图书馆7 分钟读完 (大约1015个字)

年轻人不讲武德

缘起

健身房的年轻后生不讲武德偷袭马老师，把马保国老师的眼睛给蹭了一下

音译

啊朋友们好啊，我是浑元形意太极门掌门人马保国。

刚才有个朋友，问我马老师发生甚么事了，我说怎么回事，给我发了几张截图。我一看，嗷，原来是左天，有两个年轻人，30多岁，一个体重90多公斤，一个体重80多公斤。塔们说，诶，有一个说是，我在健身房练功，颈椎练坏了，马老师你能不能教教我浑元功法，矮…帮助治疗一下我的颈椎病。我说可以。

阅读更多
发表算法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三大问题：树的最大独立集 树的重心 树的最长路径

阅读更多
Butterfly：添加全局吸底 Aplayer 播放器
发表Hexo6 分钟读完 (大约874个字)

Butterfly：添加全局吸底 Aplayer 播放器

以下步骤在 Butterfly主题上可以正常生效。如果你使用的是其他主题，可以根据情况自行适配。

配置播放器

解决与 hexo-tag-aplayer 的兼容问题

如果你没有安装过 hexo-tag-aplayer 插件，请直接跳过该步骤。

如果你安装过 hexo-tag-aplayer，请在 Hexo 的配置文件中修改以下设置：

阅读更多
关注我

分类

标签

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

最新文章

归档

×