备战蓝桥杯---搜索(剪枝)
何为剪枝,就是减少搜索树的大小。
它有什么作用呢?
1.改变搜索顺序。
2.最优化剪枝。
3.可行性剪枝。

首先,单纯的广搜是无法实现的,因为它存在来回跳的情况来拖时间。
于是我们可以用DFS,那我们如何剪枝呢?
1.已经超时了还没到------舍弃
2.沿最快的路径(忽视障碍物)仍无法在规定时间到----舍弃
3.我们用x,y计算出两者的距离(不考虑障碍物),我们考虑反悔的时间,它是反悔后到的地方时间+偶数(有来必有回),就算有障碍物,要到目标肯定是两者的距离+返回时间,于是我们可以用这奇偶性与T判断,不同就删。
4.在此,我们可以确定,我们可以先BFS求最小+奇偶性判断即可。
让我们看另外一道:

下面是分析:
1.我们可以先sort,从小到大排,遇到正确的就退出。
2.参考组合的题,我们可以固定同一个木棒上的组成从大到小。
3.我们应该先放大的,并且从左开始(因为从小开始的话枚举了很多多会被最长的判断掉,比较严谨的可以看看上次写的数独问题)
4.结尾木棒如果错,则不是它的问题(我们要替代只能用跟小的组合,显然不划算)
5.开头木棒如果错,则是上一根木棒的问题(因为这木棒迟早要用,如果它错了,其他的木棒也不会对)
6.一个木棒不行,那么和他长度一样的也不可以。
因此,我们可以用上述规则剪枝。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[100],sum;
int b[100];
bool cmp(int a,int b){return a>b;
}//nxt剩下的棍子,len;changdu;chan:shenxia changdu
int q[1000][100];
int dfs(int nxt,int len,int chan,int pos){if(nxt==0&&chan==0) return 1;if(chan==0){chan=len;nxt--;pos=0;}for(int i=pos+1;i<=n;i++){if(b[i]!=0) continue;if(a[i]>chan) continue;if(q[chan][i]==-1) continue;b[i]=1;if(dfs(nxt,len,chan-a[i],i)==1) return 1;q[chan][i]==-1;b[i]=0;if(chan==len||chan==a[i]) return 0;while(a[i+1]==a[i]) i++;}return 0;
}
int main(){cin>>n;int y;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}sort(a+1,a+n+1,cmp);for(int i=1;i<=3000;i++){if(sum%i!=0) continue;y=i;int u=sum/i;if(dfs(u-1,i,i,0)==1) break;}cout<<y;
}
再来一道:

下面是分析:

