当前位置: 首页 > 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;而不是给多个函数加上一样的代码。这样的代码既元余也不方便后…...

Vue中实现动态标签页的切换优化与状态管理

1. 动态标签页的核心需求与实现思路 在后台管理系统这类多页面应用中&#xff0c;动态标签页几乎是标配功能。想象一下你正在使用某电商后台&#xff0c;同时开着商品管理、订单处理和用户分析三个页面&#xff0c;这时候标签页的流畅切换和状态保持就显得尤为重要。 我经历过一…...

Qwen3-ASR-1.7B保姆级教程:解决‘识别结果不准确’的5类高频问题

Qwen3-ASR-1.7B保姆级教程&#xff1a;解决‘识别结果不准确’的5类高频问题 1. 引言&#xff1a;为什么你的语音识别总是不准&#xff1f; 你是不是遇到过这样的情况&#xff1a;用语音识别软件录音&#xff0c;结果出来的文字乱七八糟&#xff0c;完全不是你说的内容&#…...

基于SpringBoot的租车系统毕设实战:从需求建模到高可用部署

最近在辅导学弟学妹做毕业设计&#xff0c;发现很多“基于SpringBoot的租车系统”项目&#xff0c;虽然功能列表很长&#xff0c;但仔细一看&#xff0c;架构松散&#xff0c;业务逻辑像面条代码&#xff0c;更别提应对真实场景下的并发问题了。今天&#xff0c;我就结合自己做…...

华为光猫配置解密工具全解析:从加密破解到网络运维实战指南

华为光猫配置解密工具全解析&#xff1a;从加密破解到网络运维实战指南 【免费下载链接】HuaWei-Optical-Network-Terminal-Decoder 项目地址: https://gitcode.com/gh_mirrors/hu/HuaWei-Optical-Network-Terminal-Decoder 在网络运维工作中&#xff0c;光猫设备的配置…...

NaViL-9B效果展示:电商主图自动提取卖点文案+竞品对比分析

NaViL-9B效果展示&#xff1a;电商主图自动提取卖点文案竞品对比分析 1. 多模态大模型惊艳登场 想象一下&#xff0c;当你上传一张商品图片&#xff0c;AI不仅能准确识别图片内容&#xff0c;还能自动生成吸引人的卖点文案——这就是NaViL-9B带来的革命性体验。作为原生多模态…...

大三大学生挖洞收入十万背后:网安圈的“天才少年”,普通人能复制吗?

大三学生挖洞收入十万背后&#xff1a;网安圈的 “天才少年” &#xff0c;普通人能复制吗&#xff1f; SRC首期学员战绩疯传&#xff1a;大四小白45天回本6K&#xff1f;大三在读2个月挖洞收获六位数&#xff1f; 当朋友圈被"零基础挖洞暴富"的捷报疯狂刷屏时&…...

java 短信验证码接口开发面向接口编程实现

在Java企业级后端开发中&#xff0c;短信验证码是用户登录、注册、密码重置的核心身份验证方案&#xff0c;java短信验证码接口的规范化开发直接决定系统的扩展性与维护性。传统硬编码开发模式存在耦合度高、服务商切换困难等问题&#xff0c;本文基于面向接口编程思想&#xf…...

Onekey:3分钟搞定Steam游戏清单下载的终极神器

Onekey&#xff1a;3分钟搞定Steam游戏清单下载的终极神器 【免费下载链接】Onekey Onekey Steam Depot Manifest Downloader 项目地址: https://gitcode.com/gh_mirrors/one/Onekey 还在为复杂的Steam游戏清单获取流程而烦恼吗&#xff1f;Onekey作为一款专业的Steam D…...

告别丑陋代码块!用PyQt5+pygments实现Word代码高亮粘贴(附完整源码)

告别丑陋代码块&#xff01;用PyQt5pygments实现Word代码高亮粘贴&#xff08;附完整源码&#xff09; 在技术文档编写过程中&#xff0c;代码展示是不可或缺的部分。然而&#xff0c;直接将IDE中的代码复制到Word文档时&#xff0c;往往会丢失原有的高亮和格式&#xff0c;变成…...

Proteus8.9 安装避坑指南:从下载到稳定运行的完整流程

1. 为什么选择Proteus8.9&#xff1f; Proteus作为电子设计自动化&#xff08;EDA&#xff09;领域的经典工具&#xff0c;在单片机仿真和电路设计方面一直备受工程师和学生青睐。8.9版本之所以成为众多用户的首选&#xff0c;主要在于它对新型单片机的支持更加完善。比如STC15…...