可能用到的算法模版整理

我开始有点慌了,今天刚快乐ow完后寻思看看蓝桥杯原题,然后打开18年试题读了几个题后。。。

woc这什么玩意怎么这么难?

好吧,冷静分析了一下,其实有些题我是可以做的,但是这些使用到的算法在我日常训练中都被简化的操作给替代了。

可毕竟蓝桥不让用啊。这里整理出一些可能会用到的算法模板,我尽量写的比较详细一点,帮助理解记忆。

整理整理自己打印出来,早自习不愁没事干了……

(本文没有新干货,都是炒冷饭)


排序算法

快速排序

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
#include <iostream>
#define maxn 23333
using namespace std;
int a[maxn], n;

void qsort(int l, int r) {
int i = l, j = r;
int mid = a[(l + r) >> 1];
while (i <= j) {
while (a[i] < mid)
i++;
while (a[j] > mid)
j--;
if (i <= j) {
swap(a[i], a[j]);
i++, j--;
}
}
if (l < j)
qsort(l, j);
if (i < r)
qsort(i, r);
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
qsort(1, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
system("pause");
return 0;

}

二路归并排序

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
#include <iostream>
#define maxn 233333
using namespace std;
int ans = 0;
int a[maxn];
int t[maxn];
int n;
void merge_sort(int *a, int x, int y, int *t) {
if (y - x > 1) {
int mid = (x + y) >> 1;
int p = x, q = mid, i = x;
merge_sort(a, x, mid, t);
merge_sort(a, mid, y, t);
while (p < mid || q < y) {
if (q >= y || p < mid && a[p] <= a[q])
t[i++] = a[p++];
else {
t[i++] = a[q++];
ans += (mid - p); // 用来求逆序对
}
}
for (i = x; i < y; i++)
a[i] = t[i];
}
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
merge_sort(a, 1, n + 1, t);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
system("pause");
return 0;
}

初等数论

快速幂

计算 a^x % p。

其实就是想办法把x拆开。考虑先把它表示成二进制形式,可以用不超过logx个f[i]拼出我们想要的答案。

在x的二进制表示中,1表示“取”。二进制中的每一个1都表示2的i次方。
比如说计算a^100,100的二进制是01100100,可以看出在2^2,2^5,2^6位置是1,而这些数分别对应4,32,64,那么只需要把a^100拆分成a^64×a^32×a^4即可。

实现很容易,每次提取处最低的二进制位再除以2即可。

1
2
3
4
5
6
7
8
long long int fast_pow(long long int a,long long int x,long long int p){
long long int ans = 1;
long long int sum = a % p;
for (;x;x>>=1,sum = sum*sum%p)
if (x&1)
ans = ans*sum%p;
return ans;
}

欧几里得/扩展欧几里得

gcd:

1
2
3
4
5
int gcd(int a, int b){
  if (!b)
    return a;
  return gcd(b, a % b);
}

证明(摘自ljp学长的课件):

证明欧几里得算法正确性的关键是证明 Gcd(a,b)=Gcd(b%a,a);
令x=Gcd(a,b),y=Gcd(b%a,a);
b%a可表示为a和b的线性组合:b%a=b-(b/a)×a;
因为 a%x=0,b%x=0;
所以 (b%a)%x=0;
故y%x=0;
又(b%a)%y=[b-(b/a)×a]%y=0, a%y=0;
根据同余定理可得
b%y-(b/a)×a%y=0,所以b%y=(b/a)×a%y=0;
所以x%y=0;
所以Gcd(a,b)=Gcd(b%a,a);
证毕;

exgcd:
给出不定方程 ax+by = Gcd(a,b) ,拓展欧几里得算法可以用于求解不等方程组的整数根(x,y)

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

用来求解形似ax+by = gcd(a,b)一类方程的解。
这里的x和y不一定是正整数,有可能是负数或0.
比如说我举个例子,求一直线ax+by+c = 0上有多少个整数点(x,y)满足x∈[x1,x2],y∈[y1,y2]

边界情况:
当b=0时,gcd(a,b)=a,x=1,y=0
假设 ax1 + by1= gcd(a,b),bx2 + (a % b)y2= gcd(b,a % b)
由gcd的意义,知gcd(a,b) = gcd(b,a % b),那么有ax1 + by1 = bx2+ (a % b)y2;
也就是说ax1 + by1 = bx2 + (a - [a / b] × b)y2 = ay2 + bx2 - [a / b] × by2;
也就是说ax1 + by1 == ay2+ b(x2 - [a / b] × y2);
那么,x1 = y2; y1 = x2 - [a / b] × y2;
这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2。我们可以通过不断递归调用求解。

我们这样只能得出一组解,其他解呢?如果我们现在有解(x1,y1),任取另外一组解(x2,y2),则有ax1 + by1 = ax2 + by2 = gcd(a, b),变形可以得到a(x1 – x2) = b(y2 – y1),两边同时除以gcd(a, b),得到a’(x1 – x2) = b’(y2 – y1),因为(a’,b’)=1,所以(x1-x2)一定是b’的倍数,取x1-x2=kb’,得y2-y1=ka’。

所以我们有以下结论:
对方程ax+by+c=0,一组整数解为(x0,y0),则它的任意整数解可以写成(x0+kb’,y0-ka’),其中a’=a/gcd(a, b),b’=b/gcd(a, b)

关于ax+by=c有没有解,我们有这么一个结论:
对于方程ax+by=c(a,b,c均为整数),如果c为gcd(a,b)的倍数,则方程有整数解,反之无整数解。因为a和b都是gcd(a,b)的倍数,所以ax+by一定也是gcd(a,b)的倍数,如果c不是gcd(a,b)的倍数,一定无解。
那刚才那道题怎么做呢?

方程变形为ax+by = -c,看一下-c是不是gcd(a,b)的倍数,然后用exgcd求一下ax+by = gcd(a,b)的解,记为(x0,y0)。
等式两边同乘(-c)/gcd(a,b),就有ax0’+by0’ = -c
用刚才的结论,求出使x = x0 + kb’落在区间[x1,x2]内的k的范围和使y = y0-ka’落在区间[y1,y2]内的k的范围,取交集就是答案。

欧拉筛法

核心思想是通过让每一个数只会被它最小的质因子筛到,从而每个数只会被筛一次,时间复杂度O(n)。

对于任意一个合数,我们可以拆成最小质因子×某数i的形式,我们枚举这个数i,然后再枚举出所有筛的质数。

当我们枚举的质数可以整除i时,如果再往大里枚举,枚举的质数就不可能是最小质数了。这时就可以终止循环,继续枚举下一个i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cnt;
int prime[maxn];
bool vis[maxn];
void Eular(int n){
for (int i=2;i<=n;i++){
if (!vis[i])
prime[++cnt] = i;
for (int j=1;j<=cnt && prime[j]*i<=n;++j){
vis[prime[j]*i] = 1;
if (i % prime[j] == 0)
break;
}
}
}

高精度计算

嗷!这里不写了嗷!

高精度板子看一次恐惧一次,得想个办法规避这个知识点……

比如用大整数计算暴力得出结果的题使用数学方法?

读入优化

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int read(){
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-')
flag = true;
else
num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}

对拍

(仅能锦上添花,无法雪中送炭)

@echo off
:start
randdata.exe 
problem.exe 
std.exe
@echo %time%
fc problem.out std.out
if not errorlevel 1 goto start
pause

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for (int i=1;i<=n;i++)
father[i] = i;

void merge(int x,int y) {
x = find(x);
y = find(y);
father[y] = x;
}

int find(int x) {
if (father[x] == x)
return father[x];
father[x] = find(father[x]);//如果当前节点的father并不是代表元素,那就递归地更新老祖宗
return father[x];//返回老祖宗
}

bool check(int x,int y) {
x = find(x);
y = find(y);
if (x==y)
return true;
else
return false;
}

简单图论

多源最短路:Floyed算法

多适用于邻接矩阵,时间复杂度O(n3),适用负边权

令dis[u][v]表示从u到v的最短路径长度,w[u][v]表示连接u,v边的长度。

首先初始化所有的dis,如果对于任意u,v有边相连则dis[u][v] = w[u][v],如果没有则dis[u][v] = INF。

算法过程:

1
2
3
4
5
6
7
8
for (int k = 1; k <= n; k++) { //这层循环必须放在最外面
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}

单源最短路:Dijkstra算法


多适用于邻接表,时间复杂度O(n2)(未经优化),O((n+m)logm)(加入堆优化),不适用负边权


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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long
#define INF 2147483647
using namespace std;
int n,m,s,head[50010],cnt;
ll dis[10010];
bool used[10010];
struct Edge{
int to,from,dis;
}edge[500010];

void add_edge(int u,int v,int dis){
edge[cnt].to=v;
edge[cnt].from=head[u];
edge[cnt].dis=dis;
head[u]=cnt++;
}
typedef pair<int,int> P;
void dijkstra(int s){
priority_queue<P,vector<P>,greater<P> > q;
fill(dis,dis+n+1,INF);
fill(used,used+n+1,false);
dis[s]=0;
q.push(P(0,s));
while(!q.empty()){
P p=q.top();q.pop();
int u=p.second;
if(used[u]) continue;
used[u]=true;
int pp=head[u];
while(pp!=-1){
int v=edge[pp].to;
if(!used[v]&&dis[v]>dis[u]+edge[pp].dis){
dis[v]=dis[u]+edge[pp].dis;
q.push(P(dis[v],v));
}
pp=edge[pp].from;
}
}
}
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
add_edge(u,v,d);
}
dijkstra(s);
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
return 0;
}


