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

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

初三又打不了省选 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;
}

2019.8.6 集训笔记

2019.8.6 集训笔记

笔记

并查集

按秩合并

LCA

算法

代码实现