下面再对几个剪枝分析一下:
从m层dep层:
对于每一层的R 另h=1---->
同理:
注意:枚举r,h时要从大到小
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,_s[23],_v[23],min1=1000000;
void dfs(int r,int h,int c,int v,int s){if(c==m){if(v==n) min1=min(min1,s);return ;}if(v+_v[c]>n) return;if(s+_s[c]>min1) return;if(2*(n-v)/r+s>min1) return;for(int i=min(r-1,(int)sqrt(n-v));i>=m-c;i--){if(c==0) s=i*i;for(int j=min(h-1,(n-v)/(i*i));j>=m-c;j--){dfs(i,j,c+1,v+i*i*j,s+2*i*j);}}
}
int main(){cin>>n>>m;for(int i=m;i>=0;i--) _s[i]=_s[i+1]+2*(m-i)*(m-i);for(int i=m;i>=0;i--) _v[i]=_v[i+1]+(m-i)*(m-i)*(m-i);dfs(n,n,0,0,0);if(min1==1000000) cout<<0;else cout<<min1;
}
相关文章:
备战蓝桥杯---搜索(剪枝)
何为剪枝,就是减少搜索树的大小。 它有什么作用呢? 1.改变搜索顺序。 2.最优化剪枝。 3.可行性剪枝。 首先,单纯的广搜是无法实现的,因为它存在来回跳的情况来拖时间。 于是我们可以用DFS,那我们如何剪枝呢&#…...
ResizeObserver的使用
这篇说下ResizeObserver API。ResizeObserver接口监视 Element 内容盒或边框盒或者 SVGElement 边界尺寸的变化。 ResizeObserver避免了通过回调函数调整大小时,通常创建的无限回调循环和循环依赖项。它只能通过在后续的帧中处理 DOM 中更深层次的元素来做到这一点…...
CleanMyMac X 4.14.7帮您安全清理Mac系统垃圾
CleanMyMac X 4.14.7是一款强大的 Mac 清理、加速工具和健康卫士,可以让您的 Mac 再次恢复巅峰性能。 移除大型和旧文件、卸载应用,并删除浪费磁盘空间的无用数据。 5倍 更多可用磁盘空间 CleanMyMac X 4.14.7帮您安全清理Mac系统垃圾 CleanMyMac X 4.14.7一键深度扫描mac系统…...
C语言实现memcpy、memmove库函数
目录 引言一、库函数介绍二、库函数详解三、源码实现1.memcpy源码实现2.memmove源码实现 四、测试1.memcpy函数2.memmove函数 五、源码1.memcpy源码2.memmove源码 六、参考文献 引言 关于memcpy和memmove这两个函数,不论是算法竞赛还是找工作面试笔试,对…...
MySQL数据库④_表的约束(主键_自增长_唯一键_外键等)
目录 1. 约束概念和常见的约束 2. 空属性null/not null 2. 默认值default 3. 列描述comment 4. 自动填充zerofill 5. 主键primary key 5.1 主键 5.2 复合主键 6. 自增长auto_increment 7. 唯一键unique key 8. 外键forei…...
SpringBoot过滤器获取请求的参数
一、背景 在项目开发过程中,需要对于某些接口统一处理。 这时候就需要获取请求的报文,再对获取的报文进行统一处理。 二、了解过滤器 首先了解一下过滤器拦截器的区别: JAVA中的拦截器、过滤器:https://blog.csdn.net/qq_38254…...
幻兽帕鲁mac可以玩吗?
《幻兽帕鲁》(英文:Palworld)是一款近期在 Steam 爆红的动作冒险生存游戏,游戏设置在一个居住着「帕鲁」的开放世界中,玩家可以战斗并捕捉帕鲁,也能用它们来建造基地、骑乘和战斗。 不过目前《幻兽帕鲁》仅…...
webstorm、vscode、HBuilder配置eslint检查
你们好,我是金金金。 场景 每个人写的代码都有自己所属的风格,所以项目中统一代码风格特别重要,新开的项目中如何快速配置ESLint呢? 安装 npm install --save-dev eslint ----安装eslintnpm install --save-dev eslint-plugin-vu…...
大数据知识图谱之深度学习——基于BERT+LSTM+CRF深度学习识别模型医疗知识图谱问答可视化系统
文章目录 大数据知识图谱之深度学习——基于BERTLSTMCRF深度学习识别模型医疗知识图谱问答可视化系统一、项目概述二、系统实现基本流程三、项目工具所用的版本号四、所需要软件的安装和使用五、开发技术简介Django技术介绍Neo4j数据库Bootstrap4框架Echarts简介Navicat Premiu…...
年底个人总结
年底个人总结 前言:又到了年底,在游戏行业工作了接近10年,想想也应该把自己做过的东西做一个总结。 从14年在北京毕业,懵懂的我在机缘巧合下遇到了陈g,我行业的领路人,在他的带领下我进入到了游戏行业。 当…...
jsp教材管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 JSP 教材管理系统是一套完善的java web信息管理系统,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发,数据库为Mysql5.0&…...
SpringBoot:配置相关知识点
SpringBoot:多环境配置 配置知识点demo:点击查看LearnSpringBoot02 点击查看更多的SpringBoot教程 一、SpringBootApplication SpringBootApplication 来标注一个主程序类,说明这是一个Spring Boot应用,运行这个类的main方法来…...
在线JSON转SQL工具
在线JSON转SQL - BTool在线工具软件,为开发者提供方便。在线JSON转SQL工具可以将JSON文件中的数据或者JSON对象转换为SQL插入语句,方便用户将数据导入到数据库中。用户可以通过简单的界面上传JSON文件,或者文本框输入,点击JSON转S…...
网络安全大赛
网络安全大赛 网络安全大赛的类型有很多,比赛类型也参差不齐,这里以国内的CTF网络安全大赛里面著名的的XCTF和强国杯来介绍,国外的话用DenCon CTF和Pwn2Own来举例 CTF CTF起源于1996年DEFCON全球黑客大会,以代替之前黑客们通过互相…...
phpMyAdmin 未授权Getshell
前言 做渗透测试的时候偶然发现,phpmyadmin少见的打法,以下就用靶场进行演示了。 0x01漏洞发现 环境搭建使用metasploitable2,可在网上搜索下载,搭建很简单这里不多说了。 发现phpmyadmin,如果这个时候无法登陆,且也…...
PHP实现DESede/ECB/PKCS5Padding加密算法兼容Java SHA1PRNG
这里写自定义目录标题 背景JAVA代码解决思路PHP解密 背景 公司PHP开发对接一个Java项目接口,接口返回数据有用DESede/ECB/PKCS5Padding加密,并且key也使用了SHA1PRNG加密了,网上找了各种办法都不能解密,耗了一两天的时间…...
亚马逊认证考试系列 - 知识点 - 安全组介绍
第一部分:AWS简介 Amazon Web Services(AWS)是全球领先的云计算服务提供商,为个人、企业和政府机构提供广泛的云服务解决方案。AWS的服务包括计算、存储、数据库、分析、机器学习、人工智能、物联网、安全和企业应用等领域。AW…...
【Golang】exec.command命令日志输出示例
背景 为了输出执行命令的日志,主要是执行时间很长,而且分批输出日志的命令。 代码 func Execute(){command : exec.Command("执行命令")// 隐藏黑色窗口command.SysProcAttr &syscall.SysProcAttr{CreationFlags: 0x08000000}// 输出日…...
Dijkstra算法(求最短路)
简介: 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。 特点: 迪杰斯特拉算法采用的是一种贪心策略&a…...
ipcf 核间通讯
S32G2汽车网关开发(四):IPCF通信_s32g 车载网关 精典-CSDN博客 Linux ARM平台开发系列讲解(IPCF异核通信) 2.11.3 IPCF异核通信驱动编译及其测试-CSDN博客...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
