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

洛谷题单【算法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 奇怪的电梯 一开始以为深搜肯定没问题&#xff0c;从a点出发&#xff0c;衍生出一个二叉树&#xff0c;遍历所有情况就好了&#xff0c;但是会重复&#xff0c;所以加了一个vis防止重复&#xff0c;但是只拿了64pts&#xff0c;因为有可能某个点并不是最短被到达的&…...

WordPress主题Lolimeow v8.0.1二次元风格支持erphpdown付费下载

WordPress国人原创动漫主题lolimeow免费下载 lolimeow是一款WordPress国人原创主题&#xff0c;风格属于二次元、动漫、可爱萝莉风&#xff0c;带有后台设置&#xff0c;支持会员中心。该主题为免费主题。 1.侧栏/无侧栏切换&#xff01; 2.会员中心&#xff08;配套Erphpdown…...

WTN6xxx系列OTP语音芯片:智能语音解决方案的可靠之选

在智能语音交互领域&#xff0c;唯创知音的WTN6xxx系列OTP语音芯片以其独特的特性成为声音播放提示IC的可靠之选。本文将深入探讨WTN6xxx系列OTP语音芯片的应用优势&#xff0c;展示其在各个方面的卓越性能。 一、低成本、高性能 1.经济实惠&#xff1a; WTN6xxx系列OTP语音芯…...

腾讯云Elasticsearch Service产品体验

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

SQLE 3.0 部署实践

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

爬虫的分类

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

简说vue-router原理

vue-router原理 hash模式 实现原理 改变描点监听描点变化 history模式 实现原理 改变url监听url变化 abstracthash 和 history 模式有什么区别&#xff1f; url 不一样原理不同 其他总结扩展 history 出现404错误 vue-router原理 vue-router是vue项目的重要组成部分&#x…...

什么是 Spring 框架?

Spring 框架是一个开源的、轻量级的企业级应用框架&#xff0c;用于构建 Java 应用程序。它提供了全面的基础设施支持&#xff0c;以简化企业级应用的开发。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 工具&#xff0c;下载安装后&#xff0c;如下图&#xff1a; 2、通过Bugly或友盟等异常记录工具&#xff0c;找到闪退的内存地址和偏移量信息上图是Bugy记录的闪退信息&#xff0c;友盟的参考如下&#xff1a; 关于工具的原理和其他描述&#xff0c…...

分布式解决方案与实战

分布式多线程性能调优 使用多线程优化接口 //下单业务public Object order( long userId){long start System.currentTimeMillis();//方法的开始时间戳&#xff08;ms&#xff09;JSONObject orderInfo remoteService.createOrder(userId);Callable<JSONObject> calla…...

GitHub入门介绍

GitHub是一个基于web的版本控制系统&#xff0c;主要用于代码管理和协作开发。它是开源的&#xff0c;并且提供了一系列的功能&#xff0c;方便开发人员进行版本控制、代码托管和团队协作。 以下是GitHub的一些基本概念和功能&#xff1a; 版本控制&#xff1a;GitHub使用Git作…...

IP与子网掩码之间的关系

子网掩码用于确认IP所在的网段&#xff0c;网络位与子网掩码相匹配 如果有另一台主机想要与这个IP地址进行通信&#xff0c;这时需要看两台主机的IP地址是否处于同一网段&#xff0c;处于同一网段才能相互ping通。 那么怎么判断是否处于同一网段呢&#xff1f;我们就看子网掩…...

文档或书籍扫描为 PDF:ScanPapyrus Crack

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

Clickhouse RoaringBitmap

https://blog.csdn.net/penriver/article/details/119736050 https://juejin.cn/post/7179956435806076988 BitMap适合连续密集的正整数存储&#xff0c;对于稀疏的正整数存储&#xff0c;其性能在很多时候是没办法和int数组相比的&#xff0c;尤其是正整数跨度较大的场景&…...

C语言第四十九弹----模拟使用strcpy函数

使用C语言模拟使用strcpy函数 定义&#xff1a;strcpy 函数是 C 标准库中用于字符串复制的函数。它接受两个参数&#xff0c;第一个参数 dest 是目标字符串的指针&#xff0c;第二个参数 src 是源字符串的指针&#xff0c;函数的功能是将源字符串复制到目标字符串中&#xff0…...

docker搭建maven私库Nexus3

什么是Maven私服&#xff1f; Maven 私服是一种特殊的Maven远程仓库&#xff0c;它是架设在局域网内的仓库服务&#xff0c;用来代理位于外部的远程仓库&#xff08;中央仓库、其他远程公共仓库&#xff09;。 当然也并不是说私服只能建立在局域网&#xff0c;也有很多公司会…...

Java 基础学习(十)包装类、异常

1 包装类 1.1 包装类概述 1.1.1 什么是包装类 在进行类型转换时&#xff0c;有一种特殊的转换&#xff1a;将 int 这样的基本数据类型转换为对象&#xff0c;如下图所示&#xff1a; 所有基本类型都有一个与之对应的类&#xff0c;即包装类&#xff08;wrapper&#xff09;。…...

STM32的基本定时器注意点

本文介绍了STM32基本定时器3个重要的寄存器PSC、ARR、CNT&#xff0c;以及缓冲机制和计数细节。 基本定时器的框图 预分频器寄存器(TIMx_PSC)可以在运行过程中修改它的数值&#xff0c;新的预分频数值将在下一个更新事件时起作用。因为更新事件发生时&#xff0c;会把 TIMx_PS…...

浅谈NLP和大模型的关系

目录 一、什么是NLP 二、NLP的应用举例 三、NLP的Python实现举例 四、NLP和大模型的关系 五、NLP的难点 5.1 内容的有效界定 5.2 消歧和模糊性 5.3 有瑕疵的或不规范的输入 5.4 语言行为与计划 六、研究热点 一、什么是NLP 如果单独说NLP这3个字母&#xff0c;具有两…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

比特币:固若金汤的数字堡垒与它的四道防线

第一道防线&#xff1a;机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”&#xff08;Hashing&#xff09;就是一种军事级的加密术&#xff08;SHA-256&#xff09;&#xff0c;能将信函内容&#xff08;交易细节&#xf…...