自动搬运

查看原文

来自洛谷，原作者为

	gavinliu266 Hello, world!

搬运于2025-08-24 22:58:02，当前版本为作者最后更新于2024-05-15 21:00:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

fix：只有 dfs，没有回溯。

update：增加亿点内容。

思路 1

可以想到 dfs，搜到一个完整的序列就输出。

这里只要每个循环都从上一次的地方继续，就可以保证序列为升序；每个循环从小到大枚举，就保证了序列间是升序排列的。

时间复杂度：应该是 $O((n-m)^m)$。

这个时间复杂度也不是很确定，所以欢迎来喷。

代码实现

#include <cstdio>
using namespace std;
int n, r;
int f[25];
void dfs(int h, int l) {
	if(h == r + 1) {  // 搜到了，输出
		for(int i = 1; i <= r; ++i)
			printf("%d ", f[i]);
		putchar('\n');
		return;
	}
	for(int i = l; i <= n - r + h; ++i) {
		f[h] = i;
		dfs(h + 1, i + 1);  // 保证升序
	}
}
int main() {
	scanf("%d%d", &n, &r);
	dfs(1, 1);
}

思路 2

hgckythgcfhk 的题解给了我另一种思路。本题可以转化为求有 $m$ 个 $0$，$n-m$ 个 $1$ 的序列的全排列。

如果当前位是 $1$ 就输出，否则不输出。

实现只需要用 prev_permutation 即可。

时间复杂度：$O(nC^m_n)$。

代码实现

#include <cstdio>
#include <algorithm>
using namespace std;
int n, r;
int f[25];
int main() {
	scanf("%d%d", &n, &r);
	for(int i = 1; i <= r; ++i)
		f[i] = 1;
	do {
		for(int i = 1; i <= n; ++i)
			if(f[i]) printf("%d ", i);
		putchar('\n');
	} while(prev_permutation(f + 1, f + n + 1));  // 注意是 prev，因为初始排列的编号是最大的。
}