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

NO.71十六届蓝桥杯备战|搜索算法-递归型枚举与回溯剪枝|枚举子集|组合型枚举|枚举排列|全排列问题(C++)

news 来源：原创 2025/8/21 23:18:27

什么是搜索？
搜索，是⼀种枚举，通过穷举所有的情况来找到最优解，或者统计合法解的个数。因此，搜索有时候也叫作暴搜。
搜索⼀般分为深度优先搜索(DFS)与宽度优先搜索(BFS)。
深度优先遍历vs深度优先搜索，宽度优先遍历vs宽度优先搜索
遍历是形式，搜索是⽬的。
不过，在⼀般情况下，我们不会去纠结概念的差异，两者可以等同。
回溯与剪枝

回溯：当在搜索的过程中，遇到⾛不通或者⾛到底的情况时，就回头。
剪枝：剪掉在搜索过程中，剪掉重复出现或者不是最优解的分⽀
搜索的本质：对决策树来一次遍历，直到把所有的情况全部收集到

递归型枚举与回溯剪枝初识

画决策树；
根据决策树写递归

B3622 枚举子集（递归实现指数型枚举） - 洛谷

设⼀共有3个数，分别是1，2，3。「从前往后」考虑每⼀个数，针对当前这个数「选」或者「不选」

设计递归函数：

重复⼦问题：针对某⼀位，「选」或者「不选」这个数。因为最终结果要按照「字典序」输出，我们可以「先考虑不选」，然后「再考虑选」；
实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰

