题目描述斐波那契数列由000和111开始后续每一项为前两项之和。所有正整数都可以表示为斐波那契数列中若干不重复项的和。若限制所选集合中不能有两个连续的斐波那契数则每个正整数的表示方法唯一。这种表示称为斐波那契进制Fibonaccial base\texttt{Fibonaccial base}Fibonaccial base使用二进制串表示从右向左依次对应斐波那契数使用该数则写111不使用则写000且最高位必须为111表示中不会出现连续的111。给定一组十进制数要求输出其斐波那契进制表示。输入格式第一行包含一个整数NNN1≤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)题目分析本题要求将十进制正整数转换为斐波那契进制表示。斐波那契进制使用斐波那契数列中不连续的两项之和来唯一表示一个数。转换的关键在于从大到小贪心地选择不超过当前剩余值的最大斐波那契数并确保不选择相邻的斐波那契数。斐波那契数列从F11F_1 1F11、F22F_2 2F22开始注意此处的下标与题目中从000开始的序列有所不同但表示时从右向左依次对应斐波那契数。由于输入数字小于100000000100000000100000000斐波那契数增长很快最多只需约404040项即可覆盖所有可能的输入。贪心策略的正确性依赖于齐肯多夫定理每个正整数都可以唯一地表示为不连续的斐波那契数之和。因此每次选择不超过当前剩余值的最大斐波那契数即可得到唯一的表示。解题思路首先预计算斐波那契数列从F01F_0 1F01、F12F_1 2F12开始后续项为前两项之和直到超过最大可能的输入值100000000100000000100000000。实际计算到646464项足够。对于每个输入数字nnn从最大的斐波那契数开始向下遍历。若当前斐波那契数FiF_iFi不超过nnn则将该位置为111并从nnn中减去FiF_iFi否则该位置为000。由于贪心选择保证了不会选择相邻的斐波那契数因此最终得到的二进制串不会出现连续的111。将得到的二进制串去掉前导零后输出。使用bitset可以方便地记录每一位的状态最后转换为字符串并去除前导零。时间复杂度为O(N×logmax(n))O(N \times \log \max(n))O(N×logmax(n))空间复杂度为O(maxlogn)O(\max \log n)O(maxlogn)对于题目规模完全可行。代码实现// Fibonaccimal Base// UVa ID: 948// Verdict: Accepted// Submission Date: 2018-03-16// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXF64;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);longlongfibs[MAXF]{1,2},n;for(inti2;iMAXF;i)fibs[i]fibs[i-1]fibs[i-2];intcases;cincases;while(cases--){cinn;coutn ;bitset64finary(0);while(n){for(intiMAXF-1;i0;i--)if(nfibs[i]){finary.set(i);n-fibs[i];break;}}string ffinary.to_string();while(f.size()f.front()0)f.erase(f.begin());coutf (fib)\n;}return0;}总结本题的核心是齐肯多夫定理每个正整数唯一表示为不连续的斐波那契数之和。通过从大到小贪心选择斐波那契数可以快速得到斐波那契进制表示。实现时需要注意斐波那契数列的起始项为111和222并确保输出时去掉前导零。时间复杂度为O(N×logmax(n))O(N \times \log \max(n))O(N×logmax(n))空间复杂度为O(maxlogn)O(\max \log n)O(maxlogn)能够高效处理所有测试用例。
UVa 948 Fibonaccial Base
题目描述斐波那契数列由000和111开始后续每一项为前两项之和。所有正整数都可以表示为斐波那契数列中若干不重复项的和。若限制所选集合中不能有两个连续的斐波那契数则每个正整数的表示方法唯一。这种表示称为斐波那契进制Fibonaccial base\texttt{Fibonaccial base}Fibonaccial base使用二进制串表示从右向左依次对应斐波那契数使用该数则写111不使用则写000且最高位必须为111表示中不会出现连续的111。给定一组十进制数要求输出其斐波那契进制表示。输入格式第一行包含一个整数NNN1≤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)题目分析本题要求将十进制正整数转换为斐波那契进制表示。斐波那契进制使用斐波那契数列中不连续的两项之和来唯一表示一个数。转换的关键在于从大到小贪心地选择不超过当前剩余值的最大斐波那契数并确保不选择相邻的斐波那契数。斐波那契数列从F11F_1 1F11、F22F_2 2F22开始注意此处的下标与题目中从000开始的序列有所不同但表示时从右向左依次对应斐波那契数。由于输入数字小于100000000100000000100000000斐波那契数增长很快最多只需约404040项即可覆盖所有可能的输入。贪心策略的正确性依赖于齐肯多夫定理每个正整数都可以唯一地表示为不连续的斐波那契数之和。因此每次选择不超过当前剩余值的最大斐波那契数即可得到唯一的表示。解题思路首先预计算斐波那契数列从F01F_0 1F01、F12F_1 2F12开始后续项为前两项之和直到超过最大可能的输入值100000000100000000100000000。实际计算到646464项足够。对于每个输入数字nnn从最大的斐波那契数开始向下遍历。若当前斐波那契数FiF_iFi不超过nnn则将该位置为111并从nnn中减去FiF_iFi否则该位置为000。由于贪心选择保证了不会选择相邻的斐波那契数因此最终得到的二进制串不会出现连续的111。将得到的二进制串去掉前导零后输出。使用bitset可以方便地记录每一位的状态最后转换为字符串并去除前导零。时间复杂度为O(N×logmax(n))O(N \times \log \max(n))O(N×logmax(n))空间复杂度为O(maxlogn)O(\max \log n)O(maxlogn)对于题目规模完全可行。代码实现// Fibonaccimal Base// UVa ID: 948// Verdict: Accepted// Submission Date: 2018-03-16// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXF64;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);longlongfibs[MAXF]{1,2},n;for(inti2;iMAXF;i)fibs[i]fibs[i-1]fibs[i-2];intcases;cincases;while(cases--){cinn;coutn ;bitset64finary(0);while(n){for(intiMAXF-1;i0;i--)if(nfibs[i]){finary.set(i);n-fibs[i];break;}}string ffinary.to_string();while(f.size()f.front()0)f.erase(f.begin());coutf (fib)\n;}return0;}总结本题的核心是齐肯多夫定理每个正整数唯一表示为不连续的斐波那契数之和。通过从大到小贪心选择斐波那契数可以快速得到斐波那契进制表示。实现时需要注意斐波那契数列的起始项为111和222并确保输出时去掉前导零。时间复杂度为O(N×logmax(n))O(N \times \log \max(n))O(N×logmax(n))空间复杂度为O(maxlogn)O(\max \log n)O(maxlogn)能够高效处理所有测试用例。
