P1025 [NOIP2001 提高组] 数的划分 题解

· · 题解

P1025 [NOIP2001 提高组] 数的划分 题解

题目分析

这道题的难点主要在于需要求不同的方案，并且不论顺序。

观察后发现，所有的答案一定是一个单调不下降序列。即：对于任意答案数组 a，一定有 a_{i} \le a_{j}(i < j)。（如果有 a_{i} > a_{j}，那么两数必须交换，化为 a_{i} < a_{j} 的形式，否则会导致答案重复计数。）

那么，我们可以得到 DFS 时的一个规律：已知整数为 n，需要将其分为 k 份，当目前搜索到的数是 a_{j} 时，应有 a_{j-1} \le a_{j} \le \lfloor\frac{n-\sum_{i = 1}^{j-1} a_{i}}{k-j-1}\rfloor。

代码实现

#include<bits/stdc++.h>
using namespace std;

int n,k;
int ans;
int sum;//保存已经搜索到的数的和

void dfs(int x,int dep){
    if(dep==k-1){ //当深度达到 k-1 时就不用搜了 因为最后一个值已经确定了
        ans++;
        return;
    }
    sum+=x;
    for(int i=x;i<=(n-sum)/(k-dep);i++){ //i 的值应该大于等于他的上一个数，小于等于 剩余的数/剩余的数量（向下取整）
        dfs(i,dep+1);
    }
    sum-=x;//恢复原状态
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n/k;i++){
        sum=0;//每次对一个新的数进行 dfs 之前，先清空 sum
        dfs(i,1);
    }
    cout<<ans<<endl;
    return 0;
}

提交记录

评测记录

2025.1.16：对题解中给出的公式进行了修改。