P3539 [POI2012]ROZ-Fibonacci Representation
题意:给一个数,问最少可以用几个斐波那契数加加减减凑出来
多组数据10 数据范围1e17
第一次瞬间yy出做法,直接上去艹了。
写完了交了对了开始想证明
策略:对于一个数\(k\),有两种可能
- 存在一个\(f[i]==k\) 直接返回即可
- 存在\(f[i]<k<f[i+1]\),这时候使用\(|k-f[i]|\)与\(|f[i+1]-k|\)的较小者所代表的\(f[i]\),然后分治处理
感性证明:这样规模减小的快(其实是不会证orz)
Code:
#include <cstdio>
#define ll long long
ll f[87],k,cnt;
void init()
{
f[1]=f[2]=1;
for(int i=3;i<=86;i++)
f[i]=f[i-1]+f[i-2];
}
void divide(ll d)
{
cnt++;
for(int i=1;i<86;i++)
{
if(d==f[i]) return;
if(d>f[i]&&d<f[i+1])
{
if(d-f[i]>f[i+1]-d)
divide(f[i+1]-d);
else
divide(d-f[i]);
break;
}
}
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&k);
cnt=0;
divide(k);
printf("%d\n",cnt);
}
return 0;
}
2018.7.15