社区讨论
有什么问题
P1088[NOIP 2004 普及组] 火星人参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m3v7bms6
- 此快照首次捕获于
- 2024/11/24 14:11 去年
- 此快照最后确认于
- 2025/11/04 14:02 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
// n表示火星人手指的数目,m表示要加上去的小整数
// s用于记录当前已经生成的排列序号,t作为标记,用于判断是否已经找到目标排列
// a数组用于存储火星人手指的排列顺序,b数组用于标记数字是否已经在当前排列中使用过
int n, m, s = 0, t = 0, a[10005], b[10005];
// dfs函数用于通过深度优先搜索的方式来枚举所有可能的排列情况
// 参数x表示当前正在确定位置的手指编号(从1开始计数)
void dfs(int x) {
// 如果已经找到目标排列(t被标记为1),则直接返回,不再继续搜索
if (t == 1) return;
// 如果已经确定完所有手指的位置(即x超过了手指总数n),说明生成了一个完整的排列
if (x > n) {
s++; // 排列序号加1,表示生成了一个新的排列
// 如果当前生成的排列序号正好是要找的(加上给定小整数m后的那个排列)
if (s == m + 1) {
// 输出这个排列对应的手指顺序,每个数字之间用空格隔开
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
t = 1; // 标记已经找到目标排列,后续搜索可以停止
return;
}
}
// 尝试将每个数字放在当前手指位置x上,进行排列的生成
for (int i = 1; i <= n; i++) {
// 如果是刚开始生成排列(s为0),让i从当前位置的手指原本的值开始尝试
// 这样可以避免重复生成一些已经确定好开头部分的排列情况,起到一定的剪枝优化作用
if (s == 0) i = a[x];
// 如果数字i还没有在当前正在生成的排列中被使用过
if (b[i] == 0) {
b[i] = 1; // 标记数字i已经被使用
a[x] = i; // 将数字i放在当前手指位置x上
dfs(x + 1); // 继续确定下一个手指位置的数字,进行深度优先搜索
b[i] = 0; // 回溯,将数字i的使用标记取消,以便尝试其他可能的排列情况
}
}
}
int main() {
// 输入火星人手指的数目n和要加上的小整数m
cin >> n >> m;
// 这里原本代码应该是输入火星人手指的初始排列顺序,原代码写的是输出a[i]有误,应该改为输入
for (int i = 1; i <= n; i++)
cin >> a[i];
dfs(1); // 从第一个手指位置(编号为1)开始进行深度优先搜索,生成排列
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...