ACM入门教程资料理论基础知识

ACM

1

图论

.................................................................................................................................................................... 3

1.1 术语

...................................................................................................................................................... 3

1.2

独立集、覆盖集、支配集之间关系

.................................................................................................. 3

1.4

最小点基

1.5

拓扑排序

1.6

欧拉路

1.7

哈密顿路（正确？）

.......................................................................................................................... 8

1.8 Bellman-ford .........................................................................................................................................9

1.11.1

1.11.2 KM

算法

...............................................................................................................................12

1.12

网络流

1.12.1

.................................................................................................................................. 15

1.12.2

2

数论

.................................................................................................................................................................. 21

2.1

最大公约数

2.2

最小公倍数

2.3

快速幂取模

2.4 Fermat

欧拉定理

2.9

线性同余方程

≡

b(mod n) .............................................................................................................24

2.10

中国剩余定理

2.11 Discrete Logging(B

L

2.12 N!

最后一个不为

0

的数字

................................................................................................................27

2.13 2^14

............................................................................................................................... 27

3.1.2

3.1.3

.............................................................................................................................. 32

3.2

并查集

3.3

树状数组

ACM

3.3.1 LOWBIT ...............................................................................................................................34

3.3.2

a[p]...............................................................................................................................34

3.3.3

3.5.2 KMP

............................................................................................................................ 40

4

计算几何

.......................................................................................................................................................... 42

4.1

直线交点

4.2

判断线段相交

4.3

................................................................................................................................ 43

4.7

经纬度坐标

........................................................................................................................................ 46

4.8

凸包

.................................................................................................................................................... 47

5 Problem .............................................................................................................................................................49

5.1 RMQ-LCA ..........................................................................................................................................49

5.1.1 Range Minimum Query(RMQ) ............................................................................................ 49

5.1.5 An<O(N), O(1)> algorithm for the restricted RMQ .............................................................61

5.1.6 An AC programme ............................................................................................................... 62

5.2

最长公共子序列

LCS ........................................................................................................................65

5.3

最长上升子序列

最长不下降子序列

5.3.1 O(n^2) ...................................................................................................................................66

组合数学相关

6.1 The Number of the Same BST ........................................................................................................... 70

6.2

排列生成

6.3

.................................................................................................................................................... 72

6.3.1

7

.......................................................................................................................................................... 73

牛顿迭代

7.4

数值积分

7.5

高斯消元

8

其它

.................................................................................................................................................................. 78

ACM

一个顶点相邻，那么 D 称为图 G 的一个支配集。

极小支配集：若在 D 集中去除任何元素后 D 不再是支配集，则支配集 D 是极小支配集。

最小支配集：G 的所有支配集中顶点个数最少的支配集。

点基：设 G＝(V，E)是一个有向图，B 是若干个顶点组成的 V 的子集。如果对于任意的 Vj∈V，都存在一个

Vi∈B，使得 Vi 是 Vj 的前代，则称 B 是一个点基。

最高强连通分支：设[Si]是有向图 G 的一个强连通分支，如果在 G 中，不存在终点属于[Si]而起点不熟于[Si]

的弧，就称[Si]为最高强连通分支。

最小路径覆盖是指在有向无环图 G 里面，覆盖所有点的最少不相交简单边的集合，即每个点只属于一条边。

最小路径覆盖数＝G 的定顶点数－最小路径覆盖中的边数。

覆盖集：K 是 G 图的一个顶点子集且 G 的每一边至少有一个端点属于 K，则称 K 是 G 的一个覆盖。

(1)

一个独立集是极大独立集，当且仅当它是一个支配集；

(2)I

是独立集，当且仅当

G

I

集外的所有顶点是一个覆盖集；

I

是极大

(

最大

G

I

(

最小

)

覆盖集，即

α

(G)

（覆盖数）十β

（覆盖数）

= G

(3)

极大独立集必为极小支配集，但是极小支配集未必是极大独立集。

ACM

求所有极小支配集的公式：

φ(V1，V2，…，Vm)＝Π(Vi 十ΣU)

一个顶点同与它相邻的所有顶点进行加法运算组成一个因子项，几个因子项再连乘。连乘过程中展开成积

极小覆盖集的计算方法：

φ(V1，V2，…，Vm)＝Π(Vi 十ΠU)

某顶点的所有相邻顶点进行积运算后再与该顶点进行和运算，组成一个因子项。几个因子项连乘，并根据

逻辑运算定律展开成积之和形式。每一积项给出一个极小覆盖集，所有积项给出了一切极小覆盖集，其中

向图 则没有这个规则

gc 矩阵:gc[i][j]-> 0 : 无边

1 : 树枝边

2 : 反向边

3 : 正向边

4 : 交叉边

d 数组: 顶点的开始访问时间表

f 数组: 顶点的结束访问时间表

c 数组: 顶点颜色表 0 白色 -1 灰色 1 黑色

p 数组: 顶点的前驱表

const int maxn = 100;

int n, g[maxn][maxn], gc[maxn][maxn];

int d[maxn], f[maxn], l[maxn], p[maxn], c[maxn], b[maxn];

ACM

int time;

void dfs_visit(int u)//递归搜索以 U 为根的深度优先树

{

time++; d[u] = time, l[u] = time;

for(v = 1; v<=n; v++)

if(g[u][v] > 0)

if(c[v] == 0) //如果 v 是白色节点

{

}

if(l[v] < l[u]) //u 与 v 相连

gc[u][v] = 2; //反向边

else gc[u][v] = 4; //交叉边

}

time++; f[u] = time;

{

int u;

memset(gc, 0, sizeof(gc));

memset(c, 0, sizeof(c));

memset(b, 0, sizeof(b));