题解：P10448

gavinliu266 · 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，因为初始排列的编号是最大的。
}