单源最短路:Bellman-Ford算法(经过队列优化后的中国叫法是SPFA)

多适用于邻接表,时间复杂度O(NE)(未经优化,N为点数,E为边数),O(kE)(k是常数,加入队列优化),适用负边权。

SPFA 在形式上和广度优先搜索非常类似,不同的是广度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是说一个点修改过其它的点之后,过了一段时间可能会获得更短的路径,于是再次用来修改其它的点,这样反复进行下去。
算法时间复杂度:O(kE),E是边数。K是常数,平均值为2。

SPFA代码模板:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 5000015
#define INF 2147483647
#define ms(x) memset(x,0,sizeof(x));
using namespace std;
struct Edge{
long long int from,to,dis;
};
Edge edge[maxn];
long long int n,m,s,u,v,d;
long long int head[maxn];
long long int dis[maxn];
bool inq[maxn];
long long int cnt = 0;
void add_edge(long long int from,long long int to,long long int dis){
edge[++cnt].from = head[from];
edge[cnt].to = to;
edge[cnt].dis = dis;
head[from] = cnt;
}

void spfa(void){
queue<long long int> q;
q.push(s);
ms(inq);
inq[s] = true;
for (int i=1;i<=n;i++)
dis[i] = INF;
dis[s] = 0;
while (!q.empty()){
long long int u = q.front();
q.pop();
inq[s] = false;
for (int i=head[u];i!=0;i=edge[i].from){
long long int v = edge[i].to;
long long int w = edge[i].dis;
if (dis[u]+w < dis[v]){
dis[v] = w+ dis[u];
if (!inq[v]){
q.push(v);
inq[v] = true;
}
}
}
}

}

