zoj 3702 – Gibonacci number

问题不难,但是处理起来挺有趣的。

Gibonacci 数递推式与斐波那契数一样,但不同的是 G[0] = 1,G[1] 是一个需要确定的正整数。

然后给出一个 G[i] (G[i] < 1000000, i < 20),并给出一个 j 要求对应的 (j < 20) G[j]。

很明显,给出一个 i, G[i] 的值不一定是合法的,而且合法的数据会在 20*1000000 这个空间之内。

因此我们只需要预处理出所有 G[1] = 1..1000000 时所有的 G[1..20],然后每次给出 i 和 G[i],然后在里面查找即可。

中间用到了一些空间压缩的方法(很久没玩过 C++ 指针了),然后查找的方法用的是二分,也比较顺利的 Accept 了。

关键在于,要求输出的 G[j] 的值没有说过要 < 1000000,为此 WA 了一次。

另外在空间压缩不充分的情况下也 MLE 了一次。

// 3566763 2014-03-24 01:42:18 Accepted 3702 C++ 20 31420 呆滞的慢板

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int SZ[1000000] = {};
int buf[5000000] = {};
int* cur = buf;
int* L[1000000];

int main() {

    for(int t = 1; t < 1000000; ++t) {
        int len = 0;
        L[t] = cur;
        cur[len++] = 1;
        cur[len++] = t;
        for(int i = 2; i <= 20; ++i) {
            int p = cur[i-1] + cur[i-2];
            if(p >= 1000000) break;
            cur[len++] = p;
        }
        SZ[t] = len;
        cur += len;
    }

    int T;

    for(scanf("%d", &T); T--;) {

        int i, g, j;
        scanf("%d%d%d", &i, &g, &j);

        int l = 0, r = 1000000, m;

        while(l + 1 < r) {
            m = l + r >> 1;
            if(SZ[m] <= i || L[m][i] > g) r = m;
            else l = m;
        }

        if(SZ[l] > i && L[l][i] == g) {
            long long p[21] = {1, l};
            for(int jj = 2; jj <= j; ++jj) {
                p[jj] = p[jj-1] + p[jj-2];
            }
            printf("%lld\n", p[j]);
        }
        else puts("-1");

    }

}

【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2014/03/zoj3702.html【zoj 3702 – Gibonacci number】

发表评论

电子邮件地址不会被公开。 必填项已用*标注