这是一个LCA 树上倍增 求法的 Blog ， 差不多就是一个算法模板

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

void bfs() {
	queue<int> q;
	d[1] = 1; q.push(1);
	while(!q.empty()) {
		int x = q.front(); q.pop();
		for (int i=head[x]; i; i=Next[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x] + 1;
			f[y][0] = x;
			for (int j=1; j<=t; ++j)
				f[y][j] = f[f[y][j-1]][j-1];
			q.push(y);
		}
	}
}

int lca(int x, int y) {
	if (d[x] > d[y])	swap(x, y);
	for (int i=t; i>=0; --i)
		if (d[f[y][i]] > d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i=t; i>=0; --i)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

这是一个LCA的模板， LCA的应用需要进行初始化， 总的时间复杂度大概在O(nlogn) + O(logn) 的范围左右。

关于LCA的应用， 可以求一棵树上两点之间的最短距离 ， 模板如下所示：

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

void bfs() {
	queue<int> q;
	d[1] = 1; q.push(1);
	while(!q.empty()) {
		int x = q.front(); q.pop();
		for (int i=head[x]; i; i=Next[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x] + 1;
            dist[y] = dist[x] + edge[i];//维护从根节点到y点的距离
			f[y][0] = x;
			for (int j=1; j<=t; ++j)
				f[y][j] = f[f[y][j-1]][j-1];
			q.push(y);
		}
	}
}

int lca(int x, int y) {
	if (d[x] > d[y])	swap(x, y);
	for (int i=t; i>=0; --i)
		if (d[f[y][i]] > d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i=t; i>=0; --i)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

int ans = dist[x] + dist[y] - 2 * dist[lca(x, y)];

ans 中所存的值即为所求的答案。

LCA, 全称叫做最近公共祖先, 这是在树结构中的一个算法, 来求解一棵树中两个节点的最近公共祖先, (其实就是字面意思

关于LCA的求法, 常见的大概有3种, 效率也都不很一样:

1. 向上标记法求LCA
2. 树上倍增法求LCA
3. LCA 的 Tarjan 算法

由于第一种算法十分暴力, 直接就是根据 LCA 的定义暴力求解, 所以就不多加解释, 第二第三种方法的时间复杂度都比较优秀, 不同的是 树上倍增 支持在线处理, 而 Tarjan 算法只支持离线操作, 但是复杂度都是可以接受的, 需要根据题目来酌情选择

树上倍增求LCA

时间复杂度: O(nlogn) + O(logn) 预处理+询问

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。是一种可以进行寻找信息统计,支持查询和修改的一种高级数据结构.

有关于线段树的知识, 之前就计划进行一个线段树的知识总结, 现在抽时间进行一下总结:

像之前一样, 还是先总结一下线段树具有的一些性质:

1. 线段树的每一个节点都表示一个区间
2. 线段树具有唯一的根节点, 代表的区间是整个统计范围, 如[1, N]
3. 线段树的每一个叶结点都代表一个长度为 1 的元区间, 如 [x,x]
4. 对于每一个内部节点[l,r], 他的左子结点是[l, mid], 右字节点是[mid+1, r], 其中 mid = (l+r) / 2 (向下取整)

线段树中各节点的表示方法:

1. 根结点的编号为1
2. 编号为 x 的节点的左子结点的编号为 x 2 (x<<1), 右字节点的编号为 x 2 + 1 (x<<1|1)

这样我们就可以简单的用一个struct数组来保存一颗线段树. 当然, 这颗线段树的最后一层可能并不是连续的, 并没有填满. 最后一层产生了空余, 所以保存线段树的数组长度要不小于 4 倍的 N才能保证不会越界．

树形结构是图论中的一种特殊情况, 可以说树就是一种特殊的图结构. 树的定义是这样的, 如果一个图中一共有n个顶点, 并且有且只有n-1条边, 这样的图被称之为树.

根据树的性质, 我们可以得出几个简单的结论:

1. 树中不会出现环
2. 没有父节点的节点称为根节点
3. 每个节点有零个或多个子节点
4. . . .

根据树的一些性质我们可以求一些树的基本特征:

1. 树的直径
2. 树的DFS序
3. 树的各点子树大小
4. 树上各点的深度
5. 树的重心
6. 树的Topsort

下面是这些特征的定义:

1. 一棵树的直径就是这棵树上的一条最长路径
2. 树的DFS序指的是在对一颗树先序遍历的顺序
3. 每个点子树的大小指的是各点下所有的字节点的个数
4. 每个点的深度是指, 如果规定根节点的深度为1的话, 那么每个节点的深度等于他的父节点的深度加一
5. 一颗树的重心指的是如果把一个点删除的话, 原来的树形成的几个子树中最大的那一颗子树的大小最小的那一个点就是树的重心
6. 拓扑序(Topsort)指的是在一张有向无环图(DAG) G中, 将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

以上的这些性质基本上都可以用搜索, 或者DP的方法来求出,现在总结一下这些基本特征的代码,来加强一下记忆

刷题柱

1. p1253 经典问题
2. p1254 经典问题 LIS + Dilworth定理 ：偏序集的最少反链划分数等于最长链的长度
3. p1255 经典问题 预处理正反各求一遍 LIS 枚举每一个点处理答案
4. p1256 经典问题 先按照时间顺序进行排序， 判断第 i 个苹果之前的苹果是否可以接到， 然后更新 f 值即可

计划清单

1
2
3

1.DP + DP优化
2.图论基本算法
3.多做题

新坑

1
2
3
4

1. 数论有关内容
2. 图论提高
3. 熟悉基本模板
4. 对拍熟练掌握

计划要写的题

P1825
P1138
P1462 (非常恶心的一道大模拟)

给自己立个 Flag, 这里所列的事情都要按时完成 如果明知道自己肯定完成不了的任务就不要往这上面写.即使计划可能很微小, 但也比没有规划, 整天迷茫的人生要更有意义.

观影计划

1

《霸王别姬》 (本周)

1
2
3
4
5
6

已完成目录:
《海上钢琴师》(已完成)
《楚门的世界》(已完成)
《肖申克的救赎》(已完成)
《盗梦空间》(已完成)
《阿甘正传》(已完成)

读书计划

1
2

日常计划

1

每天练习打字 https://www.typing.com/student/lessons 每天15分钟

回来学校之后觉得应该把基础补下，于是就有了这篇博客

本博客的主要内容来自焦作一中校本教材

递归

递推定义

直接或间接调用自己的算法叫做递归算法。在一个函数的内部直接或间接地出现有对自身的引用，称他为递归函数。

写一个递归函数的两个要素： 边界条件， 递归方程。 这两部分组成了一个递归函数。

递归的一般形式

1
2
3
4
5

void rec(参数列表) {
	if (test)    return; //边界条件
    rec(参数列表); //递归调用阶段
    . . . //递归返回阶段
}

因为递归的表达简单， 但是效率并不高， 所以基于递归出现了记忆化搜索。

vector数组存图

当边权为1的图可以用vector数组存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<int>	e[100010];
int xx,yy;
for (int i=1;i<=m;++i)//	总共m条边
{
	scanf("%d%d", &xx,&yy);
    a[xx].push_back(yy);
    a[yy].push_back(xx);
}//	图的读入

for (int i=0;i<a[x].size;++i)//对于m节点相连的边的遍历。
{
	int t = a[x][i];
    if (!vis[t])
    	...
}

快速乘 与 快速幂 两个代码模板：

1
2

inline int Mul(int a,int b,int p,int res=0){for(;b;b>>=1,a=(a+a)%p)if(b&1)res=(res+a)%p;return res;}// 其实是伪的快速乘，并没有提高速度，只是防止了溢出。  记得res的值初始化为0。
inline int Power(int a,int b,int p,int res=1){for(;b;b>>=1,a=Mul(a,a,p))if(b&1)res=Mul(res,a,p);return res;}

代码很简洁只用两行就好

在膜意义下的加减乘运算

1
2
3

inline int add(int a,int b){return (a+=b) > mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b) < 0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}

这样可以保证每次加减乘运算的结果在0 ~ mod 的范围之内，优化常数。