HZOJ 斐波那契(fibonacci)

先说一个规律：

如图将每个月出生的兔子的编号写出来，可以发现一只兔子在哪一列他的父亲就是谁。

每列的首项可以通过菲波那契求得。

然后你就可以像我一样通过这个规律打表每个点的父亲，预处理出倍增数组，倍增求LCA，省掉了建树。期望得分70，实际得分50。

但是其实这已经很接近正解了：对于点i，那么fa[i]+(i所在行首项)-1=i，移项，首项可以二分求得，就可以用Olog60的复杂度找到一个点的父亲节点，所以对于每次询问暴力求就行了。

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #define LL long long

 #define int LL

 using namespace std;

 int f[];

 int n;

 inline int read()

 {

     int s=;char a=getchar();

     while(a<''||a>'')a=getchar();

     while(a>=''&&a<=''){s=s*+a-'';a=getchar();}

     return s;

 }

 signed main()

 {

 //    freopen("fibonacci2.in","r",stdin);

     f[]=;for(int i=;i<=;i++)f[i]=f[i-]+f[i-];

     for(int i=;i<=;i++)f[i]++;

     n=read();

     int a,b;

     for(int i=;i<=n;i++)

     {

         a=read(),b=read();

         while(a!=b)

         {

             if(a==||b==){a=b=;break;}

             int i;

             i=upper_bound(f+,f+,a)-f;i--;

             int fa=a-f[i]+;

             i=upper_bound(f+,f+,b)-f;i--;

             int fb=b-f[i]+;

             if(fa<fb)b=fb;

             else if(fb<fa)a=fa;

             else {a=fa;b=fb;break;}

         }

         printf("%lld\n",a);

     }

 }