洛谷题单【算法1-7】搜索
P1135 奇怪的电梯
一开始以为深搜肯定没问题,从a点出发,衍生出一个二叉树,遍历所有情况就好了,但是会重复,所以加了一个vis防止重复,但是只拿了64pts,因为有可能某个点并不是最短被到达的,但是已经被标记上了vis,所以如果要遍历这一个整个合法的最短二叉树,应该要用BFS。
DFS的话因为是一直在搜,所以加一个dis数组,更新每个点的最短次数。
#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;const int N=200+5;
int n,k[N],a,b,ans=INT_MAX,dis[N];void dfs(int x,int step){if(x<1 or x>n or step>=dis[x] or step>=ans)return;if(x==b)return ans=step,void();dis[x]=step;dfs(x+k[x],step+1);dfs(x-k[x],step+1);
}void solve(){cin>>n>>a>>b;per(i,1,n)cin>>k[i],dis[i]=INT_MAX;dfs(a,0);ans=ans==INT_MAX?-1:ans;cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}
P2895 [USACO08FEB] Meteor Shower S
坑也太多了,下面列举一下坑,题不是很难,就模拟+BFS。
1. 流星只会在0<=x<=300,0<=y<=300出现,但是没说人不能走出这个范围,人在第一象限移动
2. 多个流星降落的点,要取最早的那一个
3. 每个点最多被走一次,如果返回来走第二次,肯定不会更优,重复走还会MLE
4. 陨石还有2降落的时候才能走那个点,走上去1,走出去0,如果是1走进去就被砸了
#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define SAFE INT_MAX
#define se second
#define endl '\n'
using namespace std;
using pii=pair<int,int>;const int N=300+5;
int m,x,y,t,a[N][N],step[N][N],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},cnt=1,precnt;
bool vis[N][N];bool isingrid(pii x){//并不需要<=300return x.fr>=0 and x.se>=0 ;
}bool safe(pii x){//输入的时候已经延伸陨石了,所以判断的时候不需要延伸if(a[x.fr][x.se]!=SAFE)return false;else return true;
}void ans(pii x){cout<<step[x.fr][x.se]<<endl;
}void noans(){cout<<-1<<endl;
}void updateMeteor(){//更新陨石,所有不安全的点均有陨石,时间-1per(i,0,304)per(j,0,304)if(a[i][j]!=SAFE)a[i][j]--;
}void solve(){per(i,0,304)per(j,0,304)a[i][j]=SAFE;//标记为安全cin>>m;per(i,1,m){cin>>x>>y>>t;a[x][y]=min(a[x][y],t);//有陨石就不安全,标记一下降落时间,取最早时间per(j,0,3){//四个方向都标记pii nxt={x+dx[j],y+dy[j]};if(isingrid(nxt)){//范围是否合法a[nxt.fr][nxt.se]=min(a[nxt.fr][nxt.se],t);}}}queue<pii>q;q.push({0,0});while(!q.empty()){pii now=q.front();q.pop();cnt--;vis[now.fr][now.se]=true;if(safe(now))return ans(now);//当前点安全,输出答案per(i,0,3){pii nxt={now.fr+dx[i],now.se+dy[i]};if(isingrid(nxt) and a[nxt.fr][nxt.se]>=2 and !vis[nxt.fr][nxt.se]){q.push(nxt),precnt++;//记录一下进队的数量step[nxt.fr][nxt.se]=step[now.fr][now.se]+1;vis[nxt.fr][nxt.se]=true;//标记一下被使用过了,不要重复走,不然会MLE}}if(cnt==0){//若每一层遍历cnt都用完了,则说明要更新陨石降落时间cnt=precnt;precnt=0;updateMeteor();}}return noans();//无路可走,没有答案
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}
相关文章:
洛谷题单【算法1-7】搜索
P1135 奇怪的电梯 一开始以为深搜肯定没问题,从a点出发,衍生出一个二叉树,遍历所有情况就好了,但是会重复,所以加了一个vis防止重复,但是只拿了64pts,因为有可能某个点并不是最短被到达的&…...

