[洛谷 3424][POI2005]Fibonacci Sums

题目链接

https://www.luogu.org/problem/P3424

题解

一道小清新数论题。

我们把两个数加起来,会出现这样几种不合法的情况:

  1. 连续两个位上的值都是 1;
  2. 一个数位上的值为 2。

对于第一种情况,我们直接利用 \(f_i=f_{i-1}+f_{i-2}\) 处理即可。

对于第二种情况:我们发现 \(2f_i=f_i+f_i=f_i+f_{i-1}+f_{i-2}=f_{i+1}+f_{i-2}\),因此可以根据这条性质解决第二种情况。(特别地,\(2f_2=f_1+f_3\),\(2f_1=f_2\))

我们从高位到低位按顺序处理这两种不合法的情况即可。

注意我们处理处理当前位的时候,可能导致之前处理过的较高位再次出现不合法情况,因此我们每次处理完一位之后都要再这一位前面的两位产生的不合法情况进行处理。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[1000005],b[1000005],ans[1000005];
void dec(int x)
{
 ans[x]-=2;
 if(x==1)ans[2]++;
 else if(x==2)ans[1]++,ans[3]++;
 else ans[x-2]++,ans[x+1]++;
}
void add(int x)
{
 while(ans[x]&&ans[x+1])
 {
  ans[x]--,ans[x+1]--,ans[x+2]++;
  x+=2;
 }
}
int main()
{
 int x,y;
 scanf("%d",&x);
 for(int i=1;i<=x;i++)
  scanf("%d",&a[i]);
 scanf("%d",&y);
 for(int i=1;i<=y;i++)
  scanf("%d",&b[i]);
 int len=max(x,y);
 for(int i=1;i<=len;i++)
  ans[i]=a[i]+b[i];
 for(int i=len;i;i--)
 {
  if(ans[i]>1)dec(i);
  add(i);
  if(ans[i+1]>1)dec(i+1);
  add(i+1);
  if(ans[i+2]>1)dec(i+2);
  add(i+2);
 }
 if(ans[len+1])len++;
 if(ans[len+2])len+=2;
 printf("%d ",len);
 for(int i=1;i<=len;i++)
  printf("%d ",ans[i]);
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据