B3623 枚举排列 題解

ShanCreeperPro · 2022-04-22 22:14:06 · 题解

B3623 枚举排列 題解

如果您做完了此题，您可以尝试：

B3621 枚举元组

B3622 枚举子集

B3624 猫粮规划

题目大概的意思就是从 n 个人中选出 k 人排列，输出所有的排列方案。

这和枚举元组和枚举子集不一样的是，一个人在一个方案中只能出现一次。

方法1： 枚举所有方案后排除非法方案。

我们可以直接枚举 k 元组，然后将非法的方案剔除。

时间复杂度为 O(n^k)，无法胜任此题。

所以我们要想其他的方法。

方法2： 使用一种方法判断该数是否使用过。

我们可以用 use 数组判断数字 i 是否被使用过，如果使用过标记位 1。

在这个例子中，数字 1 和 2 已经被使用，所以对应的 use 数组中全部标记 1，下次枚举是遇到 1 就可以直接跳过。

可以写一个 dfs 函数来完成此题。

• 定义数组 a 存储枚举的数列，其中 a_i 表示第 i 位的数字；
• 定义数组 use 记录已经使用过的数字，其中在 use_i 中如果为 1 则为使用过，否则为未使用；
• 在发现 use_i=0 时，把 i 存入 a_i，将 use_i 标记为 1，递归下一个数字，递归完成后要将 use_i 标记为 0；

这就是我们的 dfs 函数。

管理员注：

由于课程需要本题不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】