P5940 [POI1997]跳

· · 题解

[POI1997] Jump

上古好题，从一个看似毫无关联的问题转化到斐波那契数列分解。

观察到这题没有 SPJ，所以第一个令人好奇的点就是是否一定存在唯一解。

同时直觉上这种构造题需要手玩一些小情况，不妨从某个单个位置有 2 开始：

number : 1 2 3 4 5
step 0 : 0 0 2 0 0
step 1 : 1 1 1 0 0
step 2 : 1 0 0 1 0

再看看对于单个 3：

number : 1 2 3 4 5 6 7
step 0 : 0 0 0 3 0 0 0
step 1 : 0 1 1 2 0 0 0
step 2 : 0 1 0 1 1 0 0
step 3 : 0 1 0 0 0 1 0

这样就得到了一个看起来不太靠谱的调整法：

当然，调整法的操作次数上限是多少，如何简洁清晰地实现，怎么证明解存在且唯一，等等。都存在一定问题。

此时，不妨换个角度，从操作过程中的不变量来观察。

第一种操作是 p 的减少换来 p-1,p-2 的增加，而第二中操作是逆运算。

我们能否给每个位置赋上合适的权值，以得到序列总权值始终不变的结论呢。

答案已经呼之欲出了，当然可以，令 f_p=f_{p-1}+f_{p-2}，这是经典的斐波那契数列，完全没有问题。

同时，算出初始序列的权值后，题目的目标也变成了：选出若干不相邻的斐波那契数，使它们的和等于初始序列的权值。

这是经典的斐波那契数列分解问题，可以证明有且仅有唯一解，并且解的构造相对容易，只要从大到小枚举斐波那契数，如果 f_i\leq 当前权值和就直接选择。

简单证明：

这都是基于，对于最大的 i 满足 f_i\leq v，f_i 一定存在于 v 的分解当中，这一事实。

而这又能够通过 f_1+f_3+\cdots +f_n 或 f_2+f_4+\cdots +f_n 均严格 <f_i 这一简单事实来证明。

并且显然通过 单个斐波那契数的拆解（对应于操作 1）和 相邻斐波那契数的合并（对应于操作 2）能够得到任意目标序列，只要全局和不变。

所以所有问题全部迎刃而解，我们已经得到了一个足够理性，足够正确，有充分证明的完备算法。

最后一个问题，对于序列赋值，f_0 应该从何开始呢？

因为存在负下标，所以在证明的时候选定 -\infty 已经足够，但是在代码实现的时候显然不能这么模糊。

实际上，上面那个不靠谱的调整法或许在这里有了些用处，可以大致观察出平移最左的棋子位置：

所以从 -(2\log _3 v+c) 开始或许就足够，在考场上的一个 trick 是可以二分这个偏移量。具体的，首先偏移量尽量调大得到准确解，之后尝试缩小并对拍，能过拍就继续调小 QwQ

于是这题就愉快的做完了/se。具体实现上需要实现一个高精度，这里偏移量选的是 80。

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

const int N = 1e4 + 10;
const ll B = 10000000000ll;
const int D = 80;
int n, a[N], b[N];

struct bigint {
    ll a[500]; int len;
    bigint(int x = 0) {memset(a, 0, sizeof(a)); len = 0; while(x) a[++ len] = x % B, x /= B;}
    bigint operator + (const bigint &p) const {
        bigint q = * this;
        q.len = max(len, p.len);
        rep(i, 1, q.len) {
            q.a[i] += p.a[i];
            q.a[i + 1] += q.a[i] / B, q.a[i] %= B;
        }
        while(q.a[q.len + 1]) q.len ++, q.a[q.len + 1] += q.a[q.len] / B, q.a[q.len] %= B;
        return q;
    }
    bigint operator - (const bigint &p) const {
        bigint q = * this;
        rep(i, 1, q.len) {
            q.a[i] -= p.a[i];
            while(q.a[i] < 0) q.a[i] += B, q.a[i + 1] --;
        }
        while(q.len && ! q.a[q.len]) q.len --;
        return q;
    }
    bigint operator * (const ll &p) const {
        bigint q = * this;
        per(i, q.len, 1) {
            ll cur = q.a[i] * p;
            q.a[i + 1] += cur / B, q.a[i] = cur % B;
        }
        rep(i, 1, q.len) {
            q.a[i + 1] += q.a[i] / B, q.a[i] %= B;
            if(q.a[i + 1] && i == q.len) q.len ++;
        }
        return q;
    }
    bool operator < (const bigint &p) const {
        if(len ^ p.len) return len < p.len;
        per(i, len, 1) if(a[i] ^ p.a[i]) return a[i] < p.a[i];
        return false;
    }
} F1, F2, A;

ll sum[N + 100];

int main() {
    int n = read();
    rep(i, 1, n) a[i] = read() + D, sum[a[i]] += read();
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - (a + 1);

    F1 = bigint(1);
    F2 = bigint(1); int c = 1;
    rep(i, 1, a[n]) {
        if(a[c] == i) A = A + (F2 * sum[a[c]]), c ++;
        swap(F1, F2), F2 = F1 + F2;
    }
    c = a[n] + 1;
    while(F2 < A) swap(F1, F2), F2 = F1 + F2, c ++;

    vector<int> ans;
    while(A.len) {
        if(! (A < F2)) A = A - F2, ans.push_back(c);
        c --, swap(F1, F2), F1 = F1 - F2;
    }
    reverse(ans.begin(), ans.end());
    for(int o : ans) printf("%d ", o - D);
    putchar('\n');
    return 0;
}