社区讨论

有什么问题

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 条回复,欢迎继续交流。

正在加载回复...