链接：https://ac.nowcoder.com/acm/problem/15663
来源：牛客网

题目描述
Fibonacci数是非常有名的一个数列,它的公式为 f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2。
我们可以把任意一个数x表示成若干不相同的Fibonacci数的和， 比如说14 = 13+1 = 8+5+1 = 8+3+2+1。
如果把Fibonacci数列作为数的位权，即f(i)作为第i位的位权，每位的系数只能是0或者1，从而得到一个01串。 比如14可以表示成 100001，11001，10111。 我们再把这个01串看成2进制，再转成10进制以后就变成了 33，25，23。 为了避免歧义，我们将使用最小的那个值23。
请按照这个过程计算一下10进制整数通过上述转换过程得到的10进制整数。
输入描述:

第一行是一个整数T(1 ≤ T ≤ 10000)，表示样例的个数。
以后每行一个样例，为一个十进制正整数x(1 ≤ x ≤ 109)。

输出描述:

每行输出一个样例的结果。

示例1
输入
复制

5
1
10
100
1000
1000000000

输出
复制

1
14
367
10966
4083305275263

题目分析：
数字用斐波那契拆分，斐波那契对应的项如果被用到就点亮，即二进制的10串开关。

算法分析:
由数学归纳法得斐波那契数列可以构成任意的数字，所以思路是维护一个前缀和，然后循环比较，当这个数的前缀和刚好大于x的时候(刚好的话，可以使得最后的结果是最小的)，下标为i，表明从开始到i的所有数字之中，一定能构成这个数，那么就减去这一个数字，不断维护这个数字x,使得其在二进制最小即是正确答案，维护x的同时，我们用p数组来不断记录二进制的标记情况，从而最后得到答案。

代码：

#include<queue>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
typedef long long ll;
using namespace  std;
ll preSum[1000]; //前缀和
ll arr[1000];
ll f[1000];
bool p[1000];//标记二进制开启状态
int n;
void topow()
{
    f[0] = 1;
    f[1] = 2;
    for (int i = 2; i < 64; i++)
    {
        f[i] = f[i - 1] * 2;
    }
}
void init(int x)//初始化
{
    int i = 0;
    arr[0] = 1;
    arr[1] = 2;
    preSum[0] = 1;
    preSum[1] = 3;
    p[1] = 0;
    p[0] = 0;
    //不能是presum[i] 因为还没被赋值
    for (int i=2;preSum[i-1]<=x;i++)//前缀和达到就可以了
    {
        arr[i] = arr[i - 1] + arr[i - 2];
        preSum[i] = preSum[i - 1] + arr[i];
        p[i] = 0;
        n = i;//大致记录
    }
}
int main()
{
    topow();
    int t;
    cin >> t;
    while (t--)
    {
        ll x;
        cin >> x;
        init(x);
        ll i = 0;
        while (x)
        {
            //找出刚好前缀和能达到的最大值 然后减去最大的
            if (preSum[i] >= x)
            {
                x -= arr[i];
                p[i] = 1;//记录标记情况
                i = 0;//重新搜索、
            }
            else
            {
                i++;                                                    
            }
        }
        //转换即可
        ll ans = 0;
        for (int i =0; i <=n ; i++)
        {
            if (p[i])
            {
                ans += f[i];
            }
        }
        cout << ans << endl;
    }
}