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

蓝桥杯杯赛之深度优先搜索优化《1.分成互质组》 《 2.小猫爬山》【dfs】【深度搜索剪枝优化】【搜索顺序】

文章目录

  • 思想
  • 例题
    • 1. 分成互质组
      • 题目链接
      • 题目描述
      • 【解法一】
      • 【解法二】
    • 2. 小猫爬山
      • 题目链接
      • 题目描述
      • 输入样例:
      • 输出样例:
      • 【思路】
      • 【WA代码】
      • 【AC代码】

思想

  1. 本质为两种搜索顺序
  • 枚举当前元素可以放入哪一组
  • 枚举每一组可以放入哪些元素
  1. 操作为两种
  • 放入当前组
  • 新开一个组

例题

1. 分成互质组

题目链接

https://www.acwing.com/problem/content/1120/

题目描述

在这里插入图片描述

【解法一】

枚举每一组可以放哪些元素

#include <iostream>
using namespace std;
const int N = 11;
int g[N][N];
int a[N];
bool st[N];
int n;
int ans = N;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
bool check(int g[], int x, int k) {for(int i = 0; i < k; i ++)if(gcd(g[i], x) > 1)	return false;return true;
}
void dfs(int gu, int gid, int start, int cnt) {if(gu >= ans)	return ;    //剪枝, 若当前分组大于答案,那么不如之前的也没必要枚举了if(cnt == n)	ans = min(ans, gu);bool flag = true;	//从start开始找,是否有元素不能入当前组for(int i = start; i < n; i ++) {if(!st[i] && check(g[gu], a[i], gid)) {st[i] = true;g[gu][gid] = a[i];dfs(gu, gid + 1, i + 1, cnt + 1);//恢复现场st[i] = false;flag = false; }} //操作二:新开数组if(flag) dfs(gu + 1, 0, 0, cnt);
}
int main() {cin >> n;for(int i = 0; i < n; i ++)	cin >> a[i];//当前在第几组,第几个数,从哪个位置开始选,已经选好几个数 dfs(1, 0, 0, 0);	cout << ans; return 0;
}

【解法二】

枚举当前元素可以放入哪个组

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;const int N = 10;
int a[N];
vector<int> g[N];   //互质组
int n;
int ans = N;int gcd(int a, int b){return b?gcd(b, a%b) : a;
}bool check(int c,int x){for(int i=0;i<g[c].size();i++){if(gcd(g[c][i],x)>1) return false;}return true;
}void dfs(int u, int k){ //当前为第u个数, 已开辟的组的个数if(u==n){ans=min(ans,k);return;}//每个元素的方法即 -> 放到当前已经存在的组中  或者  放到新开的组中//操作一:放入已经存在的组中for(int i=0; i < k; i ++){if(check(i, a[u])){g[i].push_back(a[u]);dfs(u + 1, k);g[i].pop_back();}}//可见这里的k代表着的是当前开辟数组的个数//操作二:新开一个组g[k].push_back(a[u]);dfs(u+1, k + 1);g[k].pop_back();
}int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];dfs(0, 0);cout<<ans;return 0;
}

2. 小猫爬山

题目链接

https://www.acwing.com/problem/content/167/

题目描述

在这里插入图片描述

输入样例:

5 1996
1
2
1994
12
29

输出样例:

2

【思路】

第一步很容易会误以为这是一道背包问题,不过看了眼数据范围,容量太大,而n的范围很小,故为一道dfs搜搜问题

这里根据数据范围我们必然需要优化,分析可以优化的点:
在这里插入图片描述

  • ① 要求最小车辆,那么如果我们搜索某种决策时当前的车辆数已经大于ans了,那么必然不是最优解,直接退出即可
  • ② 对于dfs决策时,要想使得决策的分支少点,那么从根开始越少的话,那么必然分支也会更少,想到从此处进行优化的话,那么若是优先考虑重量大的,可以实现,因为在已有的车辆中选择可放入的重量大的可选车辆少

