HZOJ 斐波那契(fibonacci)

先说一个规律：

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

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

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

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

1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 #define LL long long 5 #define int LL 6 using namespace std; 7 int f[70]; 8 int n; 9 inline int read()10 {11int s=0;char a=getchar();12while(a<'0'||a>'9')a=getchar();13while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}14return s;15 }16 signed main()17 {18 // freopen("fibonacci2.in","r",stdin);19 20f[1]=1;for(int i=2;i<=65;i++)f[i]=f[i-1]+f[i-2];21for(int i=2;i<=65;i++)f[i]++;22n=read();23int a,b;24for(int i=1;i<=n;i++)25{26 a=read(),b=read();27 while(a!=b)28 {29 if(a==1||b==1){a=b=1;break;}30 int i;31 i=upper_bound(f+1,f+65,a)-f;i--;32 int fa=a-f[i]+1;33 i=upper_bound(f+1,f+65,b)-f;i--;34 int fb=b-f[i]+1;35 if(fa<fb)b=fb;36 else if(fb<fa)a=fa;37 else {a=fa;b=fb;break;}38 }39 printf("%lld\n",a);40}41 }

View Code