精华内容
下载资源
问答
  • 倍增算法

    万次阅读 多人点赞 2018-08-15 14:12:43
    一直觉得倍增算法是个很神奇的东西,所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER,我非常讨厌在看别人的算法解析时整版的i,j,k等我看到鼠标就惯性移到右上角的符号语言,所以我想用最形象的方式来...

    白话讲解:转载原地址

    【序言】

            我认为吧,所有能够优化复杂度的算法都是神奇的,所有能够化繁琐为形象的文字都是伟大的。一直觉得倍增算法是个很神奇的东西,所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER,我非常讨厌在看别人的算法解析时整版的i,j,k等我看到鼠标就惯性移到右上角的符号语言,所以我想用最形象的方式来纪念它。

     

    【一】

            从前,有一只可爱得不得了的小白兔,它想从A地去往遥远的B地。

     

            2B小白兔:

                向右边跳一步,左边跳一步,再向右边跳很多步,再……(对不起,这个太脑残了)

            普通小白兔:

                向右边跳一步,再跳一步,再跳一步……再跳一步,哇,到了!好开心!

            超级小白兔:

                向右边跳一大步,一步跳到B,然后默默回头,鄙视一下那只一步一步跳的小白兔。

     

            我相信作为一个正常人,是不会考虑到2B小白兔的这种做法的,因为它太脑残了。

            同时我也相信,作为一个正常人,也不会考虑到超级小白兔的这种做法的,因为……

                “我擦!你什么时候说可以这样跳了!(愤怒)”

                “我什么时候说不可以了!(卖萌)”

            但是你不得不承认,超级小白兔还是有两把刷子的,因为它真的是太厉害了,厉害得你想都没有想到。

     

    【二】

            从前,有一只可爱得不得了的小白兔,它想从A地去往遥远的B、C、D、E、F这几个让它魂牵梦萦的地方。(不要问我从哪里来,我的梦想在远方)

     

     

            2B小白兔:

                (对不起,我的生命有限,我不想再提到它了)

            普通小白兔:

                一步又一步,生命不息,跳跃不止。

            超级小白兔:

                一步到B,再一步到C,再一步到D,再一步到E,再一步到F,完工。

     

            你不用解释,我深知你就想当那只超级小白兔,哼,你肯定是那样跳的。(神马?不是?兄弟你的智商我救不了了……)

            是的,不这样跳的人对不起社会啊,浪费时间就是浪费青春,浪费青春就是犯罪。

            好的,既然你是这样跳的,那你能告诉我你是怎么知道从A只要跳2个格子就会刚好到B的?难道你在空中使用了GPRS全球卫星定位系统?你少来好么!主页君现在都没用过这种东西,你一只白白嫩嫩下酒菜的小兔子还用这个?笑死我吗?哈哈,你一定是出发前就偷偷学普通兔子一步一步跳过一遍,然后拿个本子做小抄,记录好从每个格子跳任意步会到达的地方,然后赶在天亮之前回来,风光的按照踩点计划大步的跳,让我们觉得你很厉害的样子,我没说错吧?不过看在你有这个诚心的份上,还是为你的聪明鼓掌吧。

     

    【三】

            从前,有一只可爱得不得了的小白兔,它想从A地去往遥远的1(此处省略很多0)个地方,因为它真的是太没事情做了。

     

     

            普通小白兔:

                从离开家门的那天起,我就没有想过要放弃一步一步地跳往终点。(嗯,加油)

            超级小白兔:

                轻轻松松,绝不多走一步。(哼哼)

     

            你想知道最后的结果吗?呵呵,好像还没有出结果……

            写给普通小白兔的话:

                亲爱的小白兔,我知道你勇毅,你质朴,但是,苦海无涯,回头是岸。

            写给超级小白兔的话:

                我不知道你的小抄本是否还够用,我不知道你摸着黑就出门是为了什么,你不觉得你的行踪早就已经暴露了吗?你以为你很聪明吗?不,你错了,你就一下酒菜,永远都是,因为你不知道倍增算法,这是你失败的根源,再见,我心中永远不会逝去的蠢兔子。

     

    ---------------------------------------------------------------------------------------------- 卖萌分割线 ----------------------------------------------------------------------------------------------------

     

            普通兔子 = 速度慢,无资源损耗 || 超级兔子 = 速度快,多资源损耗

     

            还记得那只离我们远去的2B兔子吗?对,其实我们早该想到了,越蠢得不可思议的兔子身上竟然有巨大的宝藏,再看看它的名字吧,“2B”!去掉一个“B”!就是“2”!对,你没有听错,就是“2”,你能想到4、8、16、32吗?

            再想想,超级兔子的小抄本不够用,不就是因为它为了应对所有的目的地信息,它记录下了任何一个格子跳任意步会到达的格子,100个格子它要记录大概5000条信息,1000个格子大概要记录500000条信息,10000个格子它大概要记录50000000条信息,至于你晕没晕,我相信它应该晕了。

            可不可以把记录的信息数降到最低呢?当然可以,2B兔子帮你忙,让你用2战胜敌人。

            当你只记录任何一个格子跳1、2、4、8、16……步会到达的格子的时候,你有没有发现信息数突然少了好多好多啊!真的少了好多好多啊!100个格子只要500条左右,1000个格子只要5000条左右,10000个格子只要50000条左右,不比不知道,一比吓一跳啊!

            安心小抄五十年,健康生活一辈子。

            从此,超级小白兔成为了聪明小白兔,它的生活是这样的:

     

            在夜深人静的时候,它偷偷出门做小抄,记录下从每个格子跳1、2、4、8……个格子后会到达的格子,然后在太阳出来后,它在众目睽睽之下,开始了表演。

            从A出发:若跳8个格子(超过B了,放弃)

                      若跳4个格子(超过B了,放弃)

                      若跳2个格子(没超过B,跳吧)

                      若跳1个格子(没超过B,跳吧)

            从B出发:…………

     

            多么轻松的事情,只要一本很薄的小抄就可以了,最关键的是:它绝对不会连着跳两步都是跳相同的格子数,因为如果跳两次2个格子都是可行的话,那么它干嘛不跳4个格子捏?

            我们可是从多到少来判断的啊!!

     

            好的,聪明小白兔白天的事情你已经看懂了,且看它晚上是怎么打小抄的吧。

            从A出发跳1步到1(记录下来)

            从1出发跳1步到2(记录下来)

            …………(跳1步的记录完毕)

     

            从A出发跳2步?就是从A出发跳1步再跳1步的到的地方,翻看小抄,直接誊写从1出发跳1步会到的2这个格子作为A跳2步会到的格子。

            从1出发跳2步?跟刚才一样,直接誊写。

            …………(跳2步的记录完毕)

     

            从A出发跳4步?你还真去跳4步?不,它也就是等于从A出发跳2步到的2号点再跳2步会到的格子,那么我们直接誊写2号格子跳2步会到的格子就可以了。

            ……

            ……

     

            看看聪明小白兔多么聪明!也许还有自认为更聪明的:

                “在记录A跳4步会到的格子的时候,为什么不直接从A跳4步看到了哪里再记录下来呢?跳4步跟跳1步的代价不是一样的么”

                “我这样回答你好了!把你丢在纽约的一个公交车站,问你一条线路的下一个站是什么?你怎么办?当然是自己亲自走到下一个站就知道了!那如果问你接下来的第4个站是什么?难道你可以直接走到第4个站而不用途径其它的站点了吗?这不现实,你还是要一个一个站的走,因为关键在于你只能知道你目前所在站点的下一个站是什么,想知道下下个站,除非你已经到了下个站,兔子跳格子也跟这类似,虽然聪明小白兔神通广大,但是不至于伟大到可以提前预知跳几步会到哪里啊!!”

     

            从此,聪明小白兔避免了成为人类的下酒菜,而被一群OIER们像神一样的供奉了起来,不要问它为什么,因为它也不知道,貌似只是某人卖了个小萌,事情就变成这样了。

     

                                                                                                                                                                                                               

    展开全文
  • 倍增算法及其应用倍增算法及其应用 前言倍增算法及其应用倍增与其说是一种算法不如说是一种思想倍增这一思想在OI中也占有不小的地位它既直接被设计为解决某些问题的特定算法又可以与其它的算法结合优化时间复杂度...
  • 关于简单倍增算法倍增的解释st算法 倍增的解释 关于倍增算法,顾名思义,就是成倍增长,来跳过一些可以省略的计算,达到加速的效果。 st算法 说到倍增,就不得不提st算法,这大概是倍增最典型的一个应用了。 st...

    关于简单倍增算法

    倍增的解释

    关于倍增算法,顾名思义,就是成倍增长,来跳过一些可以省略的计算,达到加速的效果。

    st算法

    说到倍增,就不得不提st算法,这大概是倍增最典型的一个应用了。
    st算法,适用于RMQ问题(区间最大值),也就是求出一个序列中,数值最大的一项。朴素做法自然是一遍扫描找最大值,但是当题目询问次数很多的时候,就很有可能超时,因此用倍增算法来进行一个优化。

    以下是st算法求解RMQ问题的实现:

    首先,我们用f[i][j]来表示在序列a中,第i位数字以后数2j个数之中的最大值,那么就可以得到f[i][0]=a[i]。

    接下来进行一个DP的过程:

    for(int j = 1;j <= ( log2(n) ); j++)
    	for(int i = 1;i <= n - (1 << j) + 1; i++)
    		f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    

    f[i][j]表示的区间为[i,i+2j]中的最大值,而2j=2*2j-1=2j-1+2j-1,因此,我们可以把区间[i,i+2j]分成[i,i+2j-1]和[i+2j-1+1,2j]。既然已经可以把区间划分成两份,那么DP的思路便很明了了,f[i][j]的值便可以求出来。

    但是,问题所询问的区间并不一定恰好是2的幂次方,有可能会超出区间。

    所以,设l为区间长度,在查询时我们可以求出一个k=log2(l),向下取整。

    那么就有:l/2<=2k<=l

    max(f[i][k],f[i+2j-2k][k])便是所求区间的最大值。

    第一次写博客,写不好还请见谅,晚上也有点困了,上代码吧。

    Luogu P3865

    #include<cstdio>
    #include<iostream>
    #include<cmath>
    
    using namespace std;
    
    long f[100001][40];
    int n,m;
    
    int main(){
        cin>>n>>m;
        
        int temp;
        for(int i=1;i<=n;i++){
            scanf("%d",&temp);
            
            f[i][0]=temp;
        }
        for(int k=1;k<=(int)log2(n);k++){
            for(int i=1;i<=n-(1<<k)+1;i++){
                f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
            }
        }
        int l,r;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&l,&r);
            
            int k=log2(r-l+1);
            
            printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
        }
        return 0;
    }
    
    展开全文
  • 后缀数组倍增算法实现 + RMQ问题ST算法实现
  • LCA倍增算法

    2018-03-30 21:32:00
    倍增算法的前期铺垫 我们记节点v到根的深度为depth(v)。那么如果节点w是节点u和节点v的最近公共祖先的话,让u往上走(depth(u)-depth(w))步,让v往上走(depth(v)-depth(w))步,都将走到节点w。因此,我们首先让u和v...
    一.倍增算法的前期铺垫

    我们记节点v到根的深度为depth(v)。那么如果节点w是节点u和节点v的最近公共祖先的话,让u往上走(depth(u)-depth(w))步,让v往上走(depth(v)-depth(w))步,都将走到节点w。因此,我们首先让u和v中较深的一个往上走|depth(u)-depth(v)|步,再一起一步步往上走,直到走到同一个节点,就可以在O(depth(u)+depth(v))的时间内求出LCA。

    由于节点的最大深度为n,所以这个方法在最坏的情况下一次查询时间复杂度就要O(n),这显然是不够的。于是我们开始考虑优化。

    二.倍增算法的实现过程

    分析刚才的算法,两个节点到达同一节点后,不论怎么向上走,达到的显然还是同一节点。利用这一点,我们就能够利用二分搜索求出到达最近公共祖先的最小步数了。

    首先我们要进行预处理。对于任意的节点,可以通过fa2[v]=fa[fa[v]]得到其向上走2步到达的顶点,再利用这个信息,又可以通过fa4[v]=fa2[fa2[v]]得到其向上走4步所到的顶点。以此类推,我们可以得到其向上走2^k步所到的顶点fa[v][k],预处理的时间点复杂度为O(nlogn)。

    有了k=floor(logn)以内的所有信息后,就可以进行二分所搜的,每次查询的时间复杂度为O(logn)。

    以poj1330为例

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<cmath>
    #include<cstring>
    using namespace std;
    vector<int>v[10010];
    int fa[10010][100];//fa[i][j]表示从i节点走2^j步可以达到的祖先节点 
    int depth[10010];//记录每个节点的深度 
    int n;
    void dfs(int u,int pre,int dep)
    {
        fa[u][0]=pre;
        depth[u]=dep;
        for(int i=0;i<v[u].size();i++)
        {
            int p=v[u][i];
            dfs(p,u,dep+1);
        }
    }
    void init(int root)
    {
        dfs(root,-1,0);
        for(int j=0;(1<<(j+1))<=n;j++)
        {
            for(int i=1;i<=n;i++)
            {
                if(fa[i][j]<0)
                    fa[i][j+1]=-1;
                else
                    fa[i][j+1]=fa[fa[i][j]][j];
            }
        } 
    }
    int LCA(int u,int v)
    {
        if(depth[u]>depth[v])
            swap(u,v);
        int temp=depth[v]-depth[u];
        //cout<<temp<<endl;
        for(int i=0;(1<<i)<=temp;i++)
        {
            if((1<<i)&temp)
            {
                v=fa[v][i];
                //cout<<v<<endl;
            }
            
        }
        if(v==u)
        return u;
        for(int i=int(log(n*1.0));i>=0;i--)
        {
            if(fa[u][i]!=fa[v][i])
            {
                u=fa[u][i];
                v=fa[v][i];
            }
        }
        return fa[u][0];
    }
    int main()
    {
        int T,k,x,y;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
                v[i].clear();
            memset(fa,0,sizeof(fa));
            for(int i=1;i<=n-1;i++)
            {
                scanf("%d%d",&x,&y);
                v[x].push_back(y);
                fa[y][0]=x;
            }
            for(int i=1;i<=n;i++)
            {
                if(fa[i][0]==0)
                {
                    k=i;
                    break;
                }
            }
            //cout<<k<<endl;
            init(k);
            scanf("%d%d",&x,&y);
            printf("%d\n",LCA(x,y));    
        }
    }

     

     

    转载于:https://www.cnblogs.com/flightless/p/8678689.html

    展开全文
  • 趣说倍增算法

    2019-10-08 05:59:06
    一直觉得倍增算法是个很神奇的东西,所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER,我非常讨厌在看别人的算法解析时整版的i,j,k等我看到鼠标就惯性移到右上角的符号语言,所以我想用最形象的方式来...
     

    白话倍增[转]

     

    【序言】

            我认为吧,所有能够优化复杂度的算法都是神奇的,所有能够化繁琐为形象的文字都是伟大的。一直觉得倍增算法是个很神奇的东西,所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER,我非常讨厌在看别人的算法解析时整版的ijk等我看到鼠标就惯性移到右上角的符号语言,所以我想用最形象的方式来纪念它。

     

    【一】

            从前,有一只可爱得不得了的小白兔,它想从A地去往遥远的B地。


     

            2B小白兔:

                向右边跳一步,左边跳一步,再向右边跳很多步,再……(对不起,这个太脑残了)

            普通小白兔:

                向右边跳一步,再跳一步,再跳一步……再跳一步,哇,到了!好开心!

            超级小白兔:

                向右边跳一大步,一步跳到B,然后默默回头,鄙视一下那只一步一步跳的小白兔。

     

            我相信作为一个正常人,是不会考虑到2B小白兔的这种做法的,因为它太脑残了。

            同时我也相信,作为一个正常人,也不会考虑到超级小白兔的这种做法的,因为……

                “我擦!你什么时候说可以这样跳了!(愤怒)”

                “我什么时候说不可以了!(卖萌)”

            但是你不得不承认,超级小白兔还是有两把刷子的,因为它真的是太厉害了,厉害得你想都没有想到。

     

    【二】

            从前,有一只可爱得不得了的小白兔,它想从A地去往遥远的BCDEF这几个让它魂牵梦萦的地方。(不要问我从哪里来,我的梦想在远方)


     

     

            2B小白兔:

                (对不起,我的生命有限,我不想再提到它了)

            普通小白兔:

                一步又一步,生命不息,跳跃不止。

            超级小白兔:

                一步到B,再一步到C,再一步到D,再一步到E,再一步到F,完工。

     

            你不用解释,我深知你就想当那只超级小白兔,哼,你肯定是那样跳的。(神马?不是?兄弟你的智商我救不了了……)

            是的,不这样跳的人对不起社会啊,浪费时间就是浪费青春,浪费青春就是犯罪。

            好的,既然你是这样跳的,那你能告诉我你是怎么知道从A只要跳2个格子就会刚好到B的?难道你在空中使用了GPRS全球卫星定位系统?你少来好么!主页君现在都没用过这种东西,你一只白白嫩嫩下酒菜的小兔子还用这个?笑死我吗?哈哈,你一定是出发前就偷偷学普通兔子一步一步跳过一遍,然后拿个本子做小抄,记录好从每个格子跳任意步会到达的地方,然后赶在天亮之前回来,风光的按照踩点计划大步的跳,让我们觉得你很厉害的样子,我没说错吧?不过看在你有这个诚心的份上,还是为你的聪明鼓掌吧。

     

    【三】

            从前,有一只可爱得不得了的小白兔,它想从A地去往遥远的1(此处省略很多0)个地方,因为它真的是太没事情做了。

     

     

            普通小白兔:

                从离开家门的那天起,我就没有想过要放弃一步一步地跳往终点。(嗯,加油)

            超级小白兔:

                轻轻松松,绝不多走一步。(哼哼)

     

            你想知道最后的结果吗?呵呵,好像还没有出结果……

            写给普通小白兔的话:

                亲爱的小白兔,我知道你勇毅,你质朴,但是,苦海无涯,回头是岸。

            写给超级小白兔的话:

                我不知道你的小抄本是否还够用,我不知道你摸着黑就出门是为了什么,你不觉得你的行踪早就已经暴露了吗?你以为你很聪明吗?不,你错了,你就一下酒菜,永远都是,因为你不知道倍增算法,这是你失败的根源,再见,我心中永远不会逝去的蠢兔子。

     

    ---------------------------------------------------------------------------------------------- 卖萌分割线 ----------------------------------------------------------------------------------------------------

     

            普通兔子 速度慢,无资源损耗 || 超级兔子 速度快,多资源损耗

     

            还记得那只离我们远去的2B兔子吗?对,其实我们早该想到了,越蠢得不可思议的兔子身上竟然有巨大的宝藏,再看看它的名字吧,“2B”!去掉一个“B”!就是“2”!对,你没有听错,就是“2”,你能想到481632吗?

            再想想,超级兔子的小抄本不够用,不就是因为它为了应对所有的目的地信息,它记录下了任何一个格子跳任意步会到达的格子,100个格子它要记录大概5000条信息,1000个格子大概要记录500000条信息,10000个格子它大概要记录50000000条信息,至于你晕没晕,我相信它应该晕了。

            可不可以把记录的信息数降到最低呢?当然可以,2B兔子帮你忙,让你用2战胜敌人。

            当你只记录任何一个格子跳124816……步会到达的格子的时候,你有没有发现信息数突然少了好多好多啊!真的少了好多好多啊!100个格子只要500条左右,1000个格子只要5000条左右,10000个格子只要50000条左右,不比不知道,一比吓一跳啊!

            安心小抄五十年,健康生活一辈子。

            从此,超级小白兔成为了聪明小白兔,它的生活是这样的:

     

            在夜深人静的时候,它偷偷出门做小抄,记录下从每个格子跳1248……个格子后会到达的格子,然后在太阳出来后,它在众目睽睽之下,开始了表演。

            从A出发:若跳8个格子(超过B了,放弃)

                      若跳4个格子(超过B了,放弃)

                      若跳2个格子(没超过B,跳吧)

                      若跳1个格子(没超过B,跳吧)

            从B出发:…………

     

            多么轻松的事情,只要一本很薄的小抄就可以了,最关键的是:它绝对不会连着跳两步都是跳相同的格子数,因为如果跳两次2个格子都是可行的话,那么它干嘛不跳4个格子捏?

            我们可是从多到少来判断的啊!!

     

            好的,聪明小白兔白天的事情你已经看懂了,且看它晚上是怎么打小抄的吧。

            从A出发跳1步到1(记录下来)

            从1出发跳1步到2(记录下来)

            …………(跳1步的记录完毕)

     

            从A出发跳2步?就是从A出发跳1步再跳1步的到的地方,翻看小抄,直接誊写从1出发跳1步会到的2这个格子作为A2步会到的格子。

            从1出发跳2步?跟刚才一样,直接誊写。

            …………(跳2步的记录完毕)

     

            从A出发跳4步?你还真去跳4步?不,它也就是等于从A出发跳2步到的2号点再跳2步会到的格子,那么我们直接誊写2号格子跳2步会到的格子就可以了。

            ……

            ……

     

            看看聪明小白兔多么聪明!也许还有自认为更聪明的:

                “在记录A4步会到的格子的时候,为什么不直接从A4步看到了哪里再记录下来呢?跳4步跟跳1步的代价不是一样的么”

                “我这样回答你好了!把你丢在纽约的一个公交车站,问你一条线路的下一个站是什么?你怎么办?当然是自己亲自走到下一个站就知道了!那如果问你接下来的第4个站是什么?难道你可以直接走到第4个站而不用途径其它的站点了吗?这不现实,你还是要一个一个站的走,因为关键在于你只能知道你目前所在站点的下一个站是什么,想知道下下个站,除非你已经到了下个站,兔子跳格子也跟这类似,虽然聪明小白兔神通广大,但是不至于伟大到可以提前预知跳几步会到哪里啊!!”

     

            从此,聪明小白兔避免了成为人类的下酒菜,而被一群OIER们像神一样的供奉了起来,不要问它为什么,因为它也不知道,貌似只是某人卖了个小萌,事情就变成这样了。

     

                                                                                                                                 完

     

     


    版权声明:本文为博主(JarjingX)原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    本文链接:https://blog.csdn.net/JarjingX/article/details/8180560

     

    转载于:https://www.cnblogs.com/phemiku/p/11420617.html

    展开全文
  • 倍增算法的一些应用

    2019-10-06 20:30:07
    我所了解的倍增算法 我所了解的倍增算法大体是这样的,当我们想知道2^n次方这么个长度范围内的某个值(如最大值或者最小值),如果我知道了所有的2^(n-1)次方长度范围内的值,这样我就可以通过我所知道的这些值中算...
  • 基于倍增算法求LCA 二进制拆分
  • 常用的解决LCA问题的算法有:Tarjan算法,Doubly/倍增算法,转化为RMQ问题等。 本文介绍基于DFS+二分搜索的在线算法,Doubly/倍增算法。(此处二分不同于二分查找算法那种) 算法初探: 对于已知的一棵树(已编号),...
  • 【白话系列】倍增算法

    万次阅读 多人点赞 2012-11-13 22:06:04
    一直觉得倍增算法是个很神奇的东西,所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER,我非常讨厌在看别人的算法解析时整版的i,j,k等我看到鼠标就惯性移到右上角的符号语言,所以我想用最形象的方式来...
  • 后缀数组与倍增算法

    2019-01-22 16:02:05
    后缀数组定义:https://www.geeksforgeeks.org/suffix-array-set-1-introduction/ 详解后缀数组... 注意rank数组是所有后缀字典排序后的排名顺序   详解倍增算法https://www.cnblogs.com/nietz...
  • 最近在做字符串方面的训练,做到后缀数组时卡了好久,后缀数组的实现有两种方法,而我看的是倍增算法,其实倍增算法的思路还是很简单的(详见白书),只是给的模板代码对于我这种渣渣来说有点艰难,弄了好久才弄懂。...
  • lca倍增算法模板

    2016-09-10 10:14:37
    1431: LCA 最近公共祖先 题目描述 给一棵树, 节点数为N(1 输入 第一行: 节点数N 以下N行, 第i + 1行: 点i的父亲节点Father[i] (假定根的父亲是0) ...每个询问包含两个整数i, j你的程序应按照询问的...倍增算法:主要
  • 最近公共祖先 LCA 倍增算法倍增算法可以在线求树上两个点的LCA,时间复杂度为nlogn预处理:通过dfs遍历,记录每个节点到根节点的距离dist[u],深度d[u]init()求出树上每个节点u的2^i祖先p[u][i]求最近公共祖先,根据...
  • 建议先看看这篇博文:https://blog.csdn.net/JarjingX/article/details/8180560【白话系列】倍增算法 博主:JarjingX 以下转自:https://blog.csdn.net/wybooooooooo/article/details/80778807 博主:wybooooooooo...
  • 上一套基于二分搜索的lca倍增算法模板 #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; #define exp 1e-8...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,700
精华内容 680
关键字:

倍增算法