51nod 1350 斐波那契表示（递推+找规律）

传送门

题意

分析

我们发现该数列遵循下列规律:

1

1,2

1,2,2

1,2,2,2,3

1,2,2,2,3,2,3,3

我们令A[i]表示f[i]开始长为f[i-1]的i的最短表示和

那么得到A[i]=A[i-1]+A[i-2]+f[i-2]

那么先预处理出每一段和A[i],i不会超过84

先连续加A[i],对于剩余一段，递归处理，具体见代码

感谢qwb

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

int t;

ll n;

ll f[101],A[101];

void init()

{

    A[2]=A[1]=1;

    f[1]=f[2]=1;

    F(i,3,84)

    {

        f[i]=f[i-1]+f[i-2];

        A[i]=A[i-1]+A[i-2]+f[i-2];

    }

}

ll solve(int id,ll num)

{

    if(f[id]==num) return A[id];

    if(f[id-1]>=num) return solve(id-1,num);

    return A[id-1]+num-f[id-1]+solve(id-2,num-f[id-1]);

}

int main()

{

    init();

    for(scanf("%d",&t);t--;)

    {

        scanf("%lld",&n);

        ll sum=0,ans=0;

        int id=0;

        while(sum+f[id+1]<n) sum+=f[++id];

        F(i,1,id) ans+=A[i];

        ans+=solve(id+1,n-sum);

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

    }

    return 0;

}

巴特西

51nod 1350 斐波那契表示（递推+找规律）

传送门

题意

分析

代码

最新文章

热门文章