首页 > 其他分享 >最低公共祖先

最低公共祖先

时间:2022-08-19 22:00:19浏览次数:52  
标签:pre seq 祖先 printf 最低 pos else int 公共

https://www.acwing.com/problem/content/description/1638/

思路:
LCA(爬山法)+重建一个树(知道其两个排序),由于时间n可能比较大,而且这题时间限制比较紧张,所以最后离散化,尽量查询不用哈希,因为哈希的常数太大了。

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int N = 10010;

int m, n;
int in[N], pre[N], seq[N];
unordered_map<int, int> pos;
int p[N], depth[N];

int build(int il, int ir, int pl, int pr, int d)
{
    int root = pre[pl];
    int k = root;

    depth[root] = d;

    if (il < k) p[build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), d + 1)] = root;
    if (k < ir) p[build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, d + 1)] = root;

    return root;
}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> pre[i];
        seq[i] = pre[i];
    }

    sort(seq, seq + n);
    for (int i = 0; i < n; i ++ )
    {
        pos[seq[i]] = i;
        in[i] = i;
    }

    for (int i = 0; i < n; i ++ ) pre[i] = pos[pre[i]];

    build(0, n - 1, 0, n - 1, 0);

    while (m -- )
    {
        int a, b;
        cin >> a >> b;

        if (pos.count(a) && pos.count(b))
        {
            a = pos[a], b = pos[b];
            int x = a, y = b;

            while (a != b)
                if (depth[a] < depth[b]) b = p[b];
                else a = p[a];

            if (a != x && a != y) printf("LCA of %d and %d is %d.\n", seq[x], seq[y], seq[a]);
            else if (a == x) printf("%d is an ancestor of %d.\n", seq[x], seq[y]);
            else printf("%d is an ancestor of %d.\n", seq[y], seq[x]);
        }
        else if (pos.count(a) == 0 && pos.count(b) == 0)
            printf("ERROR: %d and %d are not found.\n", a, b);
        else if (pos.count(a) == 0)
            printf("ERROR: %d is not found.\n", a);
        else
            printf("ERROR: %d is not found.\n", b);
    }

    return 0;
}

标签:pre,seq,祖先,printf,最低,pos,else,int,公共
From: https://www.cnblogs.com/xjtfate/p/16603445.html

相关文章

  • 搭建UnityGameFramework框架最低需求项目
    1、下载GameFramework包进入官网的下载页面下载2021.05.31版本https://gameframework.cn/download/2、新建Unity项目,然后把包导入3、新建Editor文件夹,并创建GameFr......
  • 最近公共祖先(LCA)
    #include<bits/stdc++.h>usingnamespacestd;intn,m,s;structD{intd;intf[22];}a[500005];vector<int>e[500005];voiddfs(intx){......
  • 最长公共子序列
    前缀型动态规划deflongest_common_seq(s1,s2):ifnots1ornots2:returnm,n=len(s1),len(s2)#dp[i][j]=max(dp[i-1][j],dp[i][j-1......
  • (未完)【算法学习笔记】04 最近公共祖先LCA
    【算法学习笔记】04最近公共祖先LCA原理顾名思义,就是求两点的最近公共祖先(自己也是自己的祖先)。也就是两点在走到根节点的路径上最先遇到的共同的点。向上标记法比较......
  • 9.最长公共子序列问题(动态规划)
    题目描述:给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。输入格式:输入数据有多组,每组有两行,每行为一个长度不超过500的字符串(输入全是大......