题目描述Fibonacci\texttt{Fibonacci}Fibonacci数列定义为1,2,3,5,8,13,…1,2,3,5,8,13,\ldots1,2,3,5,8,13,…注意只有一个111。给定一个二进制串若从高位到低位分别乘以对应的Fibonacci\texttt{Fibonacci}Fibonacci数从大到小则称为Fibinary\texttt{Fibinary}Fibinary数。例如1010表示1⋅50⋅31⋅20⋅171\cdot5 0\cdot3 1\cdot2 0\cdot1 71⋅50⋅31⋅20⋅17。为了保证表示唯一规定任意两个相邻的111是不允许的即使用更大的Fibonacci\texttt{Fibonacci}Fibonacci项优先。给定两个合法的Fibinary\texttt{Fibinary}Fibinary数求它们的和并以Fibinary\texttt{Fibinary}Fibinary形式输出。输入格式输入包含多个测试用例每个用例由两行组成每行一个Fibinary\texttt{Fibinary}Fibinary数字字符串。相邻用例之间有一个空行。每个字符串长度不超过100100100。输入直至文件结束。输出格式对于每个测试用例输出一行为两个Fibinary\texttt{Fibinary}Fibinary数之和的Fibinary\texttt{Fibinary}Fibinary表示。相邻用例的输出之间用一个空行分隔。样例输入10010 1 10000 1000 10000 10000样例输出10100 100000 100100题目分析Fibinary\texttt{Fibinary}Fibinary数的位权从右到左依次为F11,F22,F33,F45,F58,…F_11, F_22, F_33, F_45, F_58,\ldotsF1​1,F2​2,F3​3,F4​5,F5​8,…即第iii位从000开始的权值为Fi1F_{i1}Fi1​。有效表示中不允许出现相邻的111因为FiFi1Fi2F_i F_{i1} F_{i2}Fi​Fi1​Fi2​所以相邻的111可以合并为高一位的111这是为了使表示唯一。两个Fibinary\texttt{Fibinary}Fibinary数相加时需要对每一位进行加法并处理进位。由于斐波那契数的加法规则特殊不能简单用二进制进位。例如最低位两个111相加111111应进位到次高位因为F1F12F2F_1F_12F_2F1​F1​2F2​即222对应第111位的权值222第二位两个111相加222222应分解为F1F3F_1F_3F1​F3​即产生第000位和第222位的两个111更高位两个111相加则产生低两位的两个111因为FiFiFi−1Fi−2F_i F_i F_{i-1} F_{i-2}Fi​Fi​Fi−1​Fi−2​当i≥2i \ge 2i≥2。加法过程中还需不断调整消除相邻的111。解题思路采用位串模拟加法并在每次修改后调用调整函数消除相邻111。具体步骤如下步骤1\texttt{1}1. 读入两个Fibinary\texttt{Fibinary}Fibinary字符串AAA和BBB。为了便于从低位处理将两个字符串反转并在末尾补零至足够长度比最大长度多101010位以容纳可能的进位。步骤2\texttt{2}2. 对反转后的字符串分别调用adjust\texttt{adjust}adjust函数确保它们已经消除相邻111虽然输入已合法但为保险。步骤3\texttt{3}3. 执行加法过程循环直到没有变化从最低位开始遍历如果BBB的当前位为111则将其加到AAA的对应位上。具体处理规则若AAA的当前位为000则直接将该位置111并将BBB的该位置000。若AAA的当前位为111即两个111相加若i0i0i0最低位则112112112应进位到次高位即A[1]A[1]A[1]置111A[0]A[0]A[0]和B[0]B[0]B[0]置000。若i1i1i1则224F3F1224F_3F_1224F3​F1​因此将A[0]A[0]A[0]和A[2]A[2]A[2]置111A[1]A[1]A[1]和B[1]B[1]B[1]置000。若i≥2i \ge 2i≥2则FiFiFi−1Fi−2F_i F_i F_{i-1} F_{i-2}Fi​Fi​Fi−1​Fi−2​所以将B[i−1]B[i-1]B[i−1]和B[i−2]B[i-2]B[i−2]置111B[i]B[i]B[i]置000。每次操作后立即调用adjust\texttt{adjust}adjust消除新产生的相邻111并跳出当前遍历重新开始直到所有位处理完毕且没有变化。步骤4\texttt{4}4. 处理完成后从结果字符串AAA的末尾删除多余的前导零即高位零再反转回正常顺序输出。adjust\texttt{adjust}adjust函数负责消除相邻的111从高位到低位扫描若发现相邻两个111则将其替换为001即更高的下一位置111这两个位置000然后重新扫描直到没有相邻111为止。这一操作基于FiFi1Fi2F_i F_{i1} F_{i2}Fi​Fi1​Fi2​。该算法时间复杂度O(L2)O(L^2)O(L2)其中LLL为字符串长度最多100100100完全可行。代码实现// Fibinary Numbers// UVa ID: 763// Verdict: Accepted// Submission Date: 2016-12-01// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intcases0;voidadjust(stringnumber1){boolupdatedfalse;do{updatedfalse;for(intjnumber1.length()-1;j0;j--)if(number1[j-1]1number1[j]1){intkj-1;while(number1[k]1number1[k1]1){number1[k]number1[k1]0;number1[k2]1;k2;}updatedtrue;break;}}while(updated);}voidadd(string number1,string number2){intmax_lengthmax(number1.length(),number2.length());max_length10;reverse(number1.begin(),number1.end());reverse(number2.begin(),number2.end());while(number1.length()max_length)number1.push_back(0);while(number2.length()max_length)number2.push_back(0);adjust(number1);adjust(number2);boolupdatedfalse;do{updatedfalse;for(inti0;inumber2.length();i){if(number2[i]0)continue;if(number1[i]1){updatedtrue;if(i0){number2[i]number1[i]0;number1[i1]1;}elseif(i1){number1[i1]number1[i-1]1;number1[i]number2[i]0;}else{number2[i]0;number2[i-1]number2[i-2]1;}}else{updatedtrue;number1[i]1,number2[i]0;}if(updated){adjust(number1);break;}}}while(updated);while(number1.back()0number1.length()1)number1.erase(number1.end()-1);reverse(number1.begin(),number1.end());if(cases0)cout\n;coutnumber1\n;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string number1,number2;while(cinnumber1number2)add(number1,number2);return0;}总结本题通过模拟Fibinary\texttt{Fibinary}Fibinary数的加法规则利用斐波那契数列的递推关系处理进位。关键在于将相邻111合并为更高位的111以及处理两个相同位相加时的分解规则。代码中的adjust\texttt{adjust}adjust和加法循环共同保证了结果的合法性。由于输入长度不超过100100100模拟算法高效且易于实现。该题是Fibinary\texttt{Fibinary}Fibinary进制运算的典型练习加深了对斐波那契数列性质的理解。