BZOJ2796: [Poi2012]Fibonacci Representation

2019-11-06 06:43:36

字体：大中小

来源：转载

供稿：网友

记忆化搜索所以其实就是乱搜吗…. 1017 $10^{17}$ 在fib数列里好像就70~80左右的地方，所以数据的数量不多，寻找x的解可以二分找到x大概在fib的哪个位置，然后找x和左右项的差的绝对值y

#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void down(int &x,int y){if(x>y)x=y;}const int maxn = 88;map<ll,int>h;ll n;ll f[maxn];int find_(ll x){ int l=2,r=85; while(l<=r) { int mid=(l+r)>>1; if(x<f[mid]) r=mid-1; else l=mid+1; } return l-1;}ll solve(ll x){ int k=find_(x); int ans=233; ll cl=abs(f[k]-x); if(h.count(cl)>0) ans=h[cl]; else ans=solve(cl); cl=abs(f[k+1]-x); if(h.count(cl)>0) down(ans,h[cl]); else { int l=solve(cl);if(ans>l)ans=l; } h[x]=ans+1; return ans+1;}int main(){ h[0]=0; f[1]=1; for(int i=2;i<maxn;i++) f[i]=f[i-1]+f[i-2],h[f[i]]=1; int t; scanf("%d",&t); while(t--) { scanf("%lld",&n); if(h.count(n)>0) PRintf("%d/n",h[n]); else printf("%d/n",solve(n)); } return 0;}

上一篇：cookie实现自动登陆

下一篇：redis的各种用法