P7851

· · 题解

题目大意

已知 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;
}