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

2024icpc(Ⅱ)网络赛补题E

E. Escape

在这里插入图片描述

思路:

可以看成 Sneaker 和杀戮机器人都不能在原地停留,然后杀戮机器人有个活动范围限制。如果 Sneaker 和杀戮机器人可以在原地停留,那么 Sneaker 到达一个点肯定会尽可能早,而且时间必须比杀戮机器人到达这个点短。那么预处理一下每个点最早什么时候会被杀戮机器人到达,然后在这个基础上处理出1 ∼n 的最短路即可。

由于每个机器每个时刻都不会停。我们需要分奇数和偶数时刻,来记录它们会出现的位置。

我们把点拆分为i,i+n两个点做记录。

先预处理bfs,记录所有机器人的可达点。

再跑一遍bfs,计算从起点到终点,需要的最短路径。单组数据时间复杂度 O(n + m)。

代码:

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 5;
const int mod = 998244353;
#define ll long long
const int maxn = 1000010;
#define inf 2000000000int n, m, d;
vector<int> g[maxn];
int k;
int dis[maxn];
int pre[maxn];
int dis2[maxn];
int u, v;
bool vis[maxn];void solve()
{scanf("%lld%lld%lld", &n, &m, &d);// initfor (int i = 0; i <= n; ++i){g[i].clear();vis[i] = vis[i + n] = 0;pre[i] = pre[i + n] = 0;dis[i] = dis[i + n] = inf;dis2[i] = dis2[i + n] = inf;}// build graghfor (int i = 1; i <= m; ++i){scanf("%lld%lld", &u, &v);--u, --v; // 点下标偏移到[0,n-1]g[u].push_back(v);g[v].push_back(u);}// cal dis2.scanf("%lld", &k);queue<int> q;for (int i = 1; i <= k; ++i){scanf("%lld", &u);--u; // 点下标偏移到[0,n-1]q.push(u);vis[u] = 1;dis2[u] = 0;}while (!q.empty()){u = q.front();q.pop();int f = u / n; // 偶数/奇数时刻int x = u % n; // 原始点if (dis2[u] == d){ // 超出范围continue;}for (auto v : g[x]){int y = v + n * (!f); // 下一个点if (!vis[y] && dis2[y] > dis2[u] + 1){dis2[y] = dis2[u] + 1;q.push(y);vis[y] = 1;}}}// cal dis.for (int i = 0; i <= 2 * n; ++i){vis[i] = 0;}pre[0] = -1; // 记录位置,便于输出答案dis[0] = 0;q.push(0);vis[0] = 1;while (!q.empty()){ // bfs过程同上,不赘述u = q.front();q.pop();int f = u / n;int x = u % n;for (auto v : g[x]){int y = v + n * (!f);if (dis[y] <= dis[u] + 1){continue;}if (dis[u] + 1 >= dis2[y]){continue;}dis[y] = dis[u] + 1;pre[y] = u;q.push(y);vis[y] = 1;}}if (!vis[n - 1] && !vis[2 * n - 1]){ //printf("-1\n");return;}int ed = dis[n - 1] < dis[2 * n - 1] ? n - 1 : 2 * n - 1;printf("%lld\n", dis[ed]);vector<int> res;while (ed != -1){res.push_back(ed);ed = pre[ed];}reverse(res.begin(), res.end());for (auto x : res){// 这里 x % n 求出原始点,// +1是为了复位,偏移到 [1,n]printf("%lld ", x % n + 1);}printf("\n");
}signed main()
{// std::ios::sync_with_stdio(0);// cin.tie(0);// cout.tie(0);int t = 1;scanf("%lld", &t);while (t--){solve();}return 0;
}

相关文章:

2024icpc(Ⅱ)网络赛补题E

E. Escape 思路&#xff1a; 可以看成 Sneaker 和杀戮机器人都不能在原地停留&#xff0c;然后杀戮机器人有个活动范围限制。如果 Sneaker 和杀戮机器人可以在原地停留&#xff0c;那么 Sneaker 到达一个点肯定会尽可能早&#xff0c;而且时间必须比杀戮机器人到达这个点短。那…...

