2019.8.6 集训笔记
浏览 61 | 评论 0 | 字数 3260
Snowflake_Pink
2019年08月06日
  • 明天讲高级数据结构,像树链剖分或者是平衡树以前在高中部都讲过(但是我菜的基本上不会打),上午、下午和晚上差不多把同样的知识点讲了两边。

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

    初三又打不了省选 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 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论