下面展示代码:

【WA代码】

在这里插入图片描述
枚举每一组可以放入哪些元素

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, W;
int w[N];
int g[N][N];
bool st[N];
int ans = N;void dfs(int gu, int ct, int start, int cnt) {if(gu >= ans)	return ;if(cnt == n) {ans = min(ans, gu);return;}bool flag = true;	//判断是否可以放进去当前组//操作一:加入当前组 for(int i = start; i < n; i ++) {if(!st[i] && ct + w[i] <= W) {st[i] = true;dfs(gu, ct + w[i], start + 1, cnt + 1);//恢复现场st[i] = false; flag = false;}}//操作二:新开组if(flag) 	dfs(gu + 1, 0, 0, cnt);}int main() {cin >> n >> W;for(int i = 0; i < n; i ++)	cin >> w[i];	//为了使得决策少点,优化时间,选择先放重量大的sort(w, w + n, greater<int>());//从第gu个组开始,当前在判断第gid个数,已经匹配的数字, 从哪个数开始 dfs(1, 0, 0, 0);cout << ans;return 0;
}

【AC代码】

枚举当前元素可以放入哪些组

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, W;
int w[N];
int sum[N]; //第i辆车的重量
bool st[N];
int ans = N;void dfs(int u, int k) {    //u代表当前遍历的数,k代表当前已有分组数量if(k >= ans)    return;if(u == n)  {// ans = min(ans, k);   //因为有上步条件制约,故不需要minans = k;return;}   //操作一:放入某个已有的车辆for(int i = 0; i < k; i ++) {if(sum[i] + w[u] <= W) {sum[i] += w[u];dfs(u + 1, k);//恢复现场sum[i] -= w[u];}}//操作二: 放不下,新开车辆sum[k] = w[u];dfs(u + 1, k + 1);sum[k] = 0;}int main() {cin >> n >> W;for(int i = 0; i < n; i ++)	cin >> w[i];	//为了使得决策少点,优化时间,选择先放重量大的sort(w, w + n, greater<int>());dfs(0, 0);cout << ans;return 0;
}

相关文章:

蓝桥杯杯赛之深度优先搜索优化《1.分成互质组》 《 2.小猫爬山》【dfs】【深度搜索剪枝优化】【搜索顺序】

文章目录 思想例题1. 分成互质组题目链接题目描述【解法一】【解法二】 2. 小猫爬山题目链接题目描述输入样例&#xff1a;输出样例&#xff1a;【思路】【WA代码】【AC代码】 思想 本质为两种搜索顺序&#xff1a; 枚举当前元素可以放入哪一组枚举每一组可以放入哪些元素 操…...

软件设计原则:依赖倒置

定义 依赖倒置原则&#xff08;Dependency Inversion Principle, DIP&#xff09;是面向对象设计原则之一&#xff0c;其核心是高层模块&#xff08;如业务逻辑&#xff09;不应当依赖于低层模块&#xff08;如具体的数据访问或设备控制实现&#xff09;&#xff0c;而是双方都…...

03-自媒体文章发布

自媒体文章发布 1)自媒体前后端搭建 1.1)后台搭建 ①&#xff1a;资料中找到heima-leadnews-wemedia.zip解压 拷贝到heima-leadnews-service工程下&#xff0c;并指定子模块 执行leadnews-wemedia.sql脚本 添加对应的nacos配置 spring:datasource:driver-class-name: com…...

Oracle中实现一次插入多条数据

一、需求描述 在我们实际的业务场景中&#xff0c;由于单条插入的效率很低&#xff08;每次都需要数据库资源连接关闭的开销&#xff09;&#xff0c;故需要实现一次性插入多条数据&#xff0c;用以提升数据插入的效率&#xff1b; 如下图是常见的单条插入数据&#xff1a; 二…...

【C++入门】关键字、命名空间以及输入输出

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…...

初识MySQL(中篇)

