题意分析

我们需要找到正整数 $m$ 划分为 $n$ 个非递减正整数的所有可能分区，并按字典序排序后输出第 $k$ 个分区。

• 分区：$a_1 + a_2 + \ldots + a_n = m$，且 $a_1 \leq a_2 \leq \ldots \leq a_n$。
• 字典序：类似字符串比较，从左到右逐位比较，第一个不同的数决定顺序。
• 输入限制：$1 \leq m \leq 220$，$1 \leq n \leq 10$，$k$ 不超过分区总数。

解题思路

1. 递归生成分区：
   • 使用回溯法生成所有可能的分区，并记录它们的字典序。
   • 每次递归时，确保当前数不小于前一个数，并保证剩余数的分配合法。
2. 提前终止优化：
   • 由于 $k$ 可能很大，直接生成所有分区再排序会超时，因此需要找到第 $k$ 个分区而不生成全部。
   • 可以计算以某个数开头的分区数量，如果 $k$ 在该范围内，则递归进入该分支；否则调整 $k$ 并继续。
3. 动态规划计算分区数：
   • 定义 $dp[i][j][s]$ 表示前 $i$ 个数，最后一个数为 $j$，总和为 $s$ 的分区数。
   • 通过递推关系计算分区数，用于快速判断第 $k$ 个分区的位置。

C++实现

cpp

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_M = 220;
const int MAX_N = 10;

int dp[MAX_N + 1][MAX_M + 1][MAX_M + 1];

void precompute_partitions() {
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1; i <= MAX_N; ++i) {
        for (int j = 1; j <= MAX_M; ++j) {
            for (int s = j; s <= MAX_M; ++s) {
                for (int k = 0; k <= j; ++k) {
                    dp[i][j][s] += dp[i - 1][k][s - j];
                }
            }
        }
    }
}

void find_partition(int m, int n, int k, vector<int>& partition) {
    int last = 1;
    for (int i = 0; i < n; ++i) {
        for (int x = last; x <= m; ++x) {
            int cnt = 0;
            for (int k_prev = 0; k_prev <= x; ++k_prev) {
                cnt += dp[n - i - 1][k_prev][m - x];
            }
            if (k > cnt) {
                k -= cnt;
            } else {
                partition[i] = x;
                last = x;
                m -= x;
                break;
            }
        }
    }
}

int main() {
    precompute_partitions();
    int c;
    cin >> c;
    while (c--) {
        int m, n, k;
        cin >> m >> n >> k;
        vector<int> partition(n);
        find_partition(m, n, k, partition);
        for (int num : partition) {
            cout << num << endl;
        }
    }
    return 0;
}