企业官网建设流程全解析

题目描述

斐波那契数列由000和111开始，后续每一项为前两项之和。所有正整数都可以表示为斐波那契数列中若干不重复项的和。若限制所选集合中不能有两个连续的斐波那契数，则每个正整数的表示方法唯一。这种表示称为斐波那契进制（Fibonaccial base\texttt{Fibonaccial base}Fibonaccial base），使用二进制串表示：从右向左依次对应斐波那契数，使用该数则写111，不使用则写000，且最高位必须为111，表示中不会出现连续的111。给定一组十进制数，要求输出其斐波那契进制表示。

输入格式

第一行包含一个整数NNN（1≤N≤5001 \le N \le 5001≤N≤500），表示后续数字的数量。接下来NNN行，每行包含一个小于100000000100000000100000000的正整数。

输出格式

对于每个输入整数，输出一行，格式为DEC_BASE = FIB_BASE (fib)，其中DEC_BASE为原始十进制数，FIB_BASE为其斐波那契进制表示。

样例输入

10 1 2 3 4 5 6 7 8 9 10

样例输出

1 = 1 (fib) 2 = 10 (fib) 3 = 100 (fib) 4 = 101 (fib) 5 = 1000 (fib) 6 = 1001 (fib) 7 = 1010 (fib) 8 = 10000 (fib) 9 = 10001 (fib) 10 = 10010 (fib)

题目分析

本题要求将十进制正整数转换为斐波那契进制表示。斐波那契进制使用斐波那契数列中不连续的两项之和来唯一表示一个数。转换的关键在于从大到小贪心地选择不超过当前剩余值的最大斐波那契数，并确保不选择相邻的斐波那契数。

斐波那契数列从F1=1F_1 = 1F1​=1、F2=2F_2 = 2F2​=2开始（注意此处的下标与题目中从000开始的序列有所不同，但表示时从右向左依次对应斐波那契数）。由于输入数字小于100000000100000000100000000，斐波那契数增长很快，最多只需约404040项即可覆盖所有可能的输入。

贪心策略的正确性依赖于齐肯多夫定理：每个正整数都可以唯一地表示为不连续的斐波那契数之和。因此，每次选择不超过当前剩余值的最大斐波那契数，即可得到唯一的表示。

解题思路

首先预计算斐波那契数列，从F0=1F_0 = 1F0​=1、F1=2F_1 = 2F1​=2开始，后续项为前两项之和，直到超过最大可能的输入值100000000100000000100000000。实际计算到646464项足够。

对于每个输入数字nnn，从最大的斐波那契数开始向下遍历。若当前斐波那契数FiF_iFi​不超过nnn，则将该位置为111，并从nnn中减去FiF_iFi​；否则该位置为000。由于贪心选择保证了不会选择相邻的斐波那契数，因此最终得到的二进制串不会出现连续的111。

将得到的二进制串去掉前导零后输出。使用bitset可以方便地记录每一位的状态，最后转换为字符串并去除前导零。时间复杂度为O(N×log⁡max⁡(n))O(N \times \log \max(n))O(N×logmax(n))，空间复杂度为O(max⁡log⁡n)O(\max \log n)O(maxlogn)，对于题目规模完全可行。

代码实现

// Fibonaccimal Base// UVa ID: 948// Verdict: Accepted// Submission Date: 2018-03-16// UVa Run Time: 0.000s//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXF=64;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);longlongfibs[MAXF]={1,2},n;for(inti=2;i<MAXF;i++)fibs[i]=fibs[i-1]+fibs[i-2];intcases;cin>>cases;while(cases--){cin>>n;cout<<n<<" = ";bitset<64>finary(0);while(n){for(inti=MAXF-1;i>=0;i--)if(n>=fibs[i]){finary.set(i);n-=fibs[i];break;}}string f=finary.to_string();while(f.size()&&f.front()=='0')f.erase(f.begin());cout<<f<<" (fib)\n";}return0;}

总结

本题的核心是齐肯多夫定理：每个正整数唯一表示为不连续的斐波那契数之和。通过从大到小贪心选择斐波那契数，可以快速得到斐波那契进制表示。实现时需要注意斐波那契数列的起始项为111和222，并确保输出时去掉前导零。时间复杂度为O(N×log⁡max⁡(n))O(N \times \log \max(n))O(N×logmax(n))，空间复杂度为O(max⁡log⁡n)O(\max \log n)O(maxlogn)，能够高效处理所有测试用例。