当前位置: 首页 > news >正文

【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)

目录 写在前面&#xff1a; 题目&#xff1a;92. 递归实现指数型枚举 - AcWing题库 读题&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 数据范围&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; 代码&#xff1a; AC &…...

孩子免费就读|私企经理自费赴美国东海岸高校访学

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

前端面试hr经常会问的问题

文章目录前言1.自我介绍2.为什么你要离职&#xff1f;3.工作经历4.职业规划5.优点、缺点6.还有什么要问的总结前言 这里记录了一些面试中hr或者项目负责人经常会问的一些问题&#xff0c;可以提前参考参考&#xff0c;想想该怎么回答&#xff0c;为之后的面试做好准备&#xf…...

C动态数组

在实际项目中&#xff0c;我们经常与各式各样的数据打交道。 例如&#xff1a;我们处理的是学生的数据。 struct student {int id; // 学号char name[20]; // 姓名int gender; // 性别int mark; // 成绩 };学生数据使用一个结构体表示&#xff0c;该结构体拥有4个成员。分别为…...

【STL一】STL组件(容器、迭代器、算法)

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

Java每日一练(20230312)

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

Linux中sudo,su与su -命令的区别

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

归并排序有多简单?一幅图教你看懂【C语言】

目录 归并排序的递归实现 代码实现 归并排序的非递归实现 代码实现 归并排序的思想很简单——分治法。简单地说&#xff0c;归并排序的是将序列拆分成几段子序列&#xff0c;将每一段子序列分别进行排序&#xff0c;排好之后再将有序的子序列归并&#xff08;有点像合并两…...

C++-Z字扫描实现(Zigzag Scan)

Z字扫描(Zigzag Scan) 将二维矩阵压缩成行输出&#xff1a; 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{//偶数&#xff0c;向上扫描for(int jmi…...

【华为机试真题详解 Python实现】求最大数字【2023 Q1 | 100分】

文章目录 前言题目描述输入描述输出描述示例 1示例 2题目解析参考代码前言 《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。 如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议! 本文解法非最优解(即…...

面对数万亿产业规模,如何掘金工业互联网?

近年来&#xff0c;加速工业互联网建设的声音越来越响亮。一方面&#xff0c;政策利好&#xff0c;持续驱动。从2017年的《国务院关于深化“互联网先进制造业” 发展工业互联网的指导意见》到《工业互联网创新发展三年行动计划&#xff08;2021-2023年&#xff09;》&#xff0…...

#ifdefine #define #endif (避免头文件被重复包含的真正含义)

宏定义 首先在谈论正式话题之前&#xff0c;需要先介绍一个基础概念&#xff0c;也是前提&#xff0c;那就是宏定义。 #define demo 1 #define PI 3.14我们都知道这样会将demo 在预处理阶段替换或者说展开为1&#xff0c;Pi 替换为3.14。 #define 宏定义一个标识符来表示一个…...

单片机能运行操作系统吗?

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

Python之webmagic爬虫优点与使用

一、webmagic的优点它更偏向于java的语法&#xff0c;对于熟悉java的工程师来说学习成本较低。提供多种选择器&#xff0c;如css选择器、xpath、正则等。有一个模块pipeline&#xff1a;可通过简单地配置&#xff0c;可以将爬虫抽取到的信息&#xff0c;持久化到文件、数据库等…...

代码随想录动态规划 || 121 122

Day42121. 买卖股票的最佳时机力扣题目链接给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返…...

C++STL库中不可或缺的部分—string(模拟实现)

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

MySQL复合查询

文章目录基本查询回顾多表查询自连接子查询单行子查询多行子查询多列子查询在from子句中使用子查询合并查询unionunion all基本查询回顾 查询的员工部门表结构&#xff1a; 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大影响因子

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

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...