【jzoj3769】【NOI2015模拟8.14】【A+B】

题目大意

对于每个数字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大。

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

解题思路

暴力，从后往前除去2，从后往前除去连续的1，再随意修正到合法即可。

code

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define LF double #define LL long long #define ULL unsigned int #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define fr(i,j) for(int i=begin[j];i;i=next[i]) using namespace std; int const ml=5*1e6,inf=1e9+7; int n,m,a[ml]; int max(int x,int y){return (x>y)?x:y;} int min(int x,int y){return (x<y)?x:y;} int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&n); fo(i,1,n){ char x=getchar(); while((x<'0')||(x>'9'))x=getchar(); a[i]+=x-'0'; } scanf("%d",&m); fo(i,1,m){ char x=getchar(); while((x<'0')||(x>'9'))x=getchar(); a[i]+=x-'0'; } int mx=max(n,m),tag=1; fo(j,1,6){ if(j&1){ for(int i=1;i<=mx;i++){ if(a[i]>=2){ if(i>2){ a[i+1]+=a[i]>>1; if(i+1>mx)mx++; a[i-2]+=a[i]>>1; a[i]=a[i]&1; }else if(i==2){ a[i+1]+=a[i]>>1; if(i+1>mx)mx++; a[i-1]+=a[i]>>1; a[i]=a[i]&1; }else{ a[i+1]+=a[i]>>1; if(i+1>mx)mx++; a[i]=a[i]&1; } tag=1; } } }else{ for(int i=1;i<=mx;i++){ if((i>1)&&a[i]&&a[i-1]){ int tmp=min(a[i],a[i-1]); a[i+1]+=tmp; a[i]-=tmp; a[i-1]-=tmp; if(i+1>mx)mx++; tag=1; } } } } tag=1; while(tag){ tag=0; for(int i=1;i<=mx;i++){ if(a[i]>=2){ if(i>2){ a[i+1]+=a[i]>>1; if(i+1>mx)mx++; a[i-2]+=a[i]>>1; a[i]=a[i]&1; }else if(i==2){ a[i+1]+=a[i]>>1; if(i+1>mx)mx++; a[i-1]+=a[i]>>1; a[i]=a[i]&1; }else{ a[i+1]+=a[i]>>1; if(i+1>mx)mx++; a[i]=a[i]&1; } tag=1; } if((i>1)&&a[i]&&a[i-1]){ int tmp=min(a[i],a[i-1]); a[i+1]+=tmp; a[i]-=tmp; a[i-1]-=tmp; if(i+1>mx)mx++; tag=1; } } } printf("%d ",mx); fo(i,1,mx){ putchar(a[i]+'0'); putchar(' '); } return 0; }