尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
P1706 全排列问题
记录159#includebits/stdc.h using namespace std; int path[15]; bool vis[15]; int n; void dfs(int cnt){ if(cntn){ for(int i1;in;i) cout path[i]; cout\n; return; } for(int i1;in;i){ if(vis[i]0){ vis[i]1; path[cnt]i; dfs(cnt1); vis[i]0; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; dfs(1); return 0; }题目传送门https://www.luogu.com.cn/problem/P1706前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的深度优先搜索DFS与回溯算法入门题。问题转化排列树模型生成 1∼n 的全排列本质上是在构建一棵深度为 nn 的“排列树”。我们在树的每一层对应排列中的每一个位置从 1∼n中选择一个还没有被使用过的数字填入。算法设计DFS 状态标记使用一个数组path来记录当前正在构建的排列序列。使用一个布尔数组vis来记录哪些数字已经被用过了避免重复。每次递归时枚举 1∼n 的所有数字。如果某个数字没有被用过就把它放入path中标记为已用然后进入下一层递归。当递归深度达到 n 时说明一个完整的排列已经生成将其输出。回溯的关键从下一层递归返回后必须将刚才标记为已用的数字重新标记为未用vis[i] 0以便在后续的循环中尝试其他数字。代码分块详细解释1. 全局变量定义#includebits/stdc.h using namespace std; int path[15]; bool vis[15]; int n;详细分析path数组用来存放当前正在生成的排列序列vis数组visit的缩写是一个状态标记数组vis[i] 1表示数字 ii 已经在当前排列中被使用过0表示未使用。由于题目保证 n≤9n≤9 数组开 15 足够。2. 核心逻辑DFS 搜索与回溯void dfs(int cnt){ if(cnt n){ for(int i 1; i n; i) cout path[i]; cout \n; return; } for(int i 1; i n; i){ if(vis[i] 0){ vis[i] 1; path[cnt] i; dfs(cnt 1); vis[i] 0; // 回溯撤销选择恢复现场 } } }详细分析这是代码的灵魂完美体现了回溯法“选择 - 递归 - 撤销选择”的三步曲。递归终止条件当cnt n时说明前 nn 个位置都已经填满了数字一个完整的排列已经生成。此时按照题目要求的“每个数字保留 5 个场宽”即前面加 4 个空格输出path数组。枚举与剪枝在当前位置cnt我们尝试枚举 1∼n1∼n 的所有数字。if(vis[i] 0)保证了我们只会选择那些尚未被使用的数字。状态更新与递归选定数字i后将其标记为已用vis[i] 1存入路径path[cnt] i然后进入下一层dfs(cnt 1)去填充下一个位置。回溯恢复现场当dfs(cnt 1)执行完毕返回时说明以当前数字i为起点的所有排列都已经生成完了。为了尝试下一个数字我们必须把i的状态恢复为未使用vis[i] 0这就是回溯的核心。3. 主函数与启动搜索int main(){ ios::sync_with_stdio(false); cin.tie(0); cin n; dfs(1); return 0; }详细分析读入 nn 后直接从dfs(1)开始表示从排列的第 1 个位置开始填数。由于我们是从 1 到 n 顺序枚举数字的所以生成的排列天然就是字典序的。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点路径记录path[cnt] i记录当前正在构建的排列序列保证了在到达叶子节点时能够完整地输出整个排列状态标记vis[i] 1标记数字 i 已被使用保证了“所产生的任一数字序列中不允许出现重复的数字”回溯恢复vis[i] 0撤销对数字 i 的使用标记使得数字 ii 可以在其他分支中被再次使用是生成全排列的关键字典序保证for(int i 1; i n; i)从小到大枚举数字保证了输出的排列序列天然符合字典序要求无需额外排序格式化输出cout path[i]每个数字前输出4个空格完美契合题目“每个数字保留 5 个场宽”的格式要求
RELATED

相关推荐

【单片机毕业设计推荐】 基于 51/STM32 单片机的智能台灯与温控风扇控制系统设计,基于 51/STM32 单片机的人体感应环境调控装置设计与实现(011903)

