备战蓝桥杯---搜索(剪枝)
何为剪枝,就是减少搜索树的大小。
它有什么作用呢?
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博客...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