使用语言 MySQL 使用工具 Navicat Premium 16 代码能力快速提升小方法&#xff0c;看完代码自己敲一遍&#xff0c;十分有用 目录 1.SQL语言 1.1 SQL语言组成部分 2.MySQL数据类型 2.1 数值类型 2.2 字符串类型 2.3 日期类型 3.创建数据表 3.1 创建数据表方法1 …...

前端订阅后端推送WebSocket定时任务

0.需求 后端定时向前端看板推送数据&#xff0c;每10秒或者30秒推送一次。 1.前言知识 HTTP协议是一个应用层协议&#xff0c;它的特点是无状态、无连接和单向的。在HTTP协议中&#xff0c;客户端发起请求&#xff0c;服务器则对请求进行响应。这种请求-响应的模式意味着服务器…...

提高机器人系统稳定性:引入阻尼作为共振后的相位超前

在机器人关节中&#xff0c;引入阻尼作为共振后的相位超前&#xff0c;确实是一种提高系统稳定性的有效策略。机器人关节的振动和共振是影响其性能稳定性的关键因素&#xff0c;特别是在进行高速、高精度操作时。阻尼的引入能够显著减少这些不利因素&#xff0c;提升机器人的整…...

深度学习理论基础(三)封装数据集及手写数字识别

目录 前期准备一、制作数据集1. excel表格数据2. 代码 二、手写数字识别1. 下载数据集2. 搭建模型3. 训练网络4. 测试网络5. 保存训练模型6. 导入已经训练好的模型文件7. 完整代码 前期准备 必须使用 3 个 PyTorch 内置的实用工具&#xff08;utils&#xff09;&#xff1a; ⚫…...

vue3+eachrts饼图轮流切换显示高亮数据

<template><div class"charts-box"><div class"charts-instance" ref"chartRef"></div>// 自定义legend 样式<div class"charts-note"><span v-for"(items, index) in data.dataList" cla…...

UTONMOS:AI+Web3+元宇宙数字化“三位一体”将触发经济新爆点

人工智能、元宇宙、Web3&#xff0c;被称为数字化的“三位一体”&#xff0c;如何看待这三大技术所扮演的角色&#xff1f; 3月24日&#xff0c;2024全球开发者先锋大会“数字化的三位一体——人工智能、元宇宙、Web3.0”论坛在上海漕河泾开发区举行&#xff0c;首次提出&…...

开始焦虑了

大家好&#xff0c;我是洋子&#xff0c;25届的暑期实习自从3月份开始招聘有一段时间了&#xff0c;最近接到了几个25届同学的咨询&#xff0c;其中一个学妹印象比较深刻&#xff0c;她的情况如下 个人情况 学历是双非本&#xff0c;计算机专业&#xff0c;学习方向是Java&…...

数据结构和算法:十大排序

排序算法 排序算法用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用&#xff0c;因为有序数据通常能够被更高效地查找、分析和处理。 排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定&#xff0c;如数字大小、字符 ASCII…...

LLaMA-Factory微调(sft)ChatGLM3-6B保姆教程

LLaMA-Factory微调&#xff08;sft&#xff09;ChatGLM3-6B保姆教程 准备 1、下载 下载LLaMA-Factory下载ChatGLM3-6B下载ChatGLM3windows下载CUDA ToolKit 12.1 &#xff08;本人是在windows进行训练的&#xff0c;显卡GTX 1660 Ti&#xff09; CUDA安装完毕后&#xff0c…...

Web安全-浏览器安全策略及跨站脚本攻击与请求伪造漏洞原理

Web安全-浏览器安全策略及跨站脚本攻击与请求伪造漏洞原理 Web服务组件分层概念 静态层 &#xff1a;web前端框架&#xff1a;Bootstrap&#xff0c;jQuery,HTML5框架等&#xff0c;主要存在跨站脚本攻击脚本层&#xff1a;web应用&#xff0c;web开发框架&#xff0c;web服务…...

蓝桥杯B组C++省赛——飞机降落(DFS)

