#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> perm; vector<bool> used; void dfs(int n, int q, int depth, vector<pair<int, int>>& constraints) { if (depth == n) { for (int i = 0; i < n; i++) { cout << perm[i] << " "; } cout << '\n'; return; } for (int i = n; i >= 1; i--) { if (!used[i]) { bool flag = true; for (int j = 0; j < q; j++) { if (constraints[j].first == depth + 1 && constraints[j].second == i) { flag = false; break; } } if (flag) { used[i] = true; perm[depth] = i; dfs(n, q, depth + 1, constraints); used[i] = false; } } } } int main() { int n, q; cin >> n >> q; perm.resize(n); used.resize(n + 1); vector<pair<int, int>> constraints(q); for (int i = 0; i < q; i++) { int pos, val; cin >> pos >> val; constraints[i] = make_pair(pos, val); } sort(constraints.begin(), constraints.end()); dfs(n, q, 0, constraints); return 0; }

这是一个求解排列的问题，给定一个长度为 n 的数组，要求输出这个数组的全排列，但是还有 q 个限制条件，每个限制条件表示在某个位置上只能出现某个数字。

这个问题可以用深度优先搜索来解决。我们从第一个位置开始，枚举可以放在这个位置上的数字，然后递归到下一个位置，直到填满整个数组。在枚举的时候，需要注意排除那些已经被使用过的数字以及那些和限制条件冲突的数字。

具体地，我们可以用一个 boolean 数组 used 来记录数字是否已经被使用过，用一个 vector<pair<int, int>> 来记录限制条件。在 dfs 中，我们首先检查当前位置上可以放置的数字，然后检查这个数字是否和限制条件冲突，如果不冲突，就将它标记为已经使用过，然后递归到下一个位置。如果枚举完所有可行的数字都不行，那么我们就回溯到上一个位置，尝试其他的数字。

最后，我们需要将限制条件按照位置排序，这样在 dfs 中就可以方便地判断限制条件是否冲突了。

下面是代码实现：