吉哥系列故事――最终数

Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 304 Accepted Submission(s): 102

Problem Description 　　在2012年腾讯编程马拉松比赛中，吉哥解决了一道关于斐波那契的题目，这让他非常高兴，也更加燃起了它对数学特别是斐波那契数的热爱。现在，它又在思考一个关于斐波那契的问题：
　　假如我们现在已知斐波那契数是1，1，2，3，5，8，13，21，34，55，89...
　　由于吉哥特别喜欢斐波那契数，它希望每个数中都包含斐波那契数，比如说130，其中包含了13，或者5534包含了55和34，只要数位中含有至少一个斐波那契数就是吉哥想要的数。但是这种数实在太多了，于是它去掉那些仅仅含有小于10的斐波那契数的数，比如说1，仅仅含有1，所以被去掉；或者335只含有3和5，都是小于10的斐波那契数，所以也去掉；但是131是留下的，因为它含有13，我们暂且称这类数为F数,不难得到前几个F数是 13 ，21， 34， 55， 89，113，121，130，131...
　　霸气的吉哥觉得这样还不够，它想将斐波那契进行到底――在前面F数的基础上，吉哥要得到那些是第斐波那契数个的F数！就是说，我们假设F数从1开始标号，那么13是第1个F数，吉哥想要那些在F数中的排列或者说下标也要是斐波那契数的数，吉哥称之为最终数，如13，21，34，89，130...
　　现在给你一个数n，吉哥想知道离n最近的最终数与n的差的绝对值是多少。

Input 　　输入包含多组测试数据。
　　每组测试数据包含一个整数n ( 1 <= n <= 10^11)；
　　若n = -1，表示输入结束。

Output 　　对于每个n，请输出离n最近的最终数与n的差的绝对值。
Sample Input

1
100
-1

Sample Output

12
11

Source 2013腾讯编程马拉松初赛第三场（3月23日）

把斐波那契数列插入ac自动机，然后数位dp进行二分查找，

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/8/15 16:27:37
File Name :3.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; struct Trie{ ll next[1010][10],end[1010],fail[1010]; ll root,L; void init(){ L=0; root=newnode(); } ll newnode(){ for(ll i=0;i<10;i++) next[L][i]=-1; end[L++]=0; return L-1; } void insert(ll x){ ll a[15],len=0; while(x){ a[len++]=x%10; x/=10; } //for(ll i=len-1;i>=0;i--)cout<
                
                 =0;i--){ if(next[now][a[i]]==-1) next[now][a[i]]=newnode(); now=next[now][a[i]]; } end[now]=1; } void build(){ queue
                 
                   Q; fail[root]=root; for(ll i=0;i<10;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ ll now=Q.front(); Q.pop(); end[now]|=end[fail[now]]; for(ll i=0;i<10;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } }ac; ll fib[60],dp[15][1010],seq[60],POW[20]; ll suf[15],num[15]; ll dfs(ll pos,ll st,bool flag){ if(pos==0)return 0; if(flag&&dp[pos][st]!=-1)return dp[pos][st]; ll u=flag?9:num[pos]; ll ans=0; for(ll i=0;i<=u;i++){ ll state=ac.next[st][i]; if(ac.end[state]){ if(flag||i
                  
                   10)ac.insert(fib[i]); POW[0]=1; for(ll i=1;i<=15;i++)POW[i]=10*POW[i-1]; ac.build(); for(ll i=2;i<=56;i++){ ll l=13,r=POW[12]; while(l
                   
                    >n&&n!=-1){ ll ans=1e15; for(ll i=2;i<=56;i++){ ll tt=n-seq[i]; if(tt<0)tt=-tt; ans=min(ans,tt); } cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU4509-湫湫系列故事――减肥记I..	下一篇：Tree Operations 打印出有向图中..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: