自动搬运

查看原文

来自洛谷，原作者为

	LPF 看不懂黑白却听得到钟摆，去新世界冒险和内心作伴

搬运于2025-08-24 22:15:49，当前版本为作者最后更新于2023-01-10 00:28:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[POI1997] Jump

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

• 初始有一个长度无限的空序列，所有整数（无论正负）都可以作为下标。
• 给定 $n$ 个二元组 $(p_i,x_i)$ 表示在数列中 $p_i$ 放上 $x_i$ 个棋子，即 $a_{p_i}\gets a_{p_i}+x_i$。
• 可以无限制的进行两种操作：
  • 选定 $p$，满足 $a_p>0$，操作后 $a_p$ 减 $1$，$a_{p-1},a_{p-2}$ 均加 $1$。
  • 选定 $p$，满足 $a_p,a_{p+1}>0$，操作后 $a_p,a_{p+1}$ 减 $1$，$a_{p+2}$ 加 $1$。
• 求输出一个目标局面，使得 $\forall i,a_i+a_{i+1}\leq 1$。
• $n\leq 10^4,0\leq p_i\leq 10^4, 0\leq x_i\leq 10^8$，注意 $p_i$ 可以有重复。

观察到这题没有 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

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

• 对于连续 $>0$ 的两个位置，用基本操作二不断后移。

• 对于 $\geq 3$ 的位置，持续使用对单个 $3$ 的处理方法，直至全局都不存在 $\geq 3$。因为每次操作会使全局和 $-1$，所以必定会终止。

• 现在，所有有棋子的位置均不连续，且 $\leq 2$。那么对从右往左对每个 $2$ 使用对单个 $2$ 的处理方法。

  每次可能会新增 $2$，那么相当于最右侧的 $2$ 向左平移，传递到最左侧后总会停止。

  也可能会新增 $3$，此时仍然调用对 $3$ 的方法，同样因为全局和 $-1$ 到得出操作次数有限的结论。

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

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

第一种操作是 $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$ 已经足够，但是在代码实现的时候显然不能这么模糊。

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

• 对单个 $3$ 的处理，每次会使棋子向左平移两位，每次平移后权值和 $/3$，所以大致平移 $2\log_3 v$ 距离，其中 $v$ 是总棋子个数。
• 对单个 $2$ 的处理，同样是使棋子左移两格，但最终对最左侧的棋子的影响是 $O(1)$ 的。

所以从 $-(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;
}