WordPress主题Lolimeow v8.0.1二次元风格支持erphpdown付费下载
WordPress国人原创动漫主题lolimeow免费下载 lolimeow是一款WordPress国人原创主题,风格属于二次元、动漫、可爱萝莉风,带有后台设置,支持会员中心。该主题为免费主题。 1.侧栏/无侧栏切换! 2.会员中心(配套Erphpdown…...
WTN6xxx系列OTP语音芯片:智能语音解决方案的可靠之选
在智能语音交互领域,唯创知音的WTN6xxx系列OTP语音芯片以其独特的特性成为声音播放提示IC的可靠之选。本文将深入探讨WTN6xxx系列OTP语音芯片的应用优势,展示其在各个方面的卓越性能。 一、低成本、高性能 1.经济实惠: WTN6xxx系列OTP语音芯…...

腾讯云Elasticsearch Service产品体验
基本介绍 产品概述 腾讯云 Elasticsearch Service(ES)是云端全托管海量数据检索分析服务,拥有高性能自研内核,集成X-Pack。ES 支持通过自治索引、存算分离、集群巡检等特性轻松管理集群,也支持免运维、自动弹性、按需…...

SQLE 3.0 部署实践
来自 1024 活动的投稿系列 第一篇《SQLE 3.0 部署实践》 . 作者:张昇,河北东软软件有限公司高级软件工程师,腾讯云社区作者。 爱可生开源社区出品,原创内容未经授权不得随意使用,转载请联系小编并注明来源。 本文共 32…...

爬虫的分类
爬虫的分类 网络爬虫按照系统结构和实现技术,大致可分为4类,即通用网络爬虫、聚焦网络爬虫、增量网络爬虫和深层次网络爬虫。 1.通用网络爬虫:搜索引擎的爬虫 比如用户在百度搜索引擎上检索对应关键词时,百度将对关键词进行分析…...

简说vue-router原理
vue-router原理 hash模式 实现原理 改变描点监听描点变化 history模式 实现原理 改变url监听url变化 abstracthash 和 history 模式有什么区别? url 不一样原理不同 其他总结扩展 history 出现404错误 vue-router原理 vue-router是vue项目的重要组成部分&#x…...
什么是 Spring 框架?
Spring 框架是一个开源的、轻量级的企业级应用框架,用于构建 Java 应用程序。它提供了全面的基础设施支持,以简化企业级应用的开发。Spring 的核心目标是通过促进良好的设计原则和编程习惯来提高 Java 开发人员的效率和系统的可维护性。 Spring 框架的主…...

Vue2.x源码:new Vue()做了啥
例子1new Vue做了啥?new Vue做了啥,源码解析 initMixin函数 初始化 – 初始化Vue实例的配置initLifecycle函数 – 初始化生命周期钩子函数initEvents – 初始化事件系统初始化渲染 initRender初始化inject选项 例子1 <div id"app"><div class"home&…...

iOS 借助DSYMTools工具定位到闪退的具体行数和方法名
1、下载 dSYMTools-master 工具,下载安装后,如下图: 2、通过Bugly或友盟等异常记录工具,找到闪退的内存地址和偏移量信息上图是Bugy记录的闪退信息,友盟的参考如下: 关于工具的原理和其他描述,…...

分布式解决方案与实战
分布式多线程性能调优 使用多线程优化接口 //下单业务public Object order( long userId){long start System.currentTimeMillis();//方法的开始时间戳(ms)JSONObject orderInfo remoteService.createOrder(userId);Callable<JSONObject> calla…...
GitHub入门介绍
GitHub是一个基于web的版本控制系统,主要用于代码管理和协作开发。它是开源的,并且提供了一系列的功能,方便开发人员进行版本控制、代码托管和团队协作。 以下是GitHub的一些基本概念和功能: 版本控制:GitHub使用Git作…...
IP与子网掩码之间的关系
子网掩码用于确认IP所在的网段,网络位与子网掩码相匹配 如果有另一台主机想要与这个IP地址进行通信,这时需要看两台主机的IP地址是否处于同一网段,处于同一网段才能相互ping通。 那么怎么判断是否处于同一网段呢?我们就看子网掩…...

文档或书籍扫描为 PDF:ScanPapyrus Crack
ScanPapyrus 可让您快速轻松地将文档或书籍扫描为 PDF,批处理模式使扫描过程快速高效,自动处理书籍并将其拆分为单独的页面 用于快速扫描文档、书籍或打印照片的扫描仪软件 快速扫描文档 使用此扫描仪软件,您无需在扫描仪和计算机之间来回移动…...

Clickhouse RoaringBitmap
https://blog.csdn.net/penriver/article/details/119736050 https://juejin.cn/post/7179956435806076988 BitMap适合连续密集的正整数存储,对于稀疏的正整数存储,其性能在很多时候是没办法和int数组相比的,尤其是正整数跨度较大的场景&…...
C语言第四十九弹----模拟使用strcpy函数
使用C语言模拟使用strcpy函数 定义:strcpy 函数是 C 标准库中用于字符串复制的函数。它接受两个参数,第一个参数 dest 是目标字符串的指针,第二个参数 src 是源字符串的指针,函数的功能是将源字符串复制到目标字符串中࿰…...

docker搭建maven私库Nexus3
什么是Maven私服? Maven 私服是一种特殊的Maven远程仓库,它是架设在局域网内的仓库服务,用来代理位于外部的远程仓库(中央仓库、其他远程公共仓库)。 当然也并不是说私服只能建立在局域网,也有很多公司会…...

Java 基础学习(十)包装类、异常
1 包装类 1.1 包装类概述 1.1.1 什么是包装类 在进行类型转换时,有一种特殊的转换:将 int 这样的基本数据类型转换为对象,如下图所示: 所有基本类型都有一个与之对应的类,即包装类(wrapper)。…...

STM32的基本定时器注意点
本文介绍了STM32基本定时器3个重要的寄存器PSC、ARR、CNT,以及缓冲机制和计数细节。 基本定时器的框图 预分频器寄存器(TIMx_PSC)可以在运行过程中修改它的数值,新的预分频数值将在下一个更新事件时起作用。因为更新事件发生时,会把 TIMx_PS…...
浅谈NLP和大模型的关系
目录 一、什么是NLP 二、NLP的应用举例 三、NLP的Python实现举例 四、NLP和大模型的关系 五、NLP的难点 5.1 内容的有效界定 5.2 消歧和模糊性 5.3 有瑕疵的或不规范的输入 5.4 语言行为与计划 六、研究热点 一、什么是NLP 如果单独说NLP这3个字母,具有两…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...