清北第二天,感受到了来自这个世界的不友善,大概把没听过不会的 "名词" 记录下来就已经一面了,然后被大佬说这都是最基础的东西,就很皮,那就趁别人练习字符串的题的时候,来写波博客了,倒不是不想写,(MD 这么快就 KMP,Hash,Manacher,AC 自动机,Tire 树,我毛都不会啊没法写啊,讲的巨难,详细也听不懂啊,上来一个指针就蒙了)
不扯没意思的,从早上开始积累的问题慢慢总结吧。
1、倍增:第一次听到这个词是懵逼的,然后什么树上倍增的直接让我就傻逼了,实际上在之前有次上课的时候,老师提了一句话,现在想起来倒是发现体现了倍增的思想,倍增倍增,成倍增加,就是在算 Nm 的时候,可以直接把 m 拆成 2*4*8*16*32*……,那么这个 2 4 8 16 32 这一连串就体现了倍增的思想,加快了化学反应速率算法的的速度,提高效率,避免了不必要的重复计算。
2、树:可谓有各种奇葩的不奇葩的麻烦的难的树,今天讲的大概有如下几个几百个:生成树、最大生成树、最小生成树、LCA 最近公共祖先、线段树、树状数组、树上倍增、有根树、重构树、虚树、树剖等……
一个一个来:
生成树:如果连通图 G 的一个子图是一棵包含 G 的所有顶点的树,则该子图称为 G 的生成树 (SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。
最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。即最小权重生成树,每个边所带的权重值的和最小即为最小生成树。
严格次小生成树:
最大生成树:与最小生成树相对,每个边所带的权重值和最大即为最大生成树。
线段树:数据结构中的一种,是一种二叉搜索树,与区间树相似。
树状数组:是一个查询和修改复杂度都为 log(n) 的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在 log(n) 的复杂度下进行范围修改,但是这时只能查询其中一个元素的值 (如果加入多个辅助数组则可以实现区间修改与区间查询)。
- 1#include 2 using namespace std;
- 3 int n,
- m,
- i,
- num[100001],
- t[200001],
- l,
- r; //num:原数组;t:树状数组
- 4 int lowbit(int x) 5 {
- 6
- return x & ( - x);
- 7
- }
- 8 void change(int x, int p) //将第x个数加p
- 9 {
- 10
- while (x <= n) 11 {
- 12 t[x] += p;
- 13 x += lowbit(x);
- 14
- }
- 15
- return;
- 16
- }
- 17 int sum(int k) //前k个数的和
- 18 {
- 19 int ans = 0;
- 20
- while (k > 0) 21 {
- 22 ans += t[k];
- 23 k -= lowbit(k);
- 24
- }
- 25
- return ans;
- 26
- }
- 27 int ask(int l, int r) //求l-r区间和
- 28 {
- 29
- return sum(r) - sum(l - 1);
- 30
- }
- 31 int main() 32 {
- 33 cin >> n >> m;
- 34
- for (i = 1; i <= n; i++) 35 {
- 36 cin >> num[i];
- 37 change(i, num[i]);
- 38
- }
- 39
- for (i = 1; i <= m; i++) 40 {
- 41 cin >> l >> r;
- 42 cout < endl;
- 43
- }
- 44
- return 0;
- 45
- }百科的
重构树:由最小生成树产生的,在使用 kruskal 算法考虑最小生成树的时候,树的结构和边发生了一定的改变,这里我们就把他叫做重构树,重新构建了一个树,故其边的权重值也发生了改变,那么既然提到了克鲁斯卡尔算法,就再来百度一波 kruskal 算法:先对所有的边进行排序,循环地从权值最小的边开始遍历每条边 直至图 Graph 中所有的节点都在同一个连通分量中 if 这条边连接的两个节点于图 Graphnew 中不在同一个连通分量中添加这条边到图 Graphnew 中。最后构成的这个数就是最小生成树。
同理还有 Prime 算法:任取一个点作为树的起点,该点引出的所有边中,先选出最小的一条,然后得到一个新的节点,从这两个点中引出的边中,选出最小的一条,以此类推。
即重复地操作,直到 Vnew = V:a. 在集合 E 中选取权值最小的边,其中 u 为集合 Vnew 中的元素,而 v 不在 Vnew 集合当中,并且 v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);b. 将 v 加入集合 Vnew 中,将边加入集合 Enew 中。
虚树:不存在的树,把需要询问的点放到另一个树上,即使不是一样的树。http://blog.csdn.net/jzhang1/article/details/50535800(安利一下某个大佬的网站)
LCA + 树上倍增:最近公共祖先,Least common ancestor,对于这个图而言,5 的父亲节点为 2,父亲的父亲节点为 1,4 的父亲节点为 3, 父亲的父亲节点为 2,父亲的…… 的节点为 1,那么 4、5 最近的公共祖先就是 2。
那么很容易想到一个暴力算法,就是 DFS 搜出每个点的深度,再不停地往上跳,那就会很浪费时间,所以结合第一个倍增的思想来看,就有了树上倍增的说法,所以代码如下。
- 1#include 2#include 3#include 4#include 5#include 6 using namespace std;
- 7 vector < int > g[100010];
- 8 int father[100010][40] = {
- 0
- };
- 9 int depth[100010] = {
- 0
- };
- 10 int n,
- m;
- 11 bool visit[10010] = {
- false
- };
- 12 int root;
- 13 14 void dfs(int u) 15 {
- 16 int i;
- 17 visit[u] = true;
- 18
- for (i = 0; i) 19 {
- 20 int v = g[u][i];
- 21
- if (!visit[v]) 22 {
- 23 depth[v] = depth[u] + 1;
- 24 dfs(v);
- 25
- }
- 26
- }
- 27
- } //深搜出各点的深度,存在depth中
- 28 29 void bz() 30 {
- 31 int i,
- j;
- 32
- for (j = 1; j <= 30; j++) 33
- for (i = 1; i <= n; i++) 34 father[i][j] = father[father[i][j - 1]][j - 1];
- 35
- } //倍增,处理father数组,详情参照上述讲解
- 36 37 int LCA(int u, int v) 38 {
- 39
- if (depth[u] < depth[v]) 40 {
- 41 int temp = u;
- 42 u = v;
- 43 v = temp;
- 44
- } //保证深度大的点为u,方便操作
- 45 int dc = depth[u] - depth[v];
- 46 int i;
- 47
- for (i = 0; i < 30; i++) //值得注意的是,这里需要从零枚举
- 48 {
- 49
- if ((1 < //一个判断,模拟一下就会很清晰
- 50 u = father[u][i]; 51
- }
- 52 //上述操作先处理较深的结点,使两点深度一致
- 53
- if (u == v) return u; //如果深度一样时,两个点相同,直接返回
- 54
- for (i = 29; i >= 0; i--) 55 {
- 56
- if (father[u][i] != father[v][i]) //跳2^j步不一样,就跳,否则不跳
- 57 {
- 58 u = father[u][i];
- 59 v = father[v][i];
- 60
- }
- 61
- }
- 62 u = father[u][0]; //上述过程做完,两点都在LCA下一层,所以走一步即可
- 63
- return u; 64
- }
- 65 66 int main() 67 {
- 68 int i,
- j;
- 69 scanf("%d", &n);
- 70
- for (i = 0; i <= n; i++) 71 g[i].clear();
- 72
- for (i = 1; i) 73 {
- 74 int a,
- b;
- 75 int root;
- 76 scanf("%d%d", &a, &b);
- 77 g[a].push_back(b);
- 78 father[b][0] = a;
- 79
- if (father[a][0] == 0) 80 root = a;
- 81
- }
- 82 depth[root] = 1;
- 83 dfs(root);
- 84 bz();
- 85 int x,
- y;
- 86 scanf("%d%d", &x, &y);
- 87 printf("%d", LCA(x, y));
- 88
- return 0;
- 89
- }
3. 图论:之前的各种树应该建立在图的基础上,毕竟树也是图的一种嘛,所以也就有了一下几个名词:无向图,有向图,并查集等……
那么继续总结一波
无向图:边不带方向的图。
有向图:边带方向的图。
邻接点:边的两个顶点。
度:一个顶点相关联的边的个数。
出度:有向图中一个顶点的出边个数。
入度:有向图中一个顶点的入边个数。
完全无向图:每两个顶点之间都存在一条边,共有(2n*(n-1))-1 边。(分母不会打,将就看吧)
完全有向图:每两个顶点之间都存在方向相反的两条边,共有 n*(n-1)条边。
子图:图的任意一个部分。
路径:从一个顶点到另一个顶点的一条路。
(这里指无向图)
连通:从顶点 V 到顶点 W 有路径,则两点连通。
连通图:任意两个点之间都是连通的。
连通分量:某个图的极大连通子图,就是这个图的连通分量。
(这里指有向图)
强联通图:任意两点之间的两点之间都有路径连通(正向反向都有),那么这个图就被叫做强联通图。
强连通分量:有向图的极大连通子图就是这个的强连通分量。
权:两个点之间的距离或是两个点之间的消耗。
网:一堆权的构成图。
(大概感到无聊了?那么很愉快的告诉你相关专用术语已经完了)
那么怎么样把这个图读进去呢?
当然是用邻接矩阵和邻接表 cin 来读了。
那么就看一下无向图的邻接矩阵好了。
我们可以画一个矩形,如下
很清晰可以看出来,只要是能到达的边,就用 1 来表示,两个点之间没有路径的时候用 0 来表示。
显而易见上代码
- 1
- for (i = 1; i <= n; ++i) 2 {
- 3
- for (j = 1; j <= n; ++j) 4 {
- 5 cin >> x >> y >> w;
- 6 edge[x][y] = w;
- 7 edge[y][x] = w;
- 8
- }
- 9
- }
那么有向图呢,就分了两种,带权值和不带权值的
同理,不再是单纯的有没有边,能到达就记为 1,不能到达就记为 0。
那么带权值的
这里的图不是很清楚,总之记录两个邻接点之间的距离。那么上一波代码
- 1
- for (i = 1; i <= n; ++i) 2 {
- 3
- for (j = 1; j <= n; ++j) 4 {
- 5 cin >> x >> y >> w;
- 6 edge[x][y] = w;
- 7
- }
- 8
- }
还有 167 天初赛,195 天复赛。
那是我愿意付诸一生的人,现在却没法拥有。
来源: http://www.cnblogs.com/wahahaljy/p/6786301.html