#include <bits/stdc++.h>
using namespace std;int n;
string path;void dfs(int pos)
{if (pos > n){//path存着前n个人的决策cout << path << endl;return;}//不选path += 'N';dfs(pos+1);path.pop_back(); //回溯，清空现场//选path += 'Y';dfs(pos+1);path.pop_back(); //回溯，清空现场
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;dfs(1);return 0;
}

P10448 组合型枚举 - 洛谷

设n = 4, m = 3 ，「从前往后」考虑3 个位置应该选哪个数，我们可以画出如下决策树

设计递归函数：

重复⼦问题：当前这⼀位，应该放哪个数上去。因为这是⼀个「组合」问题，不涉及排列，所以我们当前位置开始放的数，应该是「上次决策的数的下⼀位」
实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰。

#include <bits/stdc++.h>
using namespace std;int n, m;
vector<int> path;void dfs(int pos, int begin)
{if (pos > m){for (auto x : path) cout << x << " ";cout << endl;return;}for (int i = begin; i <= n; i++){path.push_back(i);dfs(pos+1, i+1);path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;dfs(1, 1);return 0;
}

#include <bits/stdc++.h>
using namespace std;int n, m;
vector<int> path;void dfs(int begin)
{if (path.size() == m){for (auto x : path) cout << x << " ";cout << endl;return;}for (int i = begin; i <= n; i++){path.push_back(i);dfs(i+1);path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;dfs(1);return 0;
}

B3623 枚举排列（递归实现排列型枚举） - 洛谷

设n = 3, k = 2 ，⼀共要选出两个数，可以依次「考虑要选出来的数」是谁，画出如下决策树

设计递归函数：

重复⼦问题：考虑这⼀位要放上什么数。因为是「排列」问题，所以我们直接从1开始枚举要放的数。
剪枝：在这⼀条路径中，我们「不能选择之前已经选择过的数」。
实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰

#include <bits/stdc++.h>
using namespace std;const int N = 15;int n, k;
vector<int> path;
bool st[N]; //标记选过的数void dfs()
{if (path.size() == k){for (auto x : path) cout << x << " ";cout << endl;return;}for (int i = 1; i <= n; i++){if (st[i]) continue;path.push_back(i);st[i] = true;dfs();//恢复现场path.pop_back();st[i] = false;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;dfs();return 0;
}

P1706 全排列问题 - 洛谷

跟上⼀道题的决策⼀样，我们可以枚举每⼀位应该放上什么数，只不过少了k的限制。剪枝的策略还是⼀样的，那就是在路径中，「不能选择之前已经选过的数」

#include <bits/stdc++.h>
using namespace std;const int N = 15;int n;
vector<int> path;
bool st[N];void dfs()
{if (path.size() == n){for (auto x : path){printf("%5d", x);        }cout << endl;return;}for (int i = 1; i <= n; i++){if (st[i]) continue;path.push_back(i);st[i] = true;dfs();path.pop_back();st[i] = false;}
}int main()
{cin >> n;dfs();return 0;
}

NO.71十六届蓝桥杯备战|搜索算法-递归型枚举与回溯剪枝|枚举子集|组合型枚举|枚举排列|全排列问题(C++)

什么是搜索？ 搜索，是⼀种枚举，通过穷举所有的情况来找到最优解，或者统计合法解的个数。因此，搜索有时候也叫作暴搜。搜索⼀般分为深度优先搜索(DFS)与宽度优先搜索(BFS)。深度优先遍历vs深度优先搜索，宽度…...

编程日记 2025/8/21 23:18:27

C++ 中为什么构造函数不需要实现虚函数，而析构函数需要？

在C中，构造函数不需要是虚函数，而析构函数往往需要，原因如下： 构造函数对象创建顺序：构造函数的主要任务是初始化对象的成员变量，创建对象时需要先调用基类的构造函数，再调用派生类的构造函数…...

编程日记 2025/8/20 19:16:31

如何获取oracle cloud永久免费的vps(4C/24G)?

1.注册oracle cloud账号 Oracle Cloud 免费套餐 | Oracle 中国新注册的小伙伴，可以在 30 天内，利用 300 美元免费储值，任性使用所有 Oracle Cloud 基础设施服务。 30 天后呢？你仍然可以畅享 Always Free 免费套餐中的云服务&am…...

编程日记 2025/8/22 18:27:03

TypeScript面试题集合【初级、中级、高级】

初级面试题什么是TypeScript？ TypeScript是JavaScript的超集，由Microsoft开发，它添加了可选的静态类型和基于类的面向对象编程。TypeScript旨在解决JavaScript的某些局限性，比如缺乏静态类型和基于类的面向对象编程&#xff0c…...

编程日记 2025/8/19 4:22:41

java面试篇并发编程篇

目录 1.线程的基础知识 1.线程与进程的区别？ 2.并行与并发的区别？ 3.创建线程的方式有哪些？ 4.线程包括哪些状态？状态之间是如何变化的？ 5.T1，T2，T3三个线程新建完毕后，如何保证…...

编程日记 2025/8/22 18:36:20

掌握 JSON 到表格转换：全面指南

高效地转换数据格式对于现代数据处理至关重要。JSON（JavaScript 对象表示法）因其灵活性而广受欢迎，而 CSV 或 Excel 等表格格式则更适用于数据分析和可视化。本文将介绍多种 JSON 转换为表格格式的方法，帮助您提升数据处理和可视化…...

编程日记 2025/8/22 18:34:26

【Spring Cloud Netflix】GateWay服务网关

1.基本概述 GateWay用于在微服务架构中提供统一的入口点，对请求进行路由，过滤和处理。它就像是整个微服务系统的大门，所有外部请求都要通过它才能访问到后端的各个微服务。 2.核心概念 2.1路由(Route) 路由是Spring Cloud gateWay中最基本…...

编程日记 2025/8/22 2:05:45

国产芯片解析：龙讯USB Type-C/DP Transmitter多场景覆盖，定义高速互联新标杆

在智能设备功能日益复杂化的今天，高速数据传输、高清视频输出与多功能接口融合已成为行业刚需。龙讯半导体（Lontium）凭借其领先的芯片设计能力，推出多款‌USB Type-C/DP Transmitter芯片‌，覆盖从消费电子到工业应用的…...

编程日记 2025/8/18 1:06:49

普通答案： #box:hover #item1{transform: rotate(-60deg); } #box:hover #item2{transform: rotate(-50deg); } #box:hover #item3{transform: rotate(-40deg); } #box:hover #item4{transform: rotate(-30deg); } #box:hover #item5{transform: rotate(-20deg); }…...

编程日记 2025/8/22 18:36:19

【Kubernetes】StorageClass 的作用是什么？如何实现动态存储供应？

StorageClass 使得用户能够根据不同的存储需求动态地申请和管理存储资源。 StorageClass 定义了如何创建存储资源，并指定了存储供应的配置，例如存储类型、质量、访问模式等。为动态存储供应提供了基础，使得 Kubernetes 可以在用户创建 PVC 时…...

编程日记 2025/8/21 20:15:53

4月7号.

双列集合的特点: Map中的常见API: //1.创建Map集合的对象 Map<String, String> m new HashMap<>();//2.添加元素 Stringvalue1 m.put("郭靖","黄蓉"); System.out.println(value1); m.put("韦小宝","沐剑屏"); m.put(&q…...

编程日记 2025/8/20 6:47:55

C++抽卡模拟器

近日在学校无聊，写了个抽卡模拟器供大家娱乐。代码实现以下功能：抽卡界面，抽卡判定、动画播放、存档。 1.抽卡界面及判定技术有限，不可能做的和原神一样精致。代码如下（注：这不是完整代码，…...

编程日记 2025/8/21 1:43:20

蓝桥杯 2. 开赛主题曲【算法赛】

2.开赛主题曲【算法赛】 - 蓝桥云课这道题和3. 无重复字符的最长子串 - 力扣（LeetCode）类似，因为题目中规定只有小写字母，所以定义统计数组时只需要定义26个字母即可，然后每次遍历的字符减去‘a’即为他的下标 impo…...

编程日记 2025/8/22 18:27:04

Spring Boot 中的 Bean

2025/4/6 向全栈工程师迈进！ 一、Bean的扫描在之前，对于Bean的扫描，我们可以在XML文件中书写标签，来指定要扫描的包路径，如下所示,可以实通过如下标签的方式： <context:component-scan base-package&…...

编程日记 2025/8/21 22:07:40

基于springboot科研论文检索系统的设计(源码+lw+部署文档+讲解)，源码可白嫖!

摘要随着我国经济的高速发展与人们生活水平的日益提高，人们对生活质量的追求也多种多样。尤其在人们生活节奏不断加快的当下，人们更趋向于足不出户解决生活上的问题，线上管理系统展现了其蓬勃生命力和广阔的前景。与此同时，在此…...

编程日记 2025/8/22 18:36:21

Mysql入门

一、数据库三层结构所谓安装Mysql数据库，就是在主机安装一个数据库管理系统(DBMS)，这个管理程序可以管理多个数据库。DBMS(database manage system)一个数据库中可以创建多个表，以保存数据(信息)。数据库管理系统(DBMS)、数据库和表的关系如…...

编程日记 2025/8/22 18:34:26

如何解决uniapp打包安卓只出现功能栏而无数据的问题

如何解决uniapp打包安卓只出现功能栏而无数据的问题经验来自：关于Vue3中调试APP触发异常：exception:white screen cause create instanceContext failed,check js stack -> at useStore (app-service.js:2309:15)解决方案 - 甲辰哥来帮你算命 - 博客…...

编程日记 2025/8/19 21:26:55

Python高级爬虫之JS逆向+安卓逆向1.1节-搭建Python开发环境

目录引言： 1.1.1 为什么要安装Python? 1.1.2 下载Python解释器 1.1.3 安装Python解释器 1.1.4 测试是否安装成功 1.1.5 跟大神学高级爬虫安卓逆向引言： 大神薯条老师的高级爬虫安卓逆向教程： 这套爬虫教程会系统讲解爬虫的初级&…...

编程日记 2025/8/17 23:06:39

剖析Mybatis中用到的设计模式

框架对很多设计模式的实现，都并非标准的代码实现，都做了比较多的自我改进。实际上，这就是所谓的灵活应用, 只借鉴不照搬, 根据具体问题针对性地去解决。涉及到Mybatis源码知识和设计模式，这点我之前的博客均有涉及。可以查看我的…...

编程日记 2025/8/22 12:35:08

MySQL 函数（入门版）

目录一、字符串函数 1、常用的字符串函数 2、函数演示 3、具体案例二、数值函数 1、常用的数值函数 2、函数演示 3、具体案例三、日期函数 1、常用的日期函数 2、函数演示 3、具体案例四、流程函数 1、常用的流程函数 2、函数演示 3、具体案例在MySQL中&a…...

编程日记 2025/8/22 8:25:47

d202546

目录一、罗马字符转数字二、二叉树的右视图三、sql-查询结果的质量和占比一、罗马字符转数字首先把两个字符组成一个数字做一下单独判断然后就是单个字符转数字 public int romanToInt(String s) {int sum 0;char[] ch s.toCharArray();int i 0;while(i < ch.len…...

编程日记 2025/8/18 11:34:02

洛谷每日1题-------Day37__P1634 禽兽的传染病

题目背景 mxj 的启发。题目描述禽兽患传染病了。一个禽兽会每轮传染 x 个禽兽。试问 n 轮传染后有多少禽兽被传染？ 输入格式两个非负整数 x 和 n。输出格式一个整数，即被传染的禽兽数。输入输出样例输入 #1复制 10 2 输出 #1复制 121…...

编程日记 2025/8/22 18:34:24

c语言修炼秘籍 - - 禁(进)忌(阶)秘(技)术(巧)【第五式】动态内存管理

c语言修炼秘籍 - - 禁(进)忌(阶)秘(技)术(巧)【第五式】动态内存管理【心法】【第零章】c语言概述【第一章】分支与循环语句【第二章】函数【第三章】数组【第四章】操作符【第五章】指针【第六章】结构体【第七章】const与c语言中一些错误代码【禁忌秘术】【第一式…...

编程日记 2025/8/22 18:32:15

理解进程和线程的概念

在操作系统中，进程和线程都是执行的基本单位，但它们在性质和管理方面有所不同进程定义: 进程是一个正在运行的程序的实例，是操作系统资源分配的基本单位。特点: 独立性：每个进程有其独立的内存空间、数据栈和其他辅助数据。重…...

编程日记 2025/8/22 18:36:18

【项目管理】第2章信息技术发展 --知识点整理

Oracle相关文档，希望互相学习，共同进步风123456789～-CSDN博客（一）知识总览对应：第1章-第5章（二）知识笔记二、信息技术的发展 1. 信息技术及其发展 1）计算机软硬件计算机硬件由电子机械、光电元件等组成的物理装置，提供物质基础给计算机软件运行。软件包括程…...

编程日记 2025/8/19 21:26:44

docker部署rabbitmq

拉取镜像 docker pull rabbitmq:managementmanagement 标签表示包含管理插件，可以通过 Web 界面管理 RabbitMQ 启动容器 docker run --restartalways -d --name rabbitmq \-p 9004:5672 -p 9005:15672 \-e RABBITMQ_DEFAULT_USERrabbitmq \-e RABBITMQ_DEFAULT_P…...

编程日记 2025/8/22 18:36:18

手搓多模态-03 顶层和嵌入层的搭建

声明：本代码非原创，是博主跟着国外大佬的视频教程编写的，本博客主要为记录学习成果所用。我们首先开始编写视觉模型这一部分，这一部分的主要功能是接收一个batch的图像，并将其转化为上下文相关的嵌入向量，…...

编程日记 2025/8/22 18:34:25

计算机系统---UEFI（统一可扩展固件接口）

一、UEFI定义与历史背景 UEFI（Unified Extensible Firmware Interface） 是替代传统BIOS的新一代固件接口标准，由UEFI论坛（前身是Intel的EFI论坛）制定，旨在解决BIOS在现代硬件和操作系统下的局限性。设计…...

编程日记 2025/8/22 18:32:17

2025年渗透测试面试题总结-某四字大厂面试复盘扩展二面（题目+回答）

网络安全领域各种资源，学习文档，以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具，欢迎关注。目录某四字大厂面试复盘二面一、文件上传绕过WAF的15种深度技巧二、SSRF利用与WAF绕过的8种高阶手法 …...

编程日记 2025/8/17 23:22:06

基于BP神经网络的杂草智能识别系统（杂草识别、Python项目）

基于BP神经网络的杂草智能识别系统项目介绍本项目是一个基于PyQt5和BP神经网络的杂草智能识别系统。系统通过图像处理和神经网络技术， 能够识别8种不同的杂草类别。用户可以通过上传图片，系统会自动识别图片中的杂草类别，并显示识别结果和…...

编程日记 2025/8/22 18:34:25

Java的Selenium的特殊元素操作与定位之时间日期控件

分为两种情况: 控件没有限制手动输入，则直接调用sendKeys方法写入时间数据 //时间日期控件处理 chromeDriver.get ("https://www,fliggy,com/?ttidsem.000000736&hlreferidbaidu.082076&route sourceseo"); chromeDriver.findElement (By.xpat…...

编程日记 2025/8/22 18:29:04

深入理解矩阵乘积的导数：以线性回归损失函数为例

深入理解矩阵乘积的导数：以线性回归损失函数为例在机器学习和数据分析领域，矩阵微积分扮演着至关重要的角色。特别是当我们涉及到优化问题，如最小化损失函数时，对矩阵表达式求导变得必不可少。本文将通过一个具体的例子——线性…...

编程日记 2025/8/22 18:30:08

基于大数据的美团外卖数据可视化分析系统

【大数据】基于大数据的美团外卖数据可视化分析系统 （完整系统源码开发笔记详细部署教程）✅ 目录一、项目简介二、项目界面展示三、项目视频展示一、项目简介该系统通过对海量外卖数据的深度挖掘与分析，能够为美团外卖平台提供运营决策支…...

编程日记 2025/8/22 18:32:17

TypeScript 类型系统详解

基础类型 TypeScript 支持丰富的基础数据类型，涵盖number、string、boolean、null、undefined、symbol以及bigint。这些类型为构建可靠的代码提供了基石。数值类型（number）：在 TypeScript 里，所有数字均为浮点数…...

编程日记 2025/8/22 18:29:04

【学Rust写CAD】33 近似 Alpha 混合函数(argb.rs补充方法）

源码 #[inline]pub fn over(self, dst: Argb) -> Argb {let a 256 - self.alpha32();let rb (dst.rb() * a) >> 8;let ag dst.ag() * a;Argb(self.0 (rb & Argb::MASK) | (ag & !Argb::MASK))}源码分析这段代码实现了一个近似 Alpha 混合（“…...

编程日记 2025/8/22 18:22:48

4.3-4.6学习总结 Java：Set系列集合+双列集合+Map

Set系列集合： 元素是唯一的。 HashSet： 哈希值： 如果没有重写hashcode方法和equals方法，那么哈希值是根据地址值计算的。 LinkedHashSet： TreeSet底层为红黑树。红黑树：两个红色节点不能相连。双列集合&…...

编程日记 2025/8/22 18:29:05

深信服护网蓝初面试题

《网安面试指南》https://mp.weixin.qq.com/s/RIVYDmxI9g_TgGrpbdDKtA?token1860256701&langzh_CN 5000篇网安资料库https://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247486065&idx2&snb30ade8200e842743339d428f414475e&chksmc0e4732df793fa3bf39…...

编程日记 2025/8/22 18:29:05

2011-2019年各省地方财政商业服务业等事务支出数据

2011-2019年各省地方财政商业服务业等事务支出数据 1、时间：2007-2019年 2、来源：国家统计局、统计年鉴 3、指标：行政区划代码、地区、年份、地方财政商业服务业等事务支出 4、范围：31省 5、指标说明：地方财政在商…...

编程日记 2025/8/22 18:30:08

InfoSec Prep: OSCP靶场渗透

InfoSec Prep: OSCP InfoSec Prep: OSCP ~ VulnHubInfoSec Prep: OSCP, made by FalconSpy. Download & walkthrough links are available.https://www.vulnhub.com/entry/infosec-prep-oscp,508/ 1，将两台虚拟机网络连接都改为NAT模式 2，攻击机上做…...

编程日记 2025/8/22 18:30:06

【Kubernetes】Kubernetes 如何管理存储？PV 和 PVC 是如何工作的？

在 Kubernetes 中，存储管理是通过 Persistent Volume (PV) 和 Persistent Volume Claim (PVC) 来实现的。它们为容器化应用提供持久化存储，使得应用在重启或重新调度时仍然能够访问数据。 1. 存储管理概述 Kubernetes 的存储管理是基于持久化卷 (Pe…...

编程日记 2025/8/22 18:34:26

CasaOS小主机本地安装1Panel运维面板结合内网穿透移动端远程运维

文章目录前言1. 添加镜像源2. 部署1Panel3. 本地访问测试4. 安装内网穿透工具5. 配置公网地址6. 配置固定公网地址前言小伙伴们，是不是一想到要远程管理服务器就头大如斗？特别是没有公网IP或路由器设置复杂时，简直让人抓狂！但…...

编程日记 2025/8/22 18:24:53

BGP路由协议之属性2

Orgin 起源公认必遵属性起源名称标记描述IGPi如果路由是由始发的 BGP 路由器使用 network 命令注入到 BGP 的，那么该 BGP 路由的 origin 属性为 IGPEGPe如果路由是通过 EGP 学习到的，那么该 BGP 路由的 Origin 属性为 EGPIncomplete?如果路由是通过…...

编程日记 2025/8/19 7:20:44

HttpClient（笔记）

介绍： 发送请求的步骤： 发送get类型的请求： 发送post类型的请求：...

编程日记 2025/8/18 0:23:27

【简历全景认知】简历的历史演变与当代定位：从羊皮卷到算法博弈的艺术

引言：时间维度下的求职凭证。当古埃及工匠在莎草纸上记录自己的技能时，他们不会想到这份"技能清单"会在四千年后演变成LinkedIn上的数字档案。简历作为个人职业身份的载体，其演变史就是一部微观的人力资源配置史。从手写推荐信到ATS系统解析的PDF，每一次形式变…...

编程日记 2025/8/17 23:36:43

ERP系统五大生产模式概述

制造业中，选择合适的生产模式是企业高效运营的关键。以下是ERP系统支持的五大核心生产模式及其特点总结： 1. MTS（按库存生产） - 定义：先生产后销售，基于需求预测提前备货。 - 适用场景：需求稳定、标准化程度高的产品（如日用品、家电）。 - 优点：交货快、生产…...

编程日记 2025/8/17 23:51:47

003 vue生命周期和钩子函数

文章目录 1.Vue实例有一个完整的生命周期，也就是说从开始创建、初始化数据、编译模板、挂载DOM、渲染-更新-渲染、卸载等一系列过程，称之为Vue实例的生命周期 2.钩子函数（监听函数）：Vue实例在完整的生命周期过程中&…...

编程日记 2025/8/17 22:20:11

学透Spring Boot — 016. 魔术师 - Spring MVC Conversion Service 类型转换

本文是我的《学透Spring Boot》专栏的第16篇文章，了解更多请移步我的专栏： Postnull的专栏《学透Spring Boot》目录遇到问题日期格式的转换实现需求创建转换器注册转换器编写Controller 访问测试存在的问题解决问题源码分析总结 …...

编程日记 2025/8/20 2:26:55

Ubuntu 22 Linux上部署DeepSeek R1保姆式操作详解（Xinference方式）

一、安装步骤 1.基础环境安装安装显卡驱动、cuda，根据自己硬件情况查找相应编号，本篇不介绍这部分内容，只给出参考指令，详情请读者自行查阅互联网其它参考资料。 sudo apt install nvidia-utils-565-server sudo apt install…...

编程日记 2025/8/21 18:52:03

C语言查漏补缺:占位符篇

占位符篇 1. 整数类型2. 字符类型3. 浮点数类型4. 指针类型5. 字符串6. 修饰符 1. 整数类型 %d / %i：用于 int（有符号十进制整数）。int num -42; printf("%d", num); // 输出: -42%u：用于 unsigned int（无…...

编程日记 2025/8/17 22:20:03

springcloud现常用的组件都有哪些，如何使用

Spring Cloud是一个用于构建分布式系统的开源框架，它提供了多个常用的组件来简化分布式系统的开发和部署。以下是Spring Cloud中常用的一些组件： Spring Cloud Config：用于集中式管理配置，并提供配置的动态刷新功能。Spring Clou…...

编程日记 2025/8/20 10:22:48

递归型枚举与回溯剪枝初识

相关文章：