mac怎么设置ip地址映射

最近开发的项目分为了两种版本&#xff0c;一个自己用的&#xff0c;一个是卖出去的。 卖出的域名是和自己的不一样的&#xff0c;系统中有一些功能是只有卖出去的版本有的&#xff0c;但我们开发完之后还得测试&#xff0c;那就需要给自己的电脑配置一个IP地址映射了&#xf…...

StringReader 使用 JAXB自动将 XML 数据映射到 Java 对象

import javax.xml.bind.JAXBContext; import javax.xml.bind.JAXBException; import javax.xml.bind.Unmarshaller; import java.io.StringReader; public class JAXBExample { public static void main(String[] args) { try { // 假设这是从某处获取的XML字符串 S…...

【系统架构设计师】专题:系统分析和设计

文章目录 一、处理流程设计1.1 流程表示工具1.2 业务流程重组BPR1.3 业务流程管理BPM二、系统设计三、人机界面设计四、结构化方法4.1 结构化分析(Structured Analysis,SA)。4.2 结构化设计(Structured Design,SD)。4.3 结构化编程(Structured Programming,SP)。4.4 数据库设…...

Lambda表达式(Java)

1.Lambda表达式 Lambda是一个匿名函数&#xff0c;我们可以将Lambda表达式理解为一段可以传递的代码&#xff08;将代码像数据一样传递&#xff09;。 “->”&#xff08;Lambda操作符&#xff09;左边&#xff1a;Lambda表达式的所有参数。右边&#xff1a;Lambda体&#x…...

不同的子序列

题目 给定一个字符串 s 和一个字符串 t &#xff0c;计算在 s 的子序列中 t 出现的个数。 字符串的一个 子序列 是指&#xff0c;通过删除一些&#xff08;也可以不删除&#xff09;字符且不干扰剩余字符相对位置所组成的新字符串。&#xff08;例如&#xff0c;“ACE” 是 “…...

CI24R1——精简版Si24R1,高性价比替代XN297开发资料

CI24R1为了减低用户的开发时间&#xff0c;将2.4G芯片开发出2.4G小模块&#xff0c;用户直接贴片调试&#xff0c;大大降低了开发时间跟生产工序。广泛应用在灯控、鼠标、玩具等智能物联网产品。 CI24R1小模块&#xff08;内置天线&#xff09; 是 2.4GHz 模块。该模块核心处理…...

MySQL递归查询笔记

目录 一、创建表结构和插入数据 二、查询所有子节点 三、查询所有父节点 四、查询指定节点的根节点 五、查询所有兄弟节点&#xff08;同级节点&#xff09; 六、获取祖先节点及其所有子节点 七、查询每个节点之间的层级关系 八、查询指定节点之间的层级关系 一、创建表…...

java中的位运算

位运算是对整数的二进制位进行操作的一种运算。在java中long, int, short, char和byte类型都可以使用位运算。 位运算的过程如下&#xff1a;首先将十进制整数转换成二进制表示形式&#xff0c;然后将位运算符应用于每个二进制数位&#xff0c;并计算结果。最后&#xff0c;将…...

llamafactory0.9.0微调qwen2vl

LLaMA-Factory/data/README_zh.md at main hiyouga/LLaMA-Factory GitHubEfficiently Fine-Tune 100+ LLMs in WebUI (ACL 2024) - LLaMA-Factory/data/README_zh.md at main hiyouga/LLaMA-Factoryhttps://github.com/hiyouga/LLaMA-Factory/blob/main...

Electron 隐藏顶部菜单

隐藏前&#xff1a; 隐藏后&#xff1a; 具体设置代码&#xff1a; 在 main.js 中加入这行即可&#xff1a; // 导入模块 const { app, BrowserWindow ,Menu } require(electron) const path require(path)// 创建主窗口 const createWindow () > {const mainWindow ne…...

软件测试学习笔记丨curl命令发送请求

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/32332 一、简介 cURL是一个通过URL传输数据的&#xff0c;功能强大的命令行工具。cURL可以与Chrome Devtool工具配合使用&#xff0c;把浏览器发送的真实请求还原出来&#xff0c;附带认证信…...

STM32+PWM+DMA驱动WS2812 —— 2024年9月24日

一、项目简介 采用STM32f103C8t6单片机&#xff0c;使用HAL库编写。项目中针对初学者驱动WS2812时会遇到的一些问题&#xff0c;给出了解决方案。 二、ws2812驱动原理 WS2812采用单线归零码的通讯方式&#xff0c;即利用高低电平的持续时间来确定0和1。这种通信方式优点是只需…...

MMD模型及动作一键完美导入UE5-IVP5U插件方案(二)

1、下载并启用IVP5U插件 1、下载IVP5U插件, IVP5U,点击Latest下载对应引擎版本,将插件放到Plugins目录,同时将.uplugin文件的EnableByDefault改为false 2、然后通过Edit->Plugins启用插件 2、导入pmx模型 1、直接在Content的某个目录拖入pmx模型,选择默认参数 2、…...

C++函数指针

函数指针是将一个函数赋值给一个变量的方法 我们使用函数的方法&#xff0c;可能会给函数传入参数&#xff0c;或者传入参数&#xff0c;函数可能有返回值&#xff0c;也可能没有返回值&#xff08;void&#xff09; 下面这个例子&#xff0c;我们调用了HelloWorld函数 auto关…...

汽车信息安全 -- 再谈车规MCU的安全启动

目录 1. 安全启动流程回顾 1.1 TC3xx的安全启动 1.2 RH850的安全启动 1.3 NXP S32K3的安全启动 1.4 小结 2.信任链的问题 3.国产HSM IP的拓展 今天接着 汽车信息安全 -- 存到HSM中的密钥还需包裹吗&#xff1f;-CSDN博客这篇文章深究另一个重要功能-- 安全启动。 该文章…...

[Linux]从零开始的Linux的远程方法介绍与配置教程

一、为什么需要远程Linux 相信大家在学习Linux时&#xff0c;要么是使用Linux的虚拟机或者在物理机上直接安装Linux。这样确实非常方便&#xff0c;我们也能直接看到Linux的桌面或者终端。既然我们都能直接看到终端或者Linux的桌面了&#xff0c;那我们为什么还要远程Linux呢&a…...

手机改IP地址怎么弄?全面解析与操作指南

在当今数字化时代&#xff0c;IP地址作为设备在网络中的唯一标识&#xff0c;其重要性不言而喻。有时候&#xff0c;出于隐私保护、网络访问需求或其他特定原因&#xff0c;我们可能需要更改手机的IP地址。然而&#xff0c;对于大多数普通用户来说&#xff0c;如何操作可能还是…...

【React】useState 和 useRef:项目开发中该如何选择

如果你正踏入用 React 进行网页开发的世界&#xff0c;那你可能已经遇到了像 useState 和 useRef 这样的术语。这两个 Hook 在构建交互性和动态组件时起着至关重要的作用。 下面&#xff0c;我们将探讨它们是什么&#xff0c;它们的功能&#xff0c;它们的区别&#xff0c;并通…...

python装饰器用法

为什么用装饰器&#xff1f; 第一个原因是&#xff0c;使用装饰器可以提升代码复用&#xff0c;避免重复冗余代码。如果我有多个函数需要测量执行时间&#xff0c;我可以直接将装饰器应用在这些函数上&#xff0c;而不是给多个函数加上一样的代码。这样的代码既元余也不方便后…...

【GNSS定位原理及算法杂记2】GNSS观测量:从捕获到解算,揭秘接收机内部信号处理链路

1. GNSS观测量&#xff1a;定位技术的三大支柱 当你打开手机地图查看自己的位置时&#xff0c;背后是GNSS接收机在默默工作。它通过处理来自太空卫星的信号&#xff0c;最终计算出你所在的位置。这个过程中最关键的就是三种观测量&#xff1a;伪距、载波相位和多普勒频移。这三…...

美军“转正”美科技公司AI系统,专家解读

来源&#xff1a;环球时报【环球时报报道 记者 刘扬】据路透社等外媒近日报道&#xff0c;五角大楼将把美国科技公司Palantir的人工智能&#xff08;AI&#xff09;系统Maven列为“正式在编项目”&#xff0c;使美军多军种将该公司的相关技术用于军事领域。五角大楼强调&#x…...

4个步骤让普通用户实现黑苹果EFI自动生成:OpCore Simplify智能工具全解析

4个步骤让普通用户实现黑苹果EFI自动生成&#xff1a;OpCore Simplify智能工具全解析 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 如何用智能工具解…...

探索Comsol在光子晶体光纤SPR - PCF传感器及光学仿真中的奇妙世界

Comsol光子晶体光纤spr pcf传感器comsol光 Comsol光子晶体光纤spr pcf传感器 comsol光学仿真spr。 利用几何相位缺陷态光子晶体实现谷自旋分离在光学领域&#xff0c;光子晶体光纤&#xff08;PCF&#xff09;以及表面等离子体共振&#xff08;SPR&#xff09;相关的研究一直热…...

【SpringBoot】scanBasePackages实战:从默认扫描到精准控制的进阶指南

1. 为什么需要自定义组件扫描路径 第一次用SpringBoot开发项目时&#xff0c;我发现只要把启动类放在顶层包下&#xff0c;所有子包的组件都能自动注册。这种"开箱即用"的特性确实方便&#xff0c;但后来接手一个老项目时遇到了问题&#xff1a;启动耗时长达2分钟&am…...

告别“金鱼记忆”:Hologres + Mem0,为大模型打造企业级长记忆引擎

想象一下这个场景&#xff1a;一位用户在周一联系某电商平台的智能客服&#xff0c;咨询了一款高端相机的详细参数和优惠活动&#xff0c;并明确表示“我倾向于购买A品牌”。客服助手热情地解答了问题。到了周三&#xff0c;这位用户再次联系客服&#xff0c;想了解这款相机的配…...

Vue.Draggable深度解析:源码实现与高级应用实战

Vue.Draggable深度解析&#xff1a;源码实现与高级应用实战 【免费下载链接】Vue.Draggable SortableJS/Vue.Draggable: Vue.Draggable 是 Sortable.js 的 Vue.js 封装组件&#xff0c;提供了拖放排序功能&#xff0c;可以在 Vue 应用中轻松实现列表元素的可拖拽重排。 项目地…...

3个场景解密LeagueAkari:如何让英雄联盟游戏效率提升300%

3个场景解密LeagueAkari&#xff1a;如何让英雄联盟游戏效率提升300% 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit LeagueAkari…...

用快马平台十分钟搭建小龙虾电商网站原型:从菜单到购物车

最近想尝试做一个小龙虾电商网站的原型&#xff0c;从菜单展示到购物车功能一气呵成。传统开发流程可能需要前后端配合、搭建环境、调试接口&#xff0c;但这次我用InsCode(快马)平台尝试了快速原型开发&#xff0c;整个过程比想象中简单很多。 1. 确定核心功能框架 首先梳理…...

从ChatGPT到机器翻译:GRPO算法如何优化大语言模型的生成效果?

GRPO算法&#xff1a;大语言模型生成效果优化的新范式 在自然语言处理领域&#xff0c;序列生成任务的质量优化一直是研究热点。从ChatGPT的对话流畅度到机器翻译的准确性&#xff0c;生成效果直接影响用户体验。传统优化方法如PPO虽然有效&#xff0c;但在处理复杂语言任务时存…...