NOIP 模拟 9 斐波那契

题解

这是一道推规律的题。

首先，这道题送分不少，先考虑 \(70pts\)，直接暴力 \(\mathcal O(n)\) 建边，\(\mathcal O(logn)\) 求 \(lca\)

其次对于 \(|a_i-b_i|\leq 1\) 的情况，直接输出 \(1\)，原因显然。

那么正解是 \(fibonacci\)，我们设 \(f_i\) 表示第 \(i\) 个月的兔子数量，那么我们根据题意，发现转移为 \(f_i=f_{i-1}+f_{i-2}\)，因为只有出生两个月的兔子能生。

那么对于一个第 \(i\) 月出生的兔子，其编号为 \(id_i=f_{i-1}+j\)，\(j\) 为其父亲编号，那么我们就可以根据此来求父亲。

这就是一个完美的 \(fibonacci\)。所以我们可以预处理出 \(fibonacci\)，然后二分，再根据求 \(lca\) 的思想跳，因为树高很小，所以我们可以视为常数。

复杂度 \(\mathcal O(mlogn)\)

Code:

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

#define int long long

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    inline int read() {

        register int x=0,f=1;char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        return x*f;

    }

}

using IO::read;

namespace nanfeng{

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    static const int N=63;

    int f[N],m;

    int lca(int a,int b) {

        int da=lower_bound(f,f+61,a)-f,db=lower_bound(f,f+61,b)-f;

        if (da>db) swap(da,db),swap(a,b);

        while(a!=b) {

            b=b-f[lower_bound(f,f+61,b)-f-1];

            db=lower_bound(f,f+61,b)-f;

            if (da>db) swap(da,db),swap(a,b);

        }

        return a;

    }

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        f[0]=f[1]=1;

        for (ri i(2);i<=62;p(i)) f[i]=f[i-1]+f[i-2];

        f[0]=0;//为了防止二分时边界溢出，f[0]处理为0

        m=read();

        for (ri i(1);i<=m;p(i)) {

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

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

        }

        return 0;

    }

    #undef int

}

int main() {return nanfeng::main();}

巴特西

NOIP 模拟 9 斐波那契

题解

最新文章

热门文章