题目连接&#xff1a;https://www.lanqiao.cn/problems/3511/learning/ 思路&#xff1a;由于数据范围很小&#xff0c;所有选择用DFS枚举所有飞机的所有的降落顺序&#xff0c;看哪个顺序可以让所有飞机顺利降落&#xff0c;有的话就算成功方案&#xff0c;输出了“YES”。 …...

Java 中的 Map集合

文章目录 添加和修改元素获取元素检查元素删除元素获取所有键 / 值 / 键值对大小 在 Java 中&#xff0c;Map 接口是 Java 集合框架的一部分&#xff0c;它存储键值对&#xff08;key-value pairs&#xff09;。Map 接口有许多常用的方法&#xff0c;用于添加、删除、获取元素&…...

基于springboot大学生兼职平台管理系统(完整源码+数据库)

一、项目简介 本项目是一套基于springboot大学生兼职平台管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、功…...

C#学生信息管理系统

一、引言 学生信息管理系统是现代学校管理的重要组成部分&#xff0c;它能够有效地管理学生的基本信息、课程信息、成绩信息等&#xff0c;提高学校管理的效率和质量。本文将介绍如何使用SQL Server数据库和C#语言在.NET平台上开发一个学生信息管理系统的课程设计项目。 二、项…...

双机 Cartogtapher 建图文件配置

双机cartogtapher建图 最近在做硕士毕设的最后一个实验&#xff0c;其中涉及到多机建图&#xff0c;经过调研最终采用cartographer建图算法&#xff0c;其中配置多机建图的文件有些麻烦&#xff0c;特此博客以记录 非常感谢我的同门 ”叶少“ 山上的稻草人-CSDN博客的帮助&am…...

VMware提示 该虚拟机似乎正在使用中,如何解决?

VMware提示 该虚拟机似乎正在使用中,如何解决&#xff1f; 问题描述解决方法1.找到安装VMware的文件目录2.在VMware目录下.lck后缀的文件夹删除或重命名3.运行VMware 问题描述 该虚拟机似乎正在使用中。 如果该虚拟机未在使用&#xff0c;请按“获取所有权(T)”按钮获取它的所…...

阿里云短信服务业务

一、了解阿里云用户权限操作 1.注册账号、实名认证&#xff1b; 2.使用AccessKey 步骤一 点击头像&#xff0c;权限安全的AccessKey 步骤二 设置子用户AccessKey 步骤三 添加用户组和用户 步骤四 添加用户组记得绑定短信服务权限 步骤五 添加用户记得勾选openApi访问 添加…...

ElasticSearch的DSL查询

ElasticSearch的DSL查询 准备工作 创建测试方法&#xff0c;初始化测试结构。 import org.apache.http.HttpHost; import org.apache.lucene.search.TotalHits; import org.elasticsearch.action.search.SearchRequest; import org.elasticsearch.action.search.SearchRespo…...

每天定时杀spark进程

##编写shell脚本 #!/bin/bash arr(“zhangsan” “lisi” “wangwu”) for i in “${arr[]}” do processps -ef|grep ${i}| grep -v "grep"| awk {print $2} kill -9 ${process} done ##每日定时杀手动启动的进程 0 19 * * * cd /kill_process && sh kil…...

win10 安装kubectl,配置config连接k8s集群

安装kubectl 按照官方文档安装&#xff1a;https://kubernetes.io/docs/tasks/tools/install-kubectl-windows/ curl安装 &#xff08;1&#xff09;下载curl安装压缩包: curl for Windows &#xff08;2&#xff09;配置环境变量&#xff1a; 用户变量&#xff1a; Path变…...

Calico IPIP和BGP TOR的数据包走向

IPIP Mesh全网互联 文字描述 APOD eth0 10.7.75.132 -----> APOD 网关 -----> A宿主机 cali76174826315网卡 -----> Atunl0 10.7.75.128 封装 ----> Aeth0 10.120.181.20 -----> 通过网关 10.120.181.254 -----> 下一跳 BNODE eth0 10.120.179.8 解封装 --…...

