2013腾讯马拉松初赛 ACM 吉哥系列故事——最终数

[c]代码库

/*

2013腾讯马拉松初赛第3场

1004吉哥系列故事——最终数
 
Time Limit: 0.2 Seconds   Memory Limit: 65536K
 
在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

*/


/*
解题报告：
基本思想，由于题目中很多和斐波那切有关的东西，我们要抓住斐波那切数列的增长速度是非常快这个特点来解决这个问题。

首先看到最小的最终数是13，那么对于10^11这个数据来说的话，13是一个解，解的上限是不超过(10^11-13)+10^11

算他是2*10^11好了。
那么我们只要统计一下这个区间内有哪些最终数就行了。
其实这样的最终数并不多。
我们枚举到第54个斐波那切数字的时候已经是超过10^12，就算1到2*10^11这些数字都是题目中说的F数好了，也就是54个。

我有一个初步的想法，就是把小于等于2*2^11的斐波那切数字找出来。然后对于每一个最终数，我们二分一个答案X来计算一下
小于等于X的数字里面有多少是F数。
如果刚刚好是给定的斐波那切个数的话，这个数字就是那个斐波那切数对应的最终数了。

这对于统计这一块我们还是采用数位DP来做。

由于直接计算包含斐波那切数字的个数不好计算，我们可以反过来计算，计算一下不包含斐波那切数字的那些数。然后总数目减去就行了。

我们可以把斐波那切数看成是字符串，做成AC自动机，然后通过AC自动机来数位DP。

dp[i][j]代表长度为i，在自动机中的状态为j的情况

dp[i][j]=sum{dp[i-1][k]} for each node[j].next[bit]==k

先写个思路，具体的实现明天再写吧。
看了best solution里面的人代码好短，不知道他们是怎么做的。

我这样的写法至少得3K吧。

来自：http://hi.baidu.com/chenwenwen0210/item/65669bc0a55e48f9ee183bbc
*/

#include<stdio.h>
#include<math.h>
#include<string.h>
typedef __int64 lld;
const int MAX = 1005;
const int MAXSON = 10;

struct {
    int id, next[MAXSON], fail;
} node[10000];

int n, tot;


int q[1000000];
void clr() {
    int i;
    tot++;
    for(i = 0; i < MAXSON; i++)
        node[tot].next[i] = 0;
    node[tot].id = node[tot].fail = 0;
}
void ins(lld n) {
    lld tmp, bit[55];
    int i = 0;
    while(n) {
        bit[i++] = n % 10;
        n /= 10;
    }

    int h = 0;
    for(i--; i >= 0; i--) {
        tmp = bit[i];
        if(node[h].next[tmp] == 0) {
            clr();
            node[h].next[tmp] = tot;
        }
        h = node[h].next[tmp];
    }
    node[h].id++;
}
void get_fail() {
    int h = 0, i;
    int f = -1, r = 0;
    int tmp, fail, k;
    q[0] = 0;
    while(f != r) {
        tmp = q[++f];
        if(node[node[tmp].fail].id > 0) //自动机添加一个往前走的东西。错在这里啊，好久没有用AC自动机了
            node[tmp].id = 1;
        for(i = 0; i < MAXSON; i++) {
            if(node[tmp].next[i] == 0) {
                fail = node[tmp].fail;
                node[tmp].next[i] = node[fail].next[i];
                continue;
            }
            k = node[tmp].next[i];
            fail = node[tmp].fail;
            if(node[fail].next[i] != k)
                node[k].fail = node[fail].next[i];
            else
                node[k].fail = 0;
            q[++r] = k;
        }
    }
}
const double EPS = 1.0e-8;
int dblcmp(double x) {
    if(fabs(x) < EPS)return 0;
    return x < 0 ? -1 : 1;
}

const lld INF = (lld)(1000000000) * (lld)(1000);
lld dp[15][1000] = {0};
lld ans[55], c;
lld f[55] = {1, 2};
void init() {
    int i, j, k;
    for(i = 0; i <= tot; i++) {
        if(node[i].id == 0) {
            dp[0][i]++;
        }
    }
    int h = 0;
    for(i = 1; i < 15; i++) {
        for(j = 0; j <= tot; j++) {
            if(node[j].id > 0)continue;
            for(k = 0; k < 10; k++) {
                h = node[j].next[k];
                if(node[h].id > 0)continue;
                dp[i][j] += dp[i - 1][h];
            }
        }
    }
    //    freopen("C:\\a.txt","w",stdout);
    //for(i=1;i<2;i++)for(j=0;j<=tot;j++)    {        printf("dp[%d][%d]=%I64d\n",i,j,dp[i][j]);    }

}
lld calc(lld n) {
    if(n == 0)return 0;
    int h, i = 0, j;
    lld m = n - 1;
    lld bit[55];
    while(n) {
        bit[i++] = n % 10;
        n /= 10;
    }
    int len = i;
    lld ret = 0;
    for(i = 1; i < len; i++) {
        for(j = 1; j < 10; j++) {
            h = node[0].next[j];
            if(node[h].id == 0) {
                ret += dp[i - 1][h];
            }
        }
    }
    h = 0;
    for(i = len; i > 0; i--) {
        j = 0;
        if(i == len)j++;
        for(; j < bit[i - 1]; j++) {
            int th = node[h].next[j];
            if(node[th].id > 0)continue;
            ret += dp[i - 1][th];
        }

        h = node[h].next[bit[i - 1]];
        if(node[h].id > 0)break;
    }
    return m - ret;
}
lld bin(lld aim) {
    lld low = 0, high = INF;
    lld mid, ret = -1;
    while(low <= high) {
        mid = (low + high) >> 1;
        if(calc(mid) >= aim) {
            ret = mid - 1;
            high = mid - 1;
        } else low = mid + 1;
    }
    return ret;
}
int main() {
    lld n;
    int i;
    tot = -1;
    clr();
    int sum = 0;
    for(i = 2; i < 55; i++) {
        f[i] = f[i - 1] + f[i - 2];
        if(f[i] >= 10) {
            ins(f[i]);
            sum += log10(f[i] * 1.0) + 1;
        } else if(f[i] >= INF)break;
    }
    //    printf("sum=%d\n",sum);
    //    printf("tot=%d\n",tot);
    get_fail();
    init();
    for(i = 2; i < 55; i++)f[i] = f[i - 1] + f[i - 2];
    c = 0;
    for(i = 0; i < 55; i++) {
        //    printf("f[%d]=%I64d\n",i,f[i]);
        ans[c] = bin(f[i]);
        if(ans[c] == -1)break;
        c++;
    }
    //printf("c=%I64d\n",c);
    //for(i=0;i<c;i++)printf("ans[%d]=%I64d\n",i,ans[i]);
    //    return 0;
    while(scanf("%I64d", &n) != EOF && n > 0) {
        lld min = n - 13;
        if(min < 0)min = -min;
        for(i = 0; i < c; i++) {
            lld tmp = n - ans[i];
            if(tmp < 0)tmp = -tmp;
            if(tmp < min)min = tmp;
        }
        printf("%I64d\n", min);
    }
    return 0;
}