【AcWing】蓝桥杯备赛-深度优先搜索-dfs(3)
目录
写在前面:
题目:93. 递归实现组合型枚举 - AcWing题库
读题:
输入格式:
输出格式:
数据范围:
输入样例:
输出样例:
解题思路:
代码:
AC !!!!!!!!!!
写在最后:
写在前面:
距离蓝桥杯已经不足一个月了,
根据江湖上的传言,
蓝桥杯最喜欢考的是深度优先搜索和动态规划,
所以蓝桥杯也叫暴搜杯、dp杯,
那我备赛当然也就从深度优先搜索,也就是所谓的dfs开始。
题目:93. 递归实现组合型枚举 - AcWing题库
读题:

输入格式:
两个整数 n,m,在同一行用空格隔开。
输出格式:
按照从小到大的顺序输出所有方案,每行 11 个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面
(例如: 1 3 5 7 排在 1 3 6 8 前面)。
数据范围:
n > 0,
0 ≤ m ≤ n,
n + (n − m) ≤ 25
输入样例:
5 3
输出样例:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
解题思路:
这道题是深度优先搜索的经典题目,
我们使用深度优先搜索的时候,
第一个要注意的点是,我们要保证,
我们写出的递归结构能够遍历所有情况,
在我们初学搜索的时候,我们一定要画一个递归搜索树观察,
递归非常抽象,画图能很好的帮助我们解题。(以上递归搜索的基本思路,多熟悉总是好的)
接下来是具体思路:
题目要求是在n个数里选m个,输出不同的选择方案
而且要升序排列,且字典序小的在前面,
我们先画一个递归搜索树理一下思路:
首先是根节点:(以n=5,m=3为例)

我的思路是按照位置填数据,
因为题目要求升序数组,所以第一个数只能是1,2,3。

根据题目升序的要求,
然后继续往下递归搜索:

继续递归搜索:

最后一行就是我们需要打印的值,
接下来将图形实现成代码:
代码:
//养成好习惯,把常用头文件包了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;//根据题目要求决定数组大小
const int N = 30;int n, m;int st[N];void dfs(int u, int start)
{//如果递归到底if(u == m){//输出for(int i = 0; i < m; i++){printf("%d ", st[i]);}puts("");return;}else{//不重复使用数字for(int i = start; i < n; i++){st[u] = i + 1;dfs(u + 1, i + 1);st[u] = 0;}}
}int main()
{scanf("%d %d", &n, &m);dfs(0, 0);return 0;
}
AC !!!!!!!!!!

