复习向

Language: C++,C

头文件使用:

1
2
3
4
5
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>

快读使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline int read()
{
int x=0,f=1;
char p=getchar();
while(p<'0'||p>'9')
{
if(p=='-') f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
x=(x<<1)+(x<<3)+p-'0';
p=getchar();
}
return x*f;
}

关于排序算法

插入排序

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
//数据下标从0开始,数组大小为n,排序后为单调不降(从小到大)
void insertion_sort(int a[],int n)
{
for(int i=1;i<n;i++)
{
int key = a[i];
int j=i-1;
while(j>=0&&a[j]>key)
{
a[j+1] = a[j];
j--;
}
a[j+1]=key;
}
}
int main()
{
const int Maxn=1e4+5;
int a[Maxn];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",a+i);
}
insertion_sort(a,n);
for(int i=0;i<n;i++)
{
printf("%d ", a[i]);
}
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
//数据下标从0开始,数组大小为n,排序后为单调不降(从小到大)
//把查找插入位置从O(n)的枚举遍历变为O(logn)的二分查找,但移动数据仍然需要O(n)的效率
//总时间复杂度不变,常数更小
void insertion_sort(int a[],int n)
{
for(int i=1;i<n;i++)
{
int key = a[i];
int pos = i;
int l=0,r=i-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[mid]>=key)
{
pos = mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
for(int j=i-1;j>=pos;j--)
{
a[j+1] = a[j];
}
a[pos]=key;
}
}
int main()
{
const int Maxn=1e4+5;
int a[Maxn];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",a+i);
}
insertion_sort(a,n);
for(int i=0;i<n;i++)
{
printf("%d ", a[i]);
}
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
//数据下标从0开始,数组大小为n,排序后为单调不降(从小到大)
void bubble_sort(int a[],int n)
{
bool flag=true;
while(flag)
{
flag = false;
for(int i=0;i<n-1;i++)
{
if(a[i+1]<a[i])
{
flag = false;
std::swap(a[i],a[+1]);
}
}
}
}
int main()
{
const int Maxn=1e4+5;
int a[Maxn];
int n;
n=read();
for(int i=0;i<n;i++) a[i]=read();
bubble_sort(a,n);
for(int i=0;i<n;i++) printf("%d ",a[i]);
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
//数据下标从0开始,数组大小为n,排序后为单调不降(从小到大)
void selection_sort(int a[],int n)
{
for(int i=0;i<n-1;i++)
{
int minIndex = i;
for(int j=i+1;j<n;j++)
{
if(a[j]<a[minIndex])
{
minIndex = j;
}
}
std::swap(a[i],a[minIndex]);
}
}

int main()
{
const int Maxn=1e4+5;
int a[Maxn];
int n;
n=read();
for(int i=0;i<n;i++) a[i]=read();
selection_sort(a,n);
for(int i=0;i<n;i++) printf("%d ",a[i]);
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
const int Maxn=1e6+5;
//区间表示 [l,r] [l,mid] [mid+1,r]
void merge_sort(int a[],int l,int r)
{
if(l>=r) return ;
int mid=l+((r-l)>>1);
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
static int tmp[Maxn];
int i=l,j=mid+1;
int now = l;
while(i<=mid&&j<=r)
{
if(a[i]<a[j]) tmp[now++] = a[i++];
else tmp[now++] = a[j++];
}
while(i<=mid) tmp[now++] = a[i++];
while(j<=r) tmp[now++] = a[j++];
for(i=l;i<=r;i++) a[i]=tmp[i];
}
int main()
{
int n;
int arr[Maxn];
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",arr+i);
merge_sort(arr,0,n-1);
for(int i=0;i<n;i++) printf("%d ", arr[i]);
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
const int Maxn=1e6+5;
//三路快速排序
//区间表示 [l,r] [l,mid] [mid+1,r]
void quick_sort(int a[],int l,int r)
{
if(l>=r) return ;
std::swap(a[l+rand()%(r-l+1)],a[l]);
int base = a[l];
int i=l+1,j=l+1,k=r;
while(i<=k)
{
if(a[i]<base) std::swap(a[i++],a[j++]);
else if(a[i]>base) std::swap(a[i],a[k--]);
else i++;
}
std::swap(a[j-1],a[l]);
quick_sort(a,l,j-2);
quick_sort(a,k+1,r);
}
int main()
{
srand(time(0));
int n;
int arr[Maxn];
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",arr+i);
quick_sort(arr,0,n-1);
for(int i=0;i<n;i++) printf("%d ", arr[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
28
29
30
void quick_sort(int a[],int l,int r)
{
if(l>=r) return ;
int base = a[l+rand()%(r-l+1)];
static int tmp[Maxn];
int cntL=l,cntR=r;
for(int i=l;i<=r;i++)
{
if(a[i]<base) tmp[cntL++]=a[i];
else if(a[i]>base) tmp[cntR--]=a[i];
}
for(int i=l;i<=r;i++)
{
if(i<cntL) a[i]=tmp[i];
else if(cntR<i) a[i]=tmp[i];
else a[i]=base;
}
quick_sort(a,l,cntL-1);
quick_sort(a,cntR+1,r);
}
int main()
{
srand(time(0));
int n;
int arr[Maxn];
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",arr+i);
quick_sort(arr,0,n-1);
for(int i=0;i<n;i++) printf("%d ", arr[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
28
29
30
31
32
const int Maxn=1e6+5;
//大顶堆,二叉堆的实现
void down(int a[],int n,int x)
{
while(x*2<=n)
{
int t=x*2;
if(t+1<=n&&a[t+1]>a[t]) t++;
if(a[t]<=a[x]) break;
std::swap(a[x],a[t]);
x=t;
}
}
//数组下标从1开始,数组长度为n
void heap_sort(int a[],int n)
{
for(int i=n;i>=1;i--) down(a,n,i);
for(int i=n;i>=2;i--)
{
std::swap(a[1],a[i]);
down(a,i-1,1);
}
}
int main()
{
int n;
int arr[Maxn];
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",arr+i);
heap_sort(arr,n);
for(int i=1;i<=n;i++) printf("%d ", arr[i]);
}

Others

其实还有 计数排序/基数排序/桶排序/希尔排序 等算法,实验课理论课似乎并无涉及?

素数筛

线性筛素数

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
inline long long read()
{
long long x=0,f=1;
char p=getchar();
while(p<'0'||p>'9')
{
if(p=='-') f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
x=(x<<1)+(x<<3)+p-'0';
p=getchar();
}
return x*f;
}
using namespace std;
const int Maxn=1e6+5;
bool vis[Maxn];
int pri[Maxn];
int m;
void prime(int n)
{
m=0;
vis[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
pri[++m]=i;
}
for(int j=1;j<=m&&i<=n/pri[j];j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
int main()
{
int x;
cin>>x;
prime(Maxn-5);
int l=1,r=m;
int num=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(x<pri[mid])
{
num=pri[mid];
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<num;
}

根号朴素筛法

字符串 trick

读入

一些库函数

KMP 算法(前缀数组)

好吧 好像不考么…

线性表

栈/队列/堆

FILO序列判定

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
inline long long read()
{
long long x=0,f=1;
char p=getchar();
while(p<'0'||p>'9')
{
if(p=='-') f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
x=(x<<1)+(x<<3)+p-'0';
p=getchar();
}
return x*f;
}
using namespace std;
const int Maxn=1e4+5;
char s[Maxn];
int main()
{
scanf("%s",s);
char Q[10],top=0;
Q[++top]='A';
char now = 'A';
for(int i=0;i<strlen(s);i++)
{
while(Q[top]!=s[i]&&now<'I')
{
Q[++top]=++now;
}
if(top&&Q[top]==s[i]&&now<='I') top--;
else break;
}
puts(top?"0":"1");
}

循环队列

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
inline long long read()
{
long long x=0,f=1;
char p=getchar();
while(p<'0'||p>'9')
{
if(p=='-') f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
x=(x<<1)+(x<<3)+p-'0';
p=getchar();
}
return x*f;
}
using namespace std;
int main()
{
int m=read(),n=read();
char q[25];
int front=0,rear=0;
for(int i=1;i<=n;i++)
{
int opt=read();
if(opt==1)
{
char x=getchar();
q[rear] = x;
rear++;
rear%=m;
}
else
{
front++;
front%=m;
}
printf("%d %d\n", front,rear);
}
for(int i=front;i!=rear;i=(i+1)%m)
{
printf("%c",q[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
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <iostream>
using namespace std;
inline int read()
{
int x=0,f=1;
char p=getchar();
while(p<'0'||p>'9')
{
if(p=='-') f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
x=(x<<1)+(x<<3)+p-'0';
p=getchar();
}
return x*f;
}
#define N 10005
int h[N],n=0;
void up(int x)
{
while(x>1)
{
if(h[x/2]>h[x])
{
swap(h[x/2],h[x]);
}
else
{
break;
}
x=x/2;
}
}
void down(int x)
{
while(x<=n)
{
int s = x*2;
if(s>n) break;
if(s<n&&h[s]>h[s+1]) s++;
if(h[x]>h[s])
{
swap(h[x],h[s]);
}
else
{
break;
}
x = s;
}

}
void Insert(int val)
{
h[++n] = val;
up(n);
}
void Del(int x)
{
h[x]=h[n--];
up(x);down(x);
}
void update(int x,int val)
{
h[x]=val;
up(x);down(x);
}
int main()
{
int m=read();
while(m--)
{
int opt=read();
if(opt==1)
{
int val=read();
Insert(val);
}
else if(opt==2)
{
Del(1);
}
else if(opt==3)
{
int x=read();
Del(x);
}
else if(opt==4)
{
int x=read(),val=read();
update(x,val);
}
}
while(n)
{
printf("%d ", h[1]);
Del(1);
}
}

常见的动态规划

序列问题:最长上升子序列

序列问题:青蛙跳石头

迷宫问题:从(1,1)走到(n,m)

区间DP问题:矩阵乘法

计数问题:数字拆分

0/1背包问题

完全背包问题

树与图 Trick

二叉树存图方法

邻接矩阵

邻接表(模拟链表实现)

排序二叉树(二叉搜索树)

二叉树的深度

多叉树转二叉树的遍历

二叉树的统计

二叉树的遍历

并查集

二分图判定(染色)

最短路(Dijkstra/Bellman-Ford/Floyd)

最小生成树(Prim/Kruskal)

判定强连通分量

判定连通图

杂项/模拟与贪心

Huffman编码

Gray码构造

用归并排序统计逆序对个数(逆序数)