【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
目录
写在前面:
题目:92. 递归实现指数型枚举 - AcWing题库
读题:
输入格式:
输出格式:
数据范围:
输入样例:
输出样例:
解题思路:
代码:
AC !!!!!!!!!!
写在最后:
写在前面:
距离蓝桥杯已经不足一个月了,
根据江湖上的传言,
蓝桥杯最喜欢考的是深度优先搜索和动态规划,
所以蓝桥杯也叫暴搜杯、dp杯,
那我备赛当然也就从深度优先搜索,也就是所谓的dfs开始。
题目:92. 递归实现指数型枚举 - AcWing题库
读题:
输入格式:
输入一个整数 n。
输出格式:
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围:
1 ≤ n ≤ 15
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
解题思路:
这道题是深度优先搜索的经典题目,
我们使用深度优先搜索的时候,
第一个要注意的点是,我们要保证,
我们写出的递归结构能够遍历所有情况,
在我们初学搜索的时候,我们一定要画一个递归搜索树观察,
递归非常抽象,画图能很好的帮助我们解题。(以上递归搜索的基本思路,多熟悉总是好的)
接下来是具体思路:
题目要求我们随机选取输出每种方案,而且要求升序输出。
我们根据要求,画出对应的搜索树:(以n=3为例)
首先是根节点:
递归搜索:
因为题目要求是升序数组,所以从第二个位置开始,
就只能填2,再下一个就得填3,以满足题目要求:
继续搜索:
如果位置已经使用过了,就搜索下一个位置,
没有位置就停下。
最后:
我们根据画出来的搜索树写代码:
代码:
//养成好习惯,先把常用头文件包了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;//数组的大小,比题目要求大即可(题目要求n是小于等于15的)
const int N = 20;//全局变量的数组会把数组元素初始化成0
int st[N];//这个是需要输入的变量
int n;void dfs(int u)
{//数组已经存了n个数,达成条件就可以打印了if(u == n){for(int i = 0; i < n; i++){//st数组元素 == 1 表示这个位置需要输出if(st[i] == 1){printf("%d ", i + 1);}}puts("");return;}else{//把数组设为1表示该位置写入了数据st[u] = 1;dfs(u + 1);st[u] = 0;//把数组设为2表示该位置为空st[u] = 2;dfs(u + 1);st[u] = 0;}
}int main()
{scanf("%d", &n);dfs(0);return 0;
}
AC !!!!!!!!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:

【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC &…...

孩子免费就读|私企经理自费赴美国东海岸高校访学
私企U经理无文章无课题,出国访学除了为考察市场、拓宽人脉、提升履资外,另一个主要目的是带孩子在美国接受当地免费的公立中小学教育,并把访学目标学校定位在东海岸。最终其采纳了板凳费相对较低的佐治亚大学邀请函,签证时居然全家…...

