A+B【NOI2015模拟8.14】

Description

对于每个数字x，我们总可以把它表示成一些斐波拉切数字之和，比如8 = 5 + 3， 而22 = 21 + 1，因此我们可以写成 x = a1 * Fib1 + a2 * Fib2 + a3 * Fib3 + … + an * Fibn, 其中，Fib1 = 1, Fib2 = 2…. Fib[i] = Fib[i – 1] + Fib[I - 2], 且a[n] > 0.那么我们称ai为x的一种斐波拉切表示，由于表示方法有很多种，我们要求最大化a[1…n]，即，如果b[1…n]和a[1…m]都可以表示x，若m > n 则a更大，若 m = n， 则从高位到低位比，第一个不同处i，若ai > bi 则a比b大。

你的任务很简单，给你两个用斐波拉切数最大化表示的两个数字，输出他们相加后用斐波那契最大化表示的数字。

Input

两行，分别表示两个数字

每一行开头一个n，表示长度

然后紧接着n个数字，为从低位到高位。

Output

同输入格式。一行。

Sample Input

4 0 1 0 1

5 0 1 0 0 1

Sample Output

6 1 0 1 0 0 1

Data Constraint

对于30%的数据 长度 <= 1000

对于100%的数据 长度 <= 1000000

---

思路

首先如果是最大表示法的话，那么每个数它的最大表示中： 1.没有连续的1，reason：Frb[i]=Frb[i-1]+Frb[i-2]; 2.没有比1大的数，reason:Frb[i]*2=Frb[i-2]+Frb[i+1]; 把两个数加起来后，暴力处理即可。

(╯‵□′)╯︵┻━┻比赛时没看到最前面两个是不符合斐波拉切规律的，忘特判了。QwQ

---

代码

#include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #define fo(i,a,b) for(int i=a;i<=b;i++) #define ll long long using namespace std; const int maxn=1000005; int a[maxn],n,b[maxn],ans[maxn]; int main() { // freopen("T.in","r",stdin); scanf("%d",&a[0]); fo(i,1,a[0]) scanf("%d",&a[i]); scanf("%d",&b[0]); fo(i,1,b[0]) scanf("%d",&b[i]); ans[0]=max(a[0],b[0]); fo(i,1,ans[0]) ans[i]=a[i]+b[i]; bool bz=true; while (bz){ bz=false; if (ans[1]>=3) ans[3]+=ans[1]/3,ans[1]%=3,bz=true; if (ans[1]>=2) ans[2]+=ans[1]/2,ans[1]%=2,bz=true; if (ans[2]>=2) { int k=ans[2]/2; ans[2]%=2; ans[1]+=k,ans[3]+=k; bz=true; } if (ans[1]>0&&ans[2]>0){ int k=min(ans[1],ans[2]); ans[3]+=k; ans[1]-=k; ans[2]-=k; bz=true; } fo(i,3,ans[0]) { if (ans[i]>0&&ans[i-1]>0){ int k=min(ans[i],ans[i-1]); ans[i+1]+=k; ans[i]-=k,ans[i-1]-=k; if (i+1>ans[0]) ans[0]=i+1; bz=true; } if (ans[i]>=2){ int k=ans[i]/2; ans[i]%=2; ans[i+1]+=k,ans[i-2]+=k; if (i+1>ans[0]) ans[0]=i+1; bz=true; } } } printf("%d ",ans[0]); fo(i,1,ans[0]) printf("%d ",ans[i]); }