题意分析

1. 问题定义：给定 $m$ 和 $n$，我们需要生成所有可能的 $n$ 元组 $(a_1, a_2, \dots, a_n)$，其中 $a_1 + a_2 + \dots + a_n = m$，并且 $a_1 \leq a_2 \leq \dots \leq a_n$。然后按照字典序排列这些划分，找到第 $k$ 个划分。
2. 字典序规则：类似于字符串的字典序，从左到右比较，第一个不同的位置决定大小关系。
3. 初始划分：字典序最小的划分是 $[1, 1, \dots, 1, m - n + 1]$，即前 $n-1$ 个 $1$，最后一个元素补足总和。

解题思路

1. 生成所有可能的划分：
   • 使用回溯法或动态规划生成所有满足条件的 $n$ 元组。
   • 由于 $m \leq 220$ 且 $n \leq 10$，直接生成所有划分是可行的。
2. 排序划分：
   • 按照字典序对所有划分进行排序。
3. 查询第 $k$ 个划分：
   • 直接输出排序后的第 $k-1$ 个划分（假设索引从 $0$ 开始）。

C++代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
#define M 500
#define N 100
int  dp[M][N][M];//和，位数，首向量
 
bool vis[M][N][M];
 
int getdp(int m,int n,int x)
{
	if(m<x)return 0;
	if(vis[m][n][x])return dp[m][n][x];
	vis[m][n][x]=true;
	if(n==1)
	{
		if(x==m)dp[m][n][x]=1;
		else dp[m][n][x]=0;
	}
	else {
		int ans=0;
		for(int i=x;i<=m-x;i++)
			ans+=getdp(m-x,n-1,i);
		dp[m][n][x]=ans;
	}
	return dp[m][n][x];
}
 
void dfs(int m,int n,int k,int pre)
{
	if(m<=0||k<=0||n<=0){return;}
	for(int i=pre;i<=m;i++)
	{
		int d=getdp(m,n,i);
		if(d<k){
			k-=d;
		}
		else
		{
			printf("%d\n",i);
			dfs(m-i,n-1,k,i);
		//	cout<<dp[m][n][i]<<'!'<<endl;
			break;
		}
	}
}
 
int main()
{
	int C;
	scanf("%d",&C);
	int m,n,k;
	while(C--)
	{
		scanf("%d%d%d",&m,&n,&k);
		dfs(m,n,k,1);
	}
	return 0;
}