首页 > ACM题库 > HDU-杭电 > HDU 4518-吉哥系列故事――最终数-动态规划-[解题报告]HOJ
2015
07-17

HDU 4518-吉哥系列故事――最终数-动态规划-[解题报告]HOJ

吉哥系列故事――最终数

问题描述 :

  在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的差的绝对值是多少。

输入:

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

输出:

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

样例输入:

1
100
-1

样例输出:

12
11

整理一下思路,明天再写。。。

 这道题,其实就是求包含大于10的斐波那切数字的第K(K是斐波那契数)个数。注意到斐波那契数的爆炸性增长,所以在范围 内的符合要求的F数并不多吧。比如求第K个F数,那么,前K个F数都是这样的数,组成它们的数字中有斐波那契数。这就是字符串匹配吧。把这些数转化成字符串匹配,也就是很经典的数位DP,求范围内含有这些数字的数有多少个。

但是,所要含的数有很多个,怎么样匹配呢?转化成字符串,构成AC自动机来做。但是,说实话,求含有数字的个数确实不好弄,没关系,把它转化成不含有就容易了。于是,就成了AC自动机+数位DP了。但是,我们要求的是第K个,那么,因为个数是单调增的,求出刚好第K个可以使用二分查找来办到。

使用AC自动机来做数位DP,首先要构建trie图,然后明白哪些状态是可转移或不可转移的,然后在trie图上进行DP就可以了。

dp[i][j],即是当前是前第i位数位,并处在自动机的j状态上。

#include <iostream>
#include <cstdio>
#define LL __int64
using namespace std;

const LL inf=10000000000000ll;
const int root=0;
LL f[60],ans[60];

int trie[550][10],bit[30],fail[550],que[550],head,tail;
int tot;
int nxt[550][10];
LL dp[15][550];
bool tag[550];

void insert(LL now){
    int len=0;
    while(now){
        bit[++len]=now%10;
        now/=10;
    }
    int p=root,i=len;
    while(i--){
        if(trie[p][bit[i+1]]==-1){
            trie[p][bit[i+1]]=++tot;
        }
        p=trie[p][bit[i+1]];
    }
    tag[p]=true;
}

void build_ac(){
    head=tail=0;
    que[tail++]=root;
    while(head!=tail){
        int tmp=que[head++];
        int p=-1;
        for(int i=0;i<10;i++){
            if(trie[tmp][i]!=-1){
                if(tmp==root) fail[trie[tmp][i]]=root;
                else{
                    p=fail[tmp];
                    while(p!=-1){
                        if(trie[p][i]!=-1){
                            fail[trie[tmp][i]]=trie[p][i];
                            break;
                        }
                        p=fail[p];
                    }
                    if(p==-1) fail[trie[tmp][i]]=root;
                }
                if(tag[fail[trie[tmp][i]]]) tag[trie[tmp][i]]=tag[fail[trie[tmp][i]]];
                que[tail++]=trie[tmp][i];
            }
            else{
                if(tmp==root) trie[tmp][i]=root;
                else{
                    p=fail[tmp];
                    while(p!=-1){
                        if(trie[p][i]!=-1){
                            trie[tmp][i]=trie[p][i];
                            break;
                        }
                        p=fail[p];
                    }
                    if(p==-1) trie[tmp][i]=root;
                }
            }
        }
    }
}

LL dfs(int len,int j,bool flag){
    if(len==0) return 1ll;
    if(!flag&&dp[len][j]!=-1) return dp[len][j];
    LL ans=0;
    int up=flag?bit[len]:9;
    for(int i=0;i<=up;i++){
        if(tag[nxt[j][i]]||nxt[j][i]==-1) continue;
        ans+=dfs(len-1,nxt[j][i],i==up&&flag);
    }
    if(!flag) dp[len][j]=ans;
    return ans;
}

LL cal(LL m){
    LL tm=m+1ll;
    int len=0;
    while(m){
        bit[++len]=m%10;
        m/=10;
    }
    return tm-dfs(len,0,true);
//    return 0;
}

LL bin(LL num){
//    cout<<cal(13)<<endl;
//    system("pause");
    LL l=0,r=inf,ret=-1,tmp;
    while(l<=r){
        LL m=(l+r)>>1;
        if((tmp=cal(m))>=num){
            r=m-1;
            ret=m;
//            cout<<m<<endl;
        }
        else l=m+1;
    }
    return ret;
}

int cal_next(int p,int j){
    if(tag[p]) return -1;
    if(tag[trie[p][j]]) return -1;
    return trie[p][j];
}

void Init(){
    tot=0;
    memset(trie,-1,sizeof(trie));
    memset(tag,false,sizeof(tag));
    memset(fail,-1,sizeof(fail));
    f[1]=1ll; f[2]=1ll;
    for(int i=3;i<=55;i++){
        f[i]=f[i-1]+f[i-2];
        if(f[i]>10){
            insert(f[i]);
        }
    }
    build_ac();
    for(int i=0;i<=tot;i++){
        for(int j=0;j<10;j++)
        nxt[i][j]=cal_next(i,j);
    }
    memset(dp,-1,sizeof(dp));
    int c=0;
    for(int i=2;i<=55;i++){
        ans[c]=bin(f[i]);
//        system("pause");
        if(ans[c]==-1) break;
        c++;
//        printf("%I64d  %d\n",ans[c-1],c);
    }
}

int main(){
    Init();
    LL n;
//    cout<<"YES"<<endl;
    while(scanf("%I64d",&n)!=EOF&&n!=-1){
        LL ret=inf;
        for(int i=0;i<54;i++){
            LL tmp=n-ans[i];
        //    cout<<tmp<<endl;
            if(tmp<0) tmp=-tmp;
            if(ret>tmp) ret=tmp;
        }
        printf("%I64d\n",ret);
    }
    return 0;
}

 

参考:http://www.cnblogs.com/jie-dcai/p/4338630.html