洛谷P3938斐波那契 题解

题目链接

这么一张图,求LCA的话,可以考虑直接建树来做。

总之不管什么方法,一定要知道每个结点的父子关系。

当然,这里说一下找规律做法。

首先分层写出来结点,图中颜色已经分好了层数。

$i$$f_i$$P$
001
112
213
324,5
436,7,8
559,10,11,12,13
6814,15,16,17,18,19,20,21
$...$$...$$...$

观察写出来的分层结点,显然可以看出来每一层结点的个数构成的数列$f_i$是斐波那契数列。

让$f_i$和分层的结点一一对应,可以找到规律,对于任意结点$P$,令$i$为$P$所在的层数,有$P$的父亲结点为$P-f_{i+1}$。

比如$P=12$的结点,对应的$i=5$,于是有$f_{i+1}=8$,那么它的父亲结点是$P-f_{i+1}=4$。

但是,眼下出现了新的问题,就是没有办法找到$P$所对应的$i$,显然我们需要一个更容易找的规律。

刚刚的规律给了一定的启发,再次观察结点,每一层最后一个结点也构成斐波那契数列。

那么,我们尝试一下把数列上移。

$i$$f_i$$P$
211
322
433
554,5
686,7,8
7139,10,11,12,13
82114,15,16,17,18,19,20,21
$...$$...$$...$

这样,将结点所在的斐波那契数列区间和结点层对齐。

因为斐波那契数列是单调递增的,那么,每次我们只要二分查找,就可以找到$P$所对应的$i$,进而求出$f_i$,那么$P$的父亲结点就是$P-f_{i-1}$。

同样$P=12$的结点,在斐波那契数列中二分查找$P$,得到$i=7$,于是有$f_{i-1}=8$,那么它的父亲结点是$P-f_{i-1}=4$。

然后,既然找到了每一个点的父亲结点,我们就直接暴力递归求LCA就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

typedef long long LL;

const int maxn=65;//最大数据取log发现到60出头足够了

int m;
LL a[maxn];

LL lca(LL x,LL y)
{
if(x<y)
std::swap(x,y);//注意要用比较大的那个向上找。
if(x==y)
return x;
LL *p=std::lower_bound(a,a+maxn,x);//lower_bound原理是二分查找,可以直接找到下确界i。
return lca(y,x-*(p-1));//注意父亲是x-f[i-1],这里用的是指针,不懂的话感性理解算法就好。
}

int main()
{
a[0]=0,a[1]=1;
for(int i=2;i<maxn;i++)
a[i]=a[i-1]+a[i-2];//预处理斐波那契数列
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
LL x,y;
scanf("%lld%lld",&x,&y);
printf("%lld\n",lca(x,y));
}
return 0;
}