前端面试hr经常会问的问题
文章目录前言1.自我介绍2.为什么你要离职?3.工作经历4.职业规划5.优点、缺点6.还有什么要问的总结前言 这里记录了一些面试中hr或者项目负责人经常会问的一些问题,可以提前参考参考,想想该怎么回答,为之后的面试做好准备…...
C动态数组
在实际项目中,我们经常与各式各样的数据打交道。 例如:我们处理的是学生的数据。 struct student {int id; // 学号char name[20]; // 姓名int gender; // 性别int mark; // 成绩 };学生数据使用一个结构体表示,该结构体拥有4个成员。分别为…...

【STL一】STL组件(容器、迭代器、算法)
【STL一】STL组件(容器、迭代器、算法)一、STL二、STL组件(component)1、stl六大组件2、C STL的13个头文件3、stl所有头文件三、容器(container)1、序列容器(Sequence container)——顺序容器2、关联容器&a…...

Java每日一练(20230312)
目录 1. 两数之和 II ★ 2. 反转链表 ★★ 3. 二叉树的层序遍历 II ★★★ 🌟 每日一练刷题专栏 C/C 每日一练 专栏 Python 每日一练 专栏 Java 每日一练 专栏 1. 两数之和 II 给定一个已按照 非递减顺序排列 的整数数组 numbers ,请你从数…...

Linux中sudo,su与su -命令的区别
前言 su命令就是切换用户的工具,怎么理解呢?比如我们以普通用户tom登录的,但要添加用户任务,执行useradd ,tom用户没有这个权限,而这个权限恰恰由root所拥有。解决办法无法有两个,一是退出tom用…...

归并排序有多简单?一幅图教你看懂【C语言】
目录 归并排序的递归实现 代码实现 归并排序的非递归实现 代码实现 归并排序的思想很简单——分治法。简单地说,归并排序的是将序列拆分成几段子序列,将每一段子序列分别进行排序,排好之后再将有序的子序列归并(有点像合并两…...
C++-Z字扫描实现(Zigzag Scan)
Z字扫描(Zigzag Scan) 将二维矩阵压缩成行输出: int index0; for(int i0;i<rowscols-1;i){//i是第几条对角线if(i&1){//odd,向下扫描for(int jmax(0,i-cols1);j<min(i,row-1);j){res[index]mtx[j][i-j];}//}else{//偶数,向上扫描for(int jmi…...
【华为机试真题详解 Python实现】求最大数字【2023 Q1 | 100分】
文章目录 前言题目描述输入描述输出描述示例 1示例 2题目解析参考代码前言 《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。 如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议! 本文解法非最优解(即…...

面对数万亿产业规模,如何掘金工业互联网?
近年来,加速工业互联网建设的声音越来越响亮。一方面,政策利好,持续驱动。从2017年的《国务院关于深化“互联网先进制造业” 发展工业互联网的指导意见》到《工业互联网创新发展三年行动计划(2021-2023年)》࿰…...
#ifdefine #define #endif (避免头文件被重复包含的真正含义)
宏定义 首先在谈论正式话题之前,需要先介绍一个基础概念,也是前提,那就是宏定义。 #define demo 1 #define PI 3.14我们都知道这样会将demo 在预处理阶段替换或者说展开为1,Pi 替换为3.14。 #define 宏定义一个标识符来表示一个…...

单片机能运行操作系统吗?
先直接上答案:可以!但是操作系统不是刚需,上操作系统比较占用单片机的资源,比如占用比较多的FLASH和RAM,间接增加了硬件成本,哪怕成本增加1毛钱,对于上量的产品,分分钟是一个工程师的…...

Python之webmagic爬虫优点与使用
一、webmagic的优点它更偏向于java的语法,对于熟悉java的工程师来说学习成本较低。提供多种选择器,如css选择器、xpath、正则等。有一个模块pipeline:可通过简单地配置,可以将爬虫抽取到的信息,持久化到文件、数据库等…...
代码随想录动态规划 || 121 122
Day42121. 买卖股票的最佳时机力扣题目链接给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返…...

C++STL库中不可或缺的部分—string(模拟实现)
前文大家好,本篇文章主要是讲解一下string一些常用接口的模拟实现。众所周知,在日常生活中,字符串无处不在,如just do it,中国,一坤年等,想要在计算机上将这些字符展现出来就需要用到string类,而对我们C程序…...

MySQL复合查询
文章目录基本查询回顾多表查询自连接子查询单行子查询多行子查询多列子查询在from子句中使用子查询合并查询unionunion all基本查询回顾 查询的员工部门表结构: mysql> show tables; ----------------- | Tables_in_scott | ----------------- | dept …...

PCIe 资料收集2
文章目录感官认识PCIe的存储空间PCIe 在 linux 下的驱动PCIe 验证1.PCIe 传递裸数据2.PCIe 转其他设备PCIe转其他总线RS232USB从用户空间理解PCIe感官认识 总线协议接口 视频介绍PCIe 视频介绍及PCIe文字介绍 PCIe上可以接各种控制器硬盘控制器硬盘声卡控制器音响咪头/耳机显…...
Linux网络编程(使用VScode远程登录ubuntu)
文章目录 前言一、SSH插件的安装1.SSH简单介绍2.SSH插件安装和配置步骤二、安装C/C++插件总结前言 本篇文章将带大家进行网络编程的准备工作,使用vscode进行远程登录ubuntu。为什么要使用vscode进行远程登录ubantu呢?因为有些小伙伴的电脑可能性能不够开启虚拟机后会导致电脑…...

如何提高项目估算精准度?关键看5大影响因子
如何让项目估算工作更加精准,我们需要重点关注5大调整因子。 1、功能点调整因子 首先需要对功能点因子进行调整,区分不同类型的系统特征值。 因为不同的系统,对项目开发的影响程度不同,一般我们把系统特征值分为14种类型ÿ…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...