明天讲高级数据结构，像树链剖分或者是平衡树以前在高中部都讲过（但是我菜的基本上不会打），上午、下午和晚上差不多把同样的知识点讲了两边。

但是感觉提高组并不需要这些东西。。。。

初三又打不了省选 QAQ，所以我觉得还是在机房打打线段树、树状数组、ST 表等一些低级数据结构。

还有把考试题改完，练一下 $dp$ 、复习一下图论 qwq

就这么决定了吧......

上面这些写在昨天 $\Uparrow \Uparrow$

今天后面说又加了联赛难度的数据结构，上午讲了 $LCA$ 、树状数组、并查集还有堆。知识点都讲得还行，但是例题就比较难了，两个 dalao 坐在我旁边让我瑟瑟发抖。

笔记

并查集

按秩合并

之前没有听过，连输入法都没有这个字词 QAQ。但是它仍然比较重要和简单。

说起来很简单，就是在合并两个不同子集时，按照 rank[] 来进行合并，rank[] 表示在合并后的这棵树下，节点的深度。rank 高的连接在 rank 低的下面，这样就可以变成一棵树了。

LCA

这个知识点在很久以前就咕咕咕了，现在补上。

最近公共祖先的暴力很容易想到，就是深度深的先到一样的高度，然后两个点一起一个一个地跳，调到一样的点就说明找到了。但是如果在一个非常毒瘤的树中，你可能把整个树都走一遍 QAQ。

所以就有了专门求 LCA 的算法：倍增，当然还有 $Tarjan$ （$O(n+q)$）和树链剖分（$O(n \log n)$）。倍增的时间复杂度也是 $O(n \log n)$ ，$Tarjan$ 是离线算法，树链剖分有点难打，所以倍增还是挺不错的。

算法

讲起来非常简单，另一个深度深的人先到同一高度。每次跳 $2^i$ 步，如果两个人跳 $2^i$ 的地方相同，就不跳，因为结果可能不是 最近 的公共祖先，如果跳到的地方不同，就跳。这样，每次跳上一次的一半，如果跳不了，就再减一半，直到能跳为止。这样，复杂度大约是 $O(\log n)$ 的。

代码实现

实现非常简单，先开一个数组 f[i][j] 表示第 $i$ 点跳 $2^j$ 步到达的地方，那么初始状态就是 f[i][0] = 父节点 ，然后就可以像动态规划那样列出转移方程了。

$$ f[i][j] = f[f[i][j-1]][j-1] $$

用文字描述就是跳 $2^{j-1}$ 步，然后再跳 $2^{j-1}$ 步。

模板题：SP14932 LCA

因为原来的洛谷的模板题打过了，为了增加 AC 题目，我选择了 $SPOJ$ QAQ

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 1e3+5;
const int MAXM = 1e3;
const int MAXQ = 1e3+5;

struct Edge {
   int v, next;
};
Edge edge[MAXN];

int T, n, m, q, dep[MAXN], rt;
int cnt, head[MAXN];
int f[MAXN][35];

bool flag[MAXN];

inline int up (int x, int dis) {
   for (int i = 30; i >= 0; i--) {
       if (1<<i <= dis) {
           x = f[x][i];
           dis -= 1<<i;
       }
   }
   return x;
}

inline void Init() {
   cnt = 0;
   rt = 0;
   memset (head, 0, sizeof (head));
   memset (edge, 0, sizeof (edge));
   memset (f, 0, sizeof (f));
   memset (flag, false, sizeof (flag));
   memset (dep, 0, sizeof (dep));
   return;
}

inline void AddEdge (int u, int v) {
   cnt++;
   edge[cnt].v = v;
   edge[cnt].next = head[u];
   head[u] = cnt;
   return;
}

void dfs (int x) {
   for (int i = head[x]; i != 0; i = edge[i].next) {
       int v = edge[i].v;
       dep[v] = dep[x] + 1;
       dfs (v);
   }
   return;
}

int main() {
   scanf ("%d", &T);
   
   for (int k = 1; k <= T; k++) {
       Init();
       scanf ("%d", &n);
       for (int i = 1; i <= n; i++) {
           scanf ("%d", &m);
           for (int j = 1; j <= m; j++) {
               int son;
               scanf ("%d", &son);
               flag[son] = true;
               f[son][0] = i;
               AddEdge (i, son);
           }
       }
       
       for (int i=1; i<=n; i++) {
           if (!flag[i]) {
               rt = i;
               break;
           }
       }
       
       dfs (rt);
       
       for (int i = 1; i <= n; i++) {
           for (int j = 1; (1<<j) <= dep[i]; j++) {
               f[i][j] = f[f[i][j-1]][j-1];
           }
       }
       
       scanf ("%d", &q);
       printf ("Case %d:\n", k);
       while (q--) {
           int l, r;
           scanf ("%d%d", &l, &r);
           
           if (dep[l] > dep[r]) {
               l = up (l, dep[l] - dep[r]);
           }
           else {
               r = up (r, dep[r] - dep[l]);
           }
           if (l == r) {//这一点很重要，不然最近公共祖先就会变成正确答案的父亲
               printf ("%d\n",l);
               continue;
           }
           for (int i = 30; i >= 0; i--) {
               if (f[l][i] == f[r][i]) continue;
               l = f[l][i];
               r = f[r][i];
           }
           
           printf ("%d\n",f[l][0]);
       }
   }
   return 0;
}

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/74/
最后修改时间：2020-04-13 11:40:28
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！