【单片机毕业设计推荐】 基于 51/STM32 单片机的智能台灯与温控风扇控制系统设计,基于 51/STM32 单片机的人体感应环境调控装置设计与实现(011903)

文章目录20 个相关毕业设计备选题目项目研究背景摘要总体方案核心功能基础功能核心功能辅助功能技术路线项目演示关于我们项目案例源码获取博主介绍:✌️码农一枚 ,专注于大学生项目实战开发、讲解和毕业🚢文撰写修改等。全栈领域优质创作者&…

📅 2026/10/9 8:25:11
《闻香识女人》4K修复版观影指南:细节解析与经典场景解读

《闻香识女人》4K修复版观影指南:细节解析与经典场景解读

1. 先确认这部电影到底讲什么,值不值得花两小时《闻香识女人》不是字面意义上的香水故事,也不是单纯的失明人士生活记录。它最核心的价值是两个处在人生低谷的人——年轻学生查理和退役中校弗兰克——在短短几天内如何通过一场纽约之旅,完成对…

📅 2026/10/16 7:05:31
从客户管理到经营闭环:2026年CRM选型的路线分化与厂商解析

从客户管理到经营闭环:2026年CRM选型的路线分化与厂商解析

2026年,国内CRM市场步入加速分化的阶段。不同企业在客户经营上的核心诉求差异明显,推动了CRM产品形态的多元化发展。一些企业需要管理复杂的销售管道与商机流程,一些企业需要覆盖全球业务的全功能套件,而越来越多的企业发现&#…

📅 2026/9/24 5:06:45
MORE NEWS

更多资讯

📰

砀山哪里可以考电工证?学历不高也能考,全国通用怎么操作

砀山哪里可以考电工证?学历不高也能考,全国通用怎么操作 你是不是也担心自己学历不够,考不了电工证?别慌, 全国通用 的特种作业操作证并不只看学历,关键是你有没有符合报考条件。今天就来聊聊 砀山哪里可以考电工证…

📰

电工证延迟申请流程多少钱?证书过期了不知道怎么复审延期

电工证延迟申请流程多少钱?证书过期了不知道怎么复审延期 证书过期了不知道怎么复审延期?现在市面上不少电工证持有者因为工作变动、疫情等特殊原因,导致证书逾期未复审,面对这种情况,很多人心里没底,不知道该如何补救。特别是像许昌这样的城市,很多电…

📰

商都县电工证报名别怕学历低,真实经历告诉你怎么顺利过审

商都县电工证报名别怕学历低,真实经历告诉你怎么顺利过审 你是不是也担心自己学历不高,连 商都县电工证报名 都报不了?别急,我来给你讲讲真实经历,看看别人怎么一步步搞定的。…

📰

特种作业实操考试心里没底怕挂科?电工证焊工证证件在哪考全攻略

特种作业实操考试心里没底怕挂科?电工证焊工证证件在哪考全攻略 实操考试心里没底怕挂科?你不是一个人。特别是在漯河这样的二三线城市,很多人从其他岗位转岗过来,想考电工证焊工证证件,却对考试流程、考试内容和考试通过率一无所知,心里没底,甚至因此…

📰

电工作业安全防护口号有效期多久 官方报名入口怎么查

电工作业安全防护口号有效期多久 官方报名入口怎么查 之前考的证在外省能不能转过来?这个问题我听过不下百次,尤其是像你这样在驻马店做中小型施工企业的老总,手里握着一帮持证电工,现在跨省施工频繁,证书的互通性直接关系到项目能不能顺利推进。别急,…

📰

电工证实操怕挂科?山东省临清电工证网上查询全攻略

电工证实操怕挂科?山东省临清电工证网上查询全攻略 实操考试心里没底怕挂科?你不是一个人。尤其是在临清,考电工证的小伙伴们大多都是抱着“能过就过”的心态去考试,结果一到实操就紧张得手心冒汗。别急,今天咱们就来聊聊 山东省临清电工证…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