洛谷mNOIP模拟赛Day1-斐波那契

题目背景

大样例下发链接：http://pan.baidu.com/s/1c0LbQ2 密码：jigg

题目描述

小 C 养了一些很可爱的兔子。有一天，小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行繁衍：一对兔子从出生后第二个月起，每个月刚开始的时候都会产下一对小兔子。我们假定，在整个过程中兔子不会出现任何意外。

小 C 把兔子按出生顺序，把兔子们从 1 开始标号，并且小 C 的兔子都是 1 号兔子和 1 号兔子的后代。如果某两对兔子是同时出生的，那么小 C 会将父母标号更小的一对优先标号。

如果我们把这种关系用图画下来，前六个月大概就是这样的：

其中，一个箭头 A → B 表示 A 是 B 的祖先，相同的颜色表示同一个月出生的兔子。

为了更细致地了解兔子们是如何繁衍的，小 C 找来了一些兔子，并且向你提出了 m 个问题：她想知道关于每两对兔子 $a_iai 和 b_ibi ，他们的最近公共祖先是谁。你能帮帮小 C 吗？$

一对兔子的祖先是这对兔子以及他们父母（如果有的话）的祖先，而最近公共祖先是指两对兔子所共有的祖先中，离他们的距离之和最近的一对兔子。比如，5 和 7 的最近公共祖先是 2，1 和 2 的最近公共祖先是 1，6 和 6 的最近公共祖先是 6。

输入输出格式

输入格式：

从标准输入读入数据。输入第一行，包含一个正整数 m。输入接下来 m 行，每行包含 2 个正整数，表示 $a_iai 和 b_ibi 。$

输出格式：

输出到标准输出中。输入一共 m 行，每行一个正整数，依次表示你对问题的答案。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

【数据范围与约定】子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。每个测试点的数据规模及特点如下表：

首先考虑70%的数据，

每天新出生的兔子数目一定是f[i]，这个很容易计算得出

然后发现，这f[i]只兔子的父亲一定是1~f[i]，于是模拟这个过程，做一遍LCA即可

再考虑100%的数据，

n达到int以上，无法模拟，

设s[i]=∑f[1~i]，发现第s[i]+1只兔子父亲肯定是1，第s[i]+2只兔子父亲肯定是2，第s[i]+f[i+1]只兔子父亲一定是f[i+1]

于是有思路：二分s数组，使得s[i]+1<=a<=s[i]+f[i+1]，这时候a的父亲就是a-s[i]

这样的话一开始a是大于s[i]的，减过之后就小于s[i]了，至少折半，效率至多是O(logn)，感觉挺快的

对b也做一遍，记录他们的“祖先历程”，然后用两个指针找一下公共祖先就可以了

实际上我是处理到10^6的，如果小于10^6就直接做倍增了，这样可能快一些，不过事实证明是差不多的

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<map>
  7 #include<set>
  8 #include<queue>
  9 #include<vector>
 10 #define INF 0x7f7f7f7f
 11 #define pii pair<int,int>
 12 #define ll long long
 13 #define MAXN 1000005
 14 #define LOG 21
 15 using namespace std;
 16 ll read(){
 17     ll x=0,f=1;char ch=getchar();
 18     while(ch<'0'||ch>'9'){if('-'==ch)f=-1;ch=getchar();}
 19     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 20     return x*f;
 21 }
 22 int fa[LOG][MAXN];
 23 ll M=1000000000005;
 24 ll dep[MAXN];
 25 ll f[MAXN]={1,1,1};
 26 ll s[MAXN]={1,2,3};
 27 vector<ll> v[2];
 28 int lca(int x,int y){
 29     if(dep[x]<dep[y]){
 30         swap(x,y);
 31     }
 32     for(int k=dep[x]-dep[y],p=0;k;p++,k>>=1){
 33         if(k&1){
 34             x=fa[p][x];
 35         }
 36     }
 37     if(x==y){
 38         return x;
 39     }
 40     for(int k=LOG-1;k>=0;k--){
 41         if(fa[k][x]!=fa[k][y]){
 42             x=fa[k][x],y=fa[k][y];
 43         }
 44     }
 45     return fa[0][x];
 46 }
 47 void work(ll a,int t){
 48     ll x=a;
 49     v[t].push_back(x);
 50     while(1){
 51         if(x<MAXN){
 52             break;
 53         }
 54         int L=0,R=60;
 55         while(R-L>1){
 56             int mid=(L+R)/2;
 57             if(s[mid]<x){
 58                 L=mid;
 59             } 
 60             else{
 61                 R=mid;
 62             }
 63         }
 64         if(s[R]<x){
 65             x=x-s[R];
 66         }
 67         else{
 68             x=x-s[L];
 69         }
 70         v[t].push_back(x);
 71     }
 72 }
 73 void init(){
 74     fa[0][2]=fa[0][3]=1;
 75     dep[2]=dep[3]=1;
 76     int i=3,j=0;
 77     while(1){
 78         f[i]=f[i-1]+f[i-2];
 79         s[i]=s[i-1]+f[i];
 80         if(s[i]>M){
 81             break;
 82         }
 83         i++;
 84     }
 85     i=3;
 86     while(1){
 87         for(j=s[i-1]+1;j<=s[i]&&j<MAXN;j++){
 88             fa[0][j]=j-s[i-1];
 89             dep[j]=dep[j-s[i-1]]+1;
 90         }
 91         if(j>=MAXN){
 92             break;
 93         }
 94         i++;
 95     }
 96     for(int k=1;k<LOG;k++){
 97         for(int i=1;i<MAXN;i++){
 98             fa[k][i]=fa[k-1][fa[k-1][i]];
 99         }
100     }    
101 }
102 void solve(){
103     int T=read();
104     while(T--){
105         ll a=read(),b=read();
106         if(a==b){
107             printf("%lld
",a);
108             continue;
109         }
110         if(a<MAXN&&b<MAXN){
111             printf("%d
",lca(a,b));
112         }
113         else{
114             v[0].clear(),v[1].clear();
115             work(a,0);
116             work(b,1);
117             int i=0,j=0,ok=0;
118             while(i<v[0].size()&&j<v[1].size()){
119                 if(v[0][i]==v[1][j]){
120                     printf("%lld
",v[1][j]);
121                     ok=1;break;
122                 }
123                 if(v[0][i]>v[1][j]){
124                     i++;
125                 }
126                 else{
127                     j++;
128                 }
129             }
130             if(!ok){
131                 a=v[0][v[0].size()-1],b=v[1][v[1].size()-1];
132                  printf("%d
",lca(a,b));           
133             }
134         }
135     }
136 }
137 int main()
138 {
139 //    freopen("data.in","r",stdin);
140     init();
141     solve();
142     return 0;
143 }