自动搬运

查看原文

来自洛谷，原作者为

	ycw123 逆风如解意，容易莫摧残

搬运于2025-08-24 22:33:39，当前版本为作者最后更新于2021-09-03 20:56:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目大意

已知 $k$ 和递推式

$$f_0=\inf,f_i=\min\{j|f_{i-j}>k\times j\}$$

给定 $n$，求 $f_n$。

solution

对于 10% 的数据

读懂题意，暴力模拟即可。

对于 30% 的数据

容易发现可以用单调栈优化，做到 $O(n)$ 的复杂度。

当 k=1 时

打表可以发现答案为 $lowbit(n)$。

当 k=2 时

打表可以发现与斐波那契序列有关，也即接下来所说的序列 $a$ 为斐波那契序列去掉第一个 $1$。

对于全部数据

假设存在正整数序列 $a$ 满足：

对于任意一个正整数 $n$，有且仅有一个序列 $p$ 满足

$$1\le p_1 < p_2 < \cdots <p_m$$ $$\sum_{i=1}^m{a_{p_i}}=n$$ $$\forall 1 \le i < m, k \times a_{p_i}<a_{p_{i+1}}$$

注意 是 $p_{i+1}$，而不是 $p_i+1$。 我们称 $a_{p_1}, a_{p_2},...,a_{p_m}$ 为 $n$ 的分解。 下面我们来证明对于正整数 $n$，和任意满足条件的 $a$，答案就是 $a_{p_1}$。

该定理的简要证明

首先我们发现 $\forall k, a_1=1$，也就是 $f_1=a_1=1$。

然后进行归纳证明。对于正整数 $i>1$，容易发现我们有

$$f_{i-a_{p_1}}=a_{p_2}$$

因为 $i-a_{p_1}$ 的分解为 $n$ 的分解去掉第一个数，即 $a_{p_2},a_{p_3},...,a_{p_m}$，而我们又有 $k \times a_{p_1}<a_{p_2}$，故 $j=a_{p_1}$ 时满足条件。

接下来我们要证明对于所有 $1 \le j < a_{p_1}$ 均不满足条件 $f_{i-j}>k\times j$。

采用反证法，若 $f_{i-j}>k\times j$ 成立，则 $k \times j < ( i-j$ 的分解的最小的数$)$，那么显然我们可以把 $j$ 的分解接上 $i-j$ 的分解形成一个新的分解，并且这个分解的不同于 $i$ 原来的分解，这样 $i$ 就有超过一个分解个数，与条件矛盾，所以 $f_i=a_{p_1}$ 成立，证毕。

序列的构造和证明

不妨设 $a_0=0$，设序列 $b_i$ 表示 能用 $a_1,a_2,...,a_i$ 可以表示出来的最大整数，令 $a_{i+1}=b_i+1$ 即可。

现在我们要证明这样构造的序列是满足条件的。

我们还是采用归纳证明，容易发现 $1=a_1=1$ 满足条件。

那么对于一个正整数 $n>1$，我们设 $m=\max\{m\mid a_m\le n\}$，根据序列的构造方法，我们容易证明 $n$ 的分解的最大数一定是 $a_m$，那么 $n$ 的分解 $=n-a_m$ 的分解再添上一个 $a_m$。

关于程序实现

容易发现以及证明 $b_i=\max\{b_j|a_j \times k<i\}+a_i$。

我们只需要双指针一下，枚举当前的 i,j。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e7;
long long n,a[N],b[N];
int k,i=0,j=0;
int main(){
    cin>>n>>k;
    while(a[i]<n) {
        ++i;
        a[i]=b[i-1]+1;
        while(j<i-1 && a[j+1]*k < a[i]) j++;
        b[i]=b[j]+a[i];
    }
    for(;i;--i)
        if(n-a[i]>0) n-=a[i];
        else if(n-a[i]==0) break;
    printf("%lld",a[i]);
    return 0;
}