作者 青鸟
之前写过好多算法的文章，但是现在主要学习开发，就把之前的做了一个汇总，挑了一些写的还可以的文章或代码，其余的就不展示到Blog上了。
最大流问题#
最大流问题一直是图论中的难点，这里给出Edmonds Karp增广路算法的模板
网络最大流
最大流的模板
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| //最大流问题
//Edmonds Karp增广路算法
#include<iostream>
#include<queue>
#include<algorithm>
typedef long long ll;
const int maxn = 520010;
using namespace std;
int n, m, s, t;
//dis表示每个点的流量，pre用来记录bfs找到的增广路
//vis用在bfs判断这个点走过没有，head用链表的形式来存这个点到下一个的起始点，通过net来形成链表
ll ans,dis[maxn];
int pre[maxn],vis[maxn],flag[2510][2510],tot=1,head[maxn];
//e数组存的是边，to是下一个点，net是链接的其他边，用链表的方式来存
struct node {
int to, net;
ll val;
}e[maxn];
//我们就可以直接使用xor1的方式
//找到对应的正向边和反向边（奇数异或1相当于-1，偶数异或1相当于+1）
inline void add(int u,int v,ll w) {
e[++tot].to = v;
e[tot].val = w;
e[tot].net = head[u];
head[u] = tot;
e[++tot].to = u;
e[tot].val = 0;
e[tot].net = head[v];
head[v] = tot;
}
inline int bfs() {
for (register int i = 1; i <= n; i++) vis[i] = 0;
queue<int> q;
q.push(s);
vis[s] = 1;
dis[s] = 2005020600;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = e[i].net) {
if (e[i].val == 0) continue; //我们只关心剩余流量>0的边
int v = e[i].to;
if (vis[v] == 1) continue; //这一条增广路没有访问过
dis[v] = min(dis[x], e[i].val);
pre[v] = i; //记录前驱，方便修改边权
q.push(v);
vis[v] = 1;
if (v == t) return 1; //找到了一条增广路
}
}
return 0;
}
inline void update() {
int x = t;
while (x != s) {
int v = pre[x];
e[v].val -= dis[t];
e[v ^ 1].val += dis[t];
x = e[v ^ 1].to;
}
ans += dis[t]; //累加每一条增广路经的最小流量值
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
if (!flag[u][v]) {
add(u, v, w);
flag[u][v] = tot;
//flag存下来u，v之间的对应边的编号
}
else e[flag[u][v] - 1].val += w;
//注意减去1，因为tot是反向边的编号
}
while(bfs())update();
cout << ans;
return 0;
}
|
线段树#
线段树是一种工具。她能把一些对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）
1. 线段树的简介#
本质上也是一种牺牲了大量的空间。
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
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| //线段树的模板
#include<iostream>
#define fast std::ios::sync_with_stdio(false);std::cin.tie(0);
using namespace std;
int n,m;
int ans;
const int maxn =5E5 + 7;
int a[maxn];
struct arry{
struct node{
int l,r,num;
}tree[maxn*4];
//build是在开始的时候i建树
void build(int left,int right,int p){
tree[p]={left,right,0};
//判断是不是叶子节点
if(left==right) {
tree[p].num = a[left];
return;
}
int mid=(left+right) >> 1;
build(left,mid,p << 1);
build(mid+1,right,p<< 1 | 1);
}
//query查询区间的数值
void query(int x,int p){
ans+=tree[p].num;
if(tree[p].l==tree[p].r)return;
int mid=(tree[p].l+tree[p].r)>>1;;
if(x<=mid)query(x,p<<1);
else query(x,p<<1|1);
}
//add是在一个区间上加上k
void add(int left,int right,int k,int p){
if(tree[p].l>=left&&tree[p].r<=right){
tree[p].num+=k;
return;
}
int mid=(tree[p].l+tree[p].r)>>1;
if(left<=mid)add(left,right,k,p<<1);
if(right>mid)add(left,right,k,p<<1|1);
}
}st;
int main(){
fast
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
st.build(1,n,1);
while(m--){
int insert;
cin>>insert;
if(insert==1){
int x,y,k;
cin>>x>>y>>k;
st.add(x,y,k,1);
}
else{
int x,y;
cin>>x;
int ans=0;
st.query(x,1);
cout<<ans<<endl;
}
}
return 0;
}
|
注意单点和区间的叠加区别很大！！！
前缀函数与KMP算法与KMP自动机#
KMP算法用在字符串匹配的问题中，可以将时间复杂度从O(N*M)变为O(N)，极大地提升了效率
构建前缀和函数的时候，当我们的s[i+1]!=s[pi[i]]的时候，我们寻找第二个长度j，使得在i位置处的前缀性质仍然得到保持，关键在于为了维持前缀性质，我们要在s[i-pi[i]+1]到s[i-1]这pi-1个字符中，找到最大的前缀和使其维持i处的前缀性，而s[i-pi[i]+1]到s[i-1]这pi-1个字符，由于前缀性，其实就等价于s[0]到是s[pi[i]-1]这几个字符，而我们要找的最大的前缀和其实就是pi[pi[i]-1],所以j=pi[pi[i]-1],以此不断向前寻找第二长度j。
下面给出KMP自动机算法的模板
模板题：KMP字符串匹配
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| //KMP自动机的构建
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const int maxn = 1E6 + 10;
//pi数组用于存储s2的前缀和
int pi[maxn], n;
//aut是KMP自动机对应的表，第一位表示上一个前缀和，第二位表示这个字母对应的值
vector<vector<int>>aut;
//prefix_function函数主要用于计算s2的前缀和函数，用到了两个优化
void prefix_function(string s) {
int n = (int)s.length();
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
}
// compute_automation函数主要用于构建KMP自动机，用到了动态规划来优化
void compute_automaton(string s) {
s += '#';//加上#来确保数组不会越界一定会在最后一位结束
n = s.size();
prefix_function(s);
aut.assign(n, vector<int>(52));//初始化aut自动机
//对小写来构建
for (int i = 0; i < n; i++) {
for (int c = 0; c < 26; c++) {
if (i > 0 && 'a' + c != s[i])
aut[i][c] = aut[pi[i - 1]][c];
else
aut[i][c] = i + ('a' + c == s[i]);
}
}
//对大写来构建
for (int i = 0; i < n; i++) {
for (int c = 0; c < 26; c++) {
if (i > 0 && 'A' + c != s[i])
aut[i][c+26] = aut[pi[i - 1]][26+c];
else
aut[i][c+26] = i + ('A' + c == s[i]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s1, s2;
cin >> s1 >> s2;
compute_automaton(s2);
int k = 0;//k表示上一位的前缀和
n--;//n是加上#后的长度，要减去1
for (int i = 0; i < s1.size(); i++) {
int x = 0;
if ((s1[i] >= 'A' && s1[i] <= 'Z'))x = s1[i] - 'A'+26;
else x = s1[i] - 'a';
k = aut[k][x];
if (k == n )cout << i -n+2<<endl;
}
for (int i = 0; i < s2.size() ; i++)cout << pi[i] << ' ';
return 0;
}
|
矩阵+快速幂算法#
将矩阵和快速幂相结合
快速幂#
假设在这正常的幂运算中，我们正常的运算是通过逐次的叠加来进行幂运算，这种的时间复杂度为n；这种方法随着n的增大就会显得很慢，这时候可以使用快速幂来优化算法的时间复杂度。
简单来说，快速幂的复杂度等同于二分法，将幂提前运算到底数中，从而实现了n的对半。下面给出了算法。同时，因为位运算的速度远远大于正常的乘除法。因此，引入幂运算。
1
2
3
4
5
6
7
8
9
10
11
| long long fastPower(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power & 1) {//此处等价于if(power%2==1)
result = result * base ;
}
power >>= 1;//此处等价于power=power/2
base = (base * base) ;
}
return result;
}
|
矩阵加速#
原题模板如下：
斐波那契数列#
题目描述:
大家都知道，斐波那契数列是满足如下性质的一个数列：
$$F_n = \left{\begin{aligned} 1 \space (n \le 2) \ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$
请你求出 $F_n \bmod 10^9 + 7$ 的值。
输入格式:
一行一个正整数 $n$
【数据范围】
对于 $60%$ 的数据，$1\le n \le 92$；
对于 $100%$ 的数据，$1\le n < 2^{63}$。
这道题目使用矩阵加速的核心在于矩阵可以将一系列有规律的连续加法变成连续乘法，在连乘时便可以使用
快速幂，从而完成了算法的优化
于是关键便是如何将加法变成乘法
给出代码如下：
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
| //矩阵加速模型
//核心：将加法改成乘法，利用前缀和方法进行缩短时间
#include <iostream>
#include <cstring>
#define fast std::ios::sync_with_stdio(false);std::cin.tie(0);
using namespace std;
const int mod=1E9+7;
struct Matrix{
int a[3][3];
Matrix(){memset(a,0,sizeof(a));}
Matrix operator*(const Matrix &b){
Matrix res;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod;
return res;
}
}ans,base;
void build(){
base.a[1][1]=1;
base.a[1][2]=1;
base.a[2][1]=1;
ans.a[1][1]=1;
ans.a[1][2]=1;
}
void quilkpow(long long n){
while(n){
if(n%2==1)ans=ans*base;
base=base*base;
n>>=1;
}
}
int main(){
fast;
long long n;
cin>>n;
if(n<=2)cout<<1;
else {
build();
quilkpow(n - 2);
cout << (ans.a[1][1]%mod);
}
return 0;
}
|
LIS问题的优化#
LIS问题也叫做最长不降子序列问题，我们传统的做法是用线性动态规划来进行求解，但是这样的时间复杂度位O(N^2)，在部分的问题中可能无法实现。下面给出一个例题，并给出普通的线性动态规划和它的优化解法
P1020 [NOIP1999 普及组] 导弹拦截
题目描述：#
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式：
一行，若干个整数，中间由空格隔开。
输出格式
：两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
传统的线性动态规划算法#
这题中为单调不升子序列，本质上与单调不降没有什么区别。我们记函数dp(i)为对于前 i 个数，在选择第 i 个数的情况下，得到的单调不升子序列的长度最长是多少。
记第 i 个数的高度为h(i).
于是可以分两种情况：
第 i 个数是子序列的第一项。于是dp(i)=1;
第 i 个数不是子序列的第一项。选择的第 i 个数之前选择了第 j 个数。根据题意，第 j 个数的值 h(j) 应当小于第 i 个数的值 h(i)。
枚举这样的 j，可以得到状态转移方程:dp(i)=max{dp(j)+1}。其中的i,j,h(i),h(j)应该满足关系：j < i并且h(j)>h(i)。
综合上述两种情况，便可以得到最终的转移方程：dp(i)=max{dp(j)+1，1}其中的i,j,h(i),h(j)应该满足关系：j < i并且h(j)>h(i)。
最后遍历所有的dp(i)找出其中的最大值。便是最后的答案了。
这样子的算法的最后的时间复杂度为O(N^2);
这样子的算法无法AC,使用二分查找进行改进。
二分查找改进后的动态规划算法#
我们规定f(i)为对于所有长度为 i 的单调不升子序列，它的最后一项的大小的最大值。特别地，若不存在则f(i)=0。下面证明：
随着 i 增大，f(i)单调不增。即f(i)>=f(i+1)。
下面使用反证法进行证明：假设存在u < v,满足f(u) < f(v)。考虑长度为 v 的单调不升子序列，根据定义它以f(v)结尾。显然我们可以该序列中挑选出一个长度为 u 的单调不升子序列，它的结尾同样是f(v)。那么由于f(v) > f(u),与f(u)最大相互矛盾，所以得证。
现在考虑以 i 结尾的单调不升子序列的长度的最大值dp(i)。由于我们需要计算所有满足的高度h(i) > h(j)的 j ，dp(j)的最大值，设 dp(j)=x,那么如果 h(i)> f(x),由于f(x) >= h(j),就有 h(i)>h(j)，矛盾，因此总有 h(i)<=f(x)。
根据刚刚得出的结论，f(i)单调不增，因此我们要找到尽可能大的 x 满足 h(i)≤f(x) 。考虑二分。
由上面给出的结论，我们可以将f(x)≥h(i)的看作合法的f(x),将f(x)< h(i)看作不合法的区域，由于f(x)的单调降低。我们需要通过二分找到合法与不合法的零界点。我们设左右区间的边界为L和R为左右的边界，且左闭右开。当R-L=1时，L的位置就是我们要找的位置。我们转移dp(i)=L+1。在更新f()时，我们只需要更新f(dp(i)),这是因为在f(dp(i))前面的大小肯定都是不小于h(i)的，所以前面的f()并不需要更新。f(dp(i))是最后一个不小于h（i）的值，即f(dp(i+1))小于h(i)。
时间复杂度为O(nlogn).
第二问#
在第一问的基础上使用贪心算法
从左到右依次枚举每个导弹。假设现在有若干个导弹拦截系统可以拦截它，那么我们肯定选择这些系统当中位置最低的那一个。如果不存在任何一个导弹拦截系统可以拦截它，那我们只能新加一个系统了。枚举到第 i 个位置时，有 mm 个系统。我们把这些系统的高度按照从小到大排列，依次记为g(1),g(2),…,g(n)。容易发现我们要找的g(x)满足g(x)≥h(i)。可以看出这也可以通过二分得到。在每一次更新g的值后，很容易看出，g还是单调不增的，如果找不到满足的导弹拦截系统，那就说明在后头直接增加一个就好了。
时间复杂度O(nlogn)
参考代码#
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
| #include<iostream>
#include<cstring>
using namespace std;
#define up(l,r,i) for(int i=l,j=r;i<=j;++i)
#define dn(r,l,i) for(int i=r,j=l;i>=j;--i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN = 1e5 + 3;
int n, t, H[MAXN], F[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin>>H[++n]) ;
--n;
F[0] = INF;
up(1, n, i) {
int l = 0, r = t + 1; while (r - l > 1) {
int m = l + (r - l) / 2;
if (F[m] >= H[i]) l = m; else r = m;
}
int x = l + 1; // dp[i]
if (x > t) t = x; F[x] = H[i];
}
cout<<t<<endl;
t = 0, memset(F, 0, sizeof(F)), F[0] = 0;
up(1, n, i) {
int l = 0, r = t + 1; while (r - l > 1) {
int m = l + (r - l) / 2;
if (F[m] < H[i]) l = m; else r = m;
}
int x = l + 1;
if (x > t) t = x; F[x] = H[i];
}
cout<<t<<endl;
return 0;
}
|
LCS问题#
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
| #include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
char s1[2010], s2[2010];
string a, b;
int ans[2010][2010];
int dfs(int i, int j) {
if (ans[i][j] != -1) return ans[i][j];
if (i == 0) return ans[i][j] = 0;
if (j == 0) return ans[i][j]=0;
if (s1[i] == s2[j])return dfs(i-1,j-1)+1;
return ans[i][j] = max(dfs(i - 1, j), dfs(i, j - 1));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> a >> b;
int len1 = a.size(), len2 = b.size();
for (int i = 1; i <= len1; i++)s1[i] = a[i - 1];
for (int i = 1; i <= len2; i++)s2[i] = b[i - 1];
memset(ans, -1, sizeof(ans));
cout<<dfs(len1, len2);
return 0;
}
|