写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(3)
目录 写在前面: 题目:93. 递归实现组合型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC &…...
宇宙最强-GPT-4 横空出世:最先进、更安全、更有用
文章目录前言一、准确性提升1.创造力2.视觉输入3.更长的上下文二、相比于ChatGPT有哪些提升1.GPT-4 的高级推理能力超越了 ChatGPT2.GPT-4 在多种测试考试中均优于 ChatGPT。三、研究团队在GPT-4模型都做了哪些改善1.遵循 GPT、GPT-2 和 GPT-3 的研究路径2.我们花了 6 个月的时…...
HashMap的实际开发使用
目 录 前言 一、HashMap是什么? 二、使用步骤 1.解析一下它实现的原理 编辑 2.实际开发使用 总结 前言 本章,只是大概记录一下hashMap的简单使用方法,以及理清一下hashMap的put方法的原理,以及get方法的原理。 一、Has…...
OpenCV入门(十三)快速学会OpenCV 12 图像梯度
OpenCV入门(十三)快速学会OpenCV 12 图像梯度1.Sobel算子1.1 计算x1.2 计算y1.3 计算xy2.Scharr算子2.1 计算x2.2 计算y2.3 计算xy3.Laplacian算子4.总结图像梯度计算的是图像变化的速度。对于图像的边缘部分,其灰度值变化较大,梯…...
软考:常见小题目计算题
01采购合同的类型采购合同主要包括总价类合同、成本补偿类合同、工料合同三大类合同。1、总价类合同此类合同为既定产品、服务或成果的采购设定一个总价。这种合同应在已明确定义需求,且不会出现重大范围变更的情况下使用。包括:(1࿰…...
【Linux】进程的程序替换
文章目录1. 程序替换1.创建子进程的目的是什么?2.了解程序是如何进行替换的3. 程序替换的基本原理当创建进程的时候,先有进程数据结构,还是先加载代码和数据?程序替换是整体替换,不是局部替换execl 返回值4. 替换函数1…...
【C++】模板(上)
文章目录1、泛型编程2、函数模板函数模板的实例化模板参数的匹配原则3、 类模板类模板的实例化1、泛型编程 void Swap(int& left, int& right) {int temp left;left right;right temp; } void Swap(double& left, double& right) {double temp left;left …...
express框架利用formidable上传图片
express框架,在上传图片功能方面,用formidable里面的incomingform功能,很方便。很多功能都已经封装好了,非常好用,简单,不需要写更深层次的代码了。确实不错。 下面是我自己跟着黑马教程的博客系统的部分&…...
测试背锅侠?入职软件测试后大d佬给我丢了这个bug分类分析,至今受益匪浅......
目录:导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜)前言 刚成为入职…...
STM32 OTA应用开发——通过内置DFU实现USB升级(方式1)
STM32 OTA应用开发——通过内置DFU实现USB升级(方式1) 目录STM32 OTA应用开发——通过内置DFU实现USB升级(方式1)前言1 硬件介绍2 环境搭建2.1 Keil uVsion2.2 zadig2.3 STM32CubeProgrammer2.4 安装USB驱动3 OTA升级结束语前言 …...
基于MFC的JavaScript进行网页数据交互
目录 前言 一、创建html对话框工程 二、使用步骤 1.引入JavaScript接口代码 2.重写相关接口 3.在html网页中添加C/C调用的接口 4.在MFC工程中添加调用接口 5.设置确认按键触发调用 6.运行结果 总结 前言 如何快速的进行MFC开发,这里我介绍一种JavaScript与C/C交互的…...
AUTOSAR-Fee
Fee模块 全称Flash EEPROM Emulation Module,属于ECU抽象层 Fee模块本身是脱离硬件的,但是Fee模块可能会引用的Fls模块定制API,所以只能算半抽象. FEE模块应从设备特定的寻址方案和分段中抽象出来,并为上层提供虚拟寻址方案和分段(virtual addressing scheme and segment…...
Linux基本命令——操作演示
Linux基本命令——操作演示Linux的目录结构Linux命令入门目录切换相关命令(cd/pwd)相对路径、绝对路径和特殊路径符创建目录命令(mkdir)文件操作命令part1 (touch、cat、more)文件操作命令part2 (cp、mv、rm)查找命令 …...
【Linux】目录和文件的权限
Linux中的权限有什么作用Linux权限管理文件访问者的分类文件类型和访问权限(事物属性)**文件权限值的表示方法**文件访问权限的相关设置方法chmodchownchgrpumaskumask使用 sudo分配权限目录的权限Linux中的权限有什么作用 Linux下有两种用户࿱…...
Unity 优化之Player Setting
Quality SettingPixel Light Count 使用前向渲染时最大像素光源数。也是性能关键。数量越大消耗越多。Texture Quality:贴图质量,可以选择Half Res,这样速度会更快,但是贴图质量会轻微下降。Anisotropic Textures 纹理各向异形Ant…...
Qt——通过一个简单的程序例程熟悉使用Qt Creator软件进行项目搭建的基本流程(新建项目、项目的文件组成、修改ui文件、编译运行与调试)
【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》 《QT开发实战》 《Android开发实战》...
Linux 如何使用 git | 新建仓库 | git 三板斧
文章目录 专栏导读 一、如何安装 git 二、注册码云账号 三、新建仓库 配置仓库信息 四、克隆远端仓库到本地 五、git 三板斧 1. 三板斧第一招:git add 2. 三板斧第二招:git commit 解决首次 git commit 失败的问题 配置机器信息 3. 三…...
3.springcloud微服务架构搭建 之 《springboot自动装配ribbon》
1.springcloud微服务架构搭建 之 《springboot自动装配Redis》 2.springcloud微服务架构搭建 之 《springboot集成nacos注册中心》 ribbon工作原理自己网上百度,说的都很详细 目录 1.项目引入openfeign和ribbon配置 2.新建lilock-ribbon-spring-boot-starter 3…...
【一】进程到底是个啥?
1. 什么是进程 进程(process):一个运行起来的程序,就是进程!,我们可以在任务管理中看到进程。 进程是操作系统进行资源分配的基本单位 2. 进程的管理 所谓的进程管理,其实就是分为两步&…...
[蓝桥杯] 双指针、BFS和DFS与图论问题
文章目录 一、日志统计 1、1 题目描述 1、2 题解关键思路与解答 二、献给阿尔吉侬的花束 2、1 题目描述 2、2 题解关键思路与解答 三、红与黑 3、1 题目描述 3、2 题解关键思路与解答 3、2、1 dfs题解代码 3、2、2 bfs题解答案 四、交换瓶子 4、1 题目描述 4、2 题解关键思路与…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