静态成员主要用于提供与类本身相关的功能或数据,有什么应用场景

静态成员&#xff08;包括静态方法和静态属性&#xff09;在JavaScript中常用于多种应用场景&#xff0c;它们为类提供了与类本身直接相关而不是与实例相关的功能或数据。以下是一些常见的应用场景&#xff1a; 工厂方法 静态方法可以作为工厂方法&#xff0c;用于创建类的实…...

在线考试|基于Springboot的在线考试管理系统设计与实现(源码+数据库+文档)

在线考试管理系统目录 目录 基于Springboot的在线考试管理系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、前台&#xff1a; 2、后台 管理员功能 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主…...

C语言-----数据在内存中的存储(1)

1.整数在内存中的存储 我们之前就了解过整数的二进制写法分别有3种&#xff0c;分别为原码&#xff0c;反码&#xff0c;补码。整型在内存中存储的是补码。 原码&#xff0c;反码&#xff0c;补码都有自己的符号位和数值位&#xff0c;符号位为1时&#xff0c;则表示负数&…...

Ribbon有哪些负载均衡策略

负载均衡类都实现了IRule接口。 RandomRule&#xff1a;随机的选用一个实例 RoundRobinRule&#xff1a;轮询的使用实例 RetryRule&#xff1a;在轮询的基础上加了一个错误重试机制&#xff0c;在deadline时间内会不断的重试 WeightResponeTimeRule&#xff1a;根据权重去做…...

网站有二级域名做竞价/手游推广渠道和推广方式

MRT(MODIS Reprojection Tool)简介&#xff1a;MODIS的全称为中分辨率成像光谱仪(Moderate-Resolution Imaging Spectroradiometer)&#xff0c;是搭载在Terra和Aqua卫星上的一个重要的传感器。MRT是一种针对MODIS数据的处理工具。它可以帮助用户把MODIS影像重新投影到更为标准…...

怎么创建网站平台赚钱/网络营销专业是做什么的

目录 一、方法的概念及使用 1、什么是方法(method) 2、方法定义 3、方法调用的执行过程 4、实参和形参的关系 二、方法重载 1、为什么需要方法重载 2、方法重载概念 3、方法签名 三、递归 1、递归的概念 2、递归执行过程分析 3、递归练习 一、方法的概念及使用 1、…...

只用html5可以做网站吗/aso优化软件

目录中的文件显示ls -l长文件输出ls -a显示所有文件ls -al长文件格式显示所有文件ls -alh显示所有文件&#xff0c;显示文件大小ls -alhs 显示所有文件&#xff0c;显示文件大小&#xff0c;按字母先后顺序排序&#xff0c;正序ls -alhsr 显示所有文件&#xff0c;显示文件大小…...

cms系统哪个好用/湖南百度seo

当我们需要从一个对象里面&#xff0c;每次获取不同属性,那么我们是不是要 单独写N个方法呢&#xff1f; 例如&#xff1a;class 有 下发标识、删除标识、类型标识等等 我们不同的场景只需要查询这个类的一个标识&#xff0c;那么是不是每个查询标识都搞一个方法呢&#xff1…...

网站建设 汇卓/淘宝推广怎么做

转载https://blog.csdn.net/gesanghua601/article/details/85131156 最近经常利用wireshark抓包&#xff0c;查看数据包的数据&#xff0c;遇到一二问题总结下&#xff0c;也分享给遇到同样问题的小伙伴儿~~ 抓包rtp难以直观看到裸码流格式数据&#xff0c;进而难以判断码流类…...

永州城乡建设网站/宁德市市长

Jackson中的ValueNode的所有子类(JSON库)具有用于获取基础值对象的不同方法,例如IntNode有getIntValue,BooleanNode有getBooleanValue等等.为什么没有调用简单的getValue的泛型/多态方法只返回一个Object,并且该Object是Integer或Boolean等,根据调用该方法的节点类型&#xff1…...