当前位置: 首页 > 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…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...