主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
P9331 [JOISC 2023 Day1] Passport
最后更新于 2025-05-17 18:30:11
作者
Zpair
分类
题解
题解
P9331
复制 Markdown
查看原文
更新内容
注意到可达的点一定构成一段区间，所以问题等价于同时走到 $1,n$ 的最小花费。 先建反图预处理出 $1$ 和 $n$ 到每个点的距离，记为 $dis1$ 和 $dis2$，这个线段树优化建图然后bfs一遍就行。 考虑钦定最后答案的护照获得顺序，对于当前的可达区间 $[l,r]$，我们要求在取 $[l,r]$ 之外的点后再也不能取 $[l,r]$ 中的点，容易发现这并不影响答案。 对于当前的 $[l,r]$，我们最多会在其中取两个点，否则一定会有点的区间被完全包含。 当取两个点 $x,y$ 时，不妨令 $L_x \le l,R_y \ge r$。则一定存在一组最优解满足 $x$ 走到 $1$，$y$ 走到 $n$。因为如果是从 $x$ 走到 $n$，则当前的 $y$ 可以放在以后选取，这样一定不劣，于是此时答案为 $\min(dis1_x+dis2_y+2)$。 进一步的，我们不需要枚举选取的两个点 $x,y$，上面的式子等价于当前区间到 $1,n$ 的距离和。 当取一个点 $x$ 时，不妨令：$L_x \le l$，另一边的情况类似。 我们断定，将当前可达区间改为 $[L_x,R_x]$ 不影响答案。 当 $R_x \ge r$ 时显然成立。 当 $R_x < r$ 时，被错误标记为不可达的区间为 $[R_x+1,r]$，根据我们的钦定顺序，这段区间不会影响后面的选取。 当 $r=n$ 时，当前区间的答案可以被取两个点统计到，否则后续的选取一定会有一段覆盖到 $n$ 的区间，则 $[R_x+1,r]$ 的区间被标记为不可达也不会影响答案。 于是可以发现上面的可达区间只有每个点的对应区间，设：$f_p$ 表示从 $[L_p,R_p]$ 开始同时到 $1,n$ 的最小花费，则有：$f_p=\min(dis1_p+dis2_p,\min_{p \rightarrow t}(f_t+1))$。 按照最短路的更新方式 bfs 一遍即可。 双倍经验：[[USACO21DEC] Tickets P](https://www.luogu.com.cn/problem/P7984)。
正在渲染内容...
点赞
2
收藏
0
