主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P13516 [KOI 2025 #1] 快递运输
最后更新于 2025-07-31 08:59:16
作者
ran_qwq
分类
题解
题解
P13516
复制 Markdown
查看原文
删除文章
更新内容
下面我们定义 $1\sim n$ 上的位置集合为主干道,其他位置为岔路。我们没必要把快递搬出主干道,证明考虑我们把物品搬到了从【主干道一位置 $u$ 分出的岔路】上的一位置 $v$。那么 $u$ 肯定是可达的,且相比 $v$ 更靠近 $n$,所以比 $v$ 更优。 所以每个机器人的有效覆盖范围是主干道上的一段区间,直接转化为链的情况。设机器人物流中心到主干道距离为 $d$,离 $1$ 点距离为 $D$,则可以覆盖主干道上离 $1$ 点距离为 $[D-X,D+X-2d]$。 能到达 $n$ 的充要条件是每个位置都有区间覆盖,加机器人和删机器人的操作都可以用区间加区间求 max 线段树维护。因为线段树上的区间端点是整数所以要转成左闭右开区间。 值域过大,可以离散化,也可以动态开点,反正空间开得下,时间也够。 [这是代码。](https://www.luogu.com.cn/paste/7ureloez)
正在渲染内容...
点赞
0
收藏
0