P5940 [POI1997] 跳 题解

前言

挺有意思的题，记录一下。

正文

分析题目

简化一下题意，有一个无限长的的数组，从负无穷到正无穷，然后初始这个数组上一些点有一些数，现在可以使用两种操作让这个数组任意两个相邻的数的和不超过一，首选选择一个下标 $p$：

1. 让 $a_p$ 加一，$a_{p-1},a_{p-2}$ 减一。

2. 让 $a_p$ 减一，$a_{p-1},a_{p-2}$ 加一。

首先这两个操作是互逆的。然后这个操作会给人一种感觉，就是 $p-1,p-2$ 位置上的数各取一，和一个 $p$ 位置取一是等价的。所以可以花费 $p-1,p-2$ 位置各减去一作为代价，让 $p$ 位置加上一，另一个操作同理。

那就给每个位置钦定一个权值 $w_p$ 可以满足这样的条件，肯定有 $w_p=w_{p-1}+w_{p-2}$，即斐波那契数列。这样每次操作后数组的带权和不变，我们令这个值是 $s$，那么结束状态就是把 $s$ 拆分成不同且不相邻的一些斐波那契数之和，所以把问题转化为求一个数的斐波那契拆解（我也不知道这个叫什么）。

求解方法很简单，每次减去小于等于这个数的最大斐波那契数即可。为什么这样是对的呢，用归纳法证明，首先 $s$ 是一或者二可以直接拆解，那么设当前已知分解方法的最大的数是 $n$，现在来分解 $n+1$，找到的小于等于 $n+1$ 的最大斐波那契数是 $f$，那么 $n+1-f\leq n$ 所以一定能拆解下去。那么可不可能分解出来有相邻的数呢？不可能，假设分解出 $fib_{i-1}$ 和 $fib_i$，再找最大的斐波那契数的时候就会找 $fib_{i+1}$ 了，而不是这两个。

代码实现

由于需要高精，建议使用 python 实现，并且钦定权值要从小一点的地方开始钦定，这里建议是 $-100$。

B=100
n=int(input())

pos=[0]*100010
val=[0]*100010
fib=[0]*200010
fib[0]=fib[1]=1
res=[]

sumFib=0
cnt=0

minp=0x3f3f3f3f
maxp=0

for i in range(0,n):
    [pos[i],val[i]]=map(int,input().split())
    maxp=max(pos[i],maxp)
    minp=max(pos[i],minp)
    
cnt=maxp+B
for i in range(2,cnt+1):
    fib[i]=fib[i-1]+fib[i-2]

for i in range(0,n):
    sumFib+=fib[pos[i]+B]*val[i]

while fib[cnt]<sumFib:
    fib[cnt+1]=fib[cnt]+fib[cnt-1]
    cnt+=1

while sumFib>0:
    while fib[cnt]>sumFib:
        cnt-=1
    res.append(cnt-B)
    sumFib-=fib[cnt]

res.reverse()

print(*res)