HDU 4518

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

这道题，其实就是求包含大于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=;

LL f[],ans[];

int trie[][],bit[],fail[],que[],head,tail;

int tot;

int nxt[][];

LL dp[][];

bool tag[];

void insert(LL now){

    int len=;

    while(now){

        bit[++len]=now%;

        now/=;

    }

    int p=root,i=len;

    while(i--){

        if(trie[p][bit[i+]]==-){

            trie[p][bit[i+]]=++tot;

        }

        p=trie[p][bit[i+]];

    }

    tag[p]=true;

}

void build_ac(){

    head=tail=;

    que[tail++]=root;

    while(head!=tail){

        int tmp=que[head++];

        int p=-;

        for(int i=;i<;i++){

            if(trie[tmp][i]!=-){

                if(tmp==root) fail[trie[tmp][i]]=root;

                else{

                    p=fail[tmp];

                    while(p!=-){

                        if(trie[p][i]!=-){

                            fail[trie[tmp][i]]=trie[p][i];

                            break;

                        }

                        p=fail[p];

                    }

                    if(p==-) 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!=-){

                        if(trie[p][i]!=-){

                            trie[tmp][i]=trie[p][i];

                            break;

                        }

                        p=fail[p];

                    }

                    if(p==-) trie[tmp][i]=root;

                }

            }

        }

    }

}

LL dfs(int len,int j,bool flag){

    if(len==) return 1ll;

    if(!flag&&dp[len][j]!=-) return dp[len][j];

    LL ans=;

    int up=flag?bit[len]:;

    for(int i=;i<=up;i++){

        if(tag[nxt[j][i]]||nxt[j][i]==-) continue;

        ans+=dfs(len-,nxt[j][i],i==up&&flag);

    }

    if(!flag) dp[len][j]=ans;

    return ans;

}

LL cal(LL m){

    LL tm=m+1ll;

    int len=;

    while(m){

        bit[++len]=m%;

        m/=;

    }

    return tm-dfs(len,,true);

//    return 0;

}

LL bin(LL num){

//    cout<<cal(13)<<endl;

//    system("pause");

    LL l=,r=inf,ret=-,tmp;

    while(l<=r){

        LL m=(l+r)>>;

        if((tmp=cal(m))>=num){

            r=m-;

            ret=m;

//            cout<<m<<endl;

        }

        else l=m+;

    }

    return ret;

}

int cal_next(int p,int j){

    if(tag[p]) return -;

    if(tag[trie[p][j]]) return -;

    return trie[p][j];

}

void Init(){

    tot=;

    memset(trie,-,sizeof(trie));

    memset(tag,false,sizeof(tag));

    memset(fail,-,sizeof(fail));

    f[]=1ll; f[]=1ll;

    for(int i=;i<=;i++){

        f[i]=f[i-]+f[i-];

        if(f[i]>){

            insert(f[i]);

        }

    }

    build_ac();

    for(int i=;i<=tot;i++){

        for(int j=;j<;j++)

        nxt[i][j]=cal_next(i,j);

    }

    memset(dp,-,sizeof(dp));

    int c=;

    for(int i=;i<=;i++){

        ans[c]=bin(f[i]);

//        system("pause");

        if(ans[c]==-) break;

        c++;

//        printf("%I64d  %d\n",ans[c-1],c);

    }

}

int main(){

    Init();

    LL n;

//    cout<<"YES"<<endl;

    while(scanf("%I64d",&n)!=EOF&&n!=-){

        LL ret=inf;

        for(int i=;i<;i++){

            LL tmp=n-ans[i];

        //    cout<<tmp<<endl;

            if(tmp<) tmp=-tmp;

            if(ret>tmp) ret=tmp;

        }

        printf("%I64d\n",ret);

    }

    return ;

}

巴特西

HDU 4518

最新文章

热门文章