int main(){
cin >> n >> m >> s;
for (int i=1;i<=m;i++){
cin >> u >> v >> d;
add_edge(u,v,d);
}
spfa();
for (int i=1;i<=n;i++)
cout << dis[i] << " ";
return 0;
}

该算法的速度非常之快,但当该算法运行在稠密图或者人为构造的网格图上,该算法的复杂度极有可能退化成O(NE)。

Kruskal算法

时间复杂度O(ElogE)(E为边数)

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>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 5005
#define maxm 200005
using namespace std;
struct Edge{
int from,to,dis;
bool operator <(const Edge &rhs)const{
return dis < rhs.dis;
}
};
Edge edge[maxm];
int father[maxm];
int n,m;
int totedge = 0;
int k = 0;
int ans = 0;
inline int read(){
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-')
flag = true;
else
num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
void init(){
for (register int i=1;i<=m;i++)
father[i] = i;
}
int find(int x){
if (father[x] == x)
return father[x];
father[x] = find(father[x]);
return father[x];
}

void merge(int x,int y){
father[find(x)] = find(y);
}

int main(){
n = read();m = read();
for (register int i=1;i<=m;i++){
edge[i].from = read();
edge[i].to = read();
edge[i].dis = read();
}
sort(edge+1,edge+m+1);
init();
while (totedge < n-1){
if (find(edge[++k].from) != find(edge[k].to)){
ans += edge[k].dis;
merge(edge[k].from,edge[k].to);
totedge++;
}
}
printf("%d\n",ans);
return 0;
}

拓扑排序

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
#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 23333
using namespace std;
struct Edge {
int from, to, dis;
};
Edge edge[maxn];
int n, m, s, u, v, d;
int inDegree[maxn];
int tot = 0;
int head[maxn];

void addEdge(int from, int to, int dis) {
edge[++tot].from = head[from];
edge[tot].to = to;
edge[tot].dis = dis;
head[from] = tot;
inDegree[to]++; // update in-degree
}

void output(int u) {
cout << u << " ";
}

void topoSort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0)
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
output(u);
for (int i = head[u]; i; i = edge[i].from) {
int v = edge[i].to;
inDegree[v]--;
if (inDegree[v] == 0)
q.push(v);
}
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> d;
addEdge(u, v, d);
}
topoSort();
system("pause");
return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:可能用到的算法模版整理

文章作者:Shawn Zhou

发布时间:2019年03月08日 - 20:03

最后更新:2019年03月10日 - 10:03

原始链接:http://shawnzhou.xyz/2019/03/08/19-03-08-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%