JOISC做题记录

发布时间 2023-09-25 15:17:23作者: 铃兰星夜

题目真的很好!!!所以来写一写。

但都是一句话题解,因为我实在很懒。打 * 的是没独立做出来的。

慢慢补,不急

2023 Day1T1 Two Currencies

签到题。主席树上二分就行。$O((n+Q) \log n)$。

*2023 Day1T2 Festivals in JOI Kingdom 2

还不会。

2023 Day1T3 Passport

走遍 $1 \sim n$ 显然等价于走到 $1$ 和 $n$。

考虑 $x$ 点的答案长什么样,枚举一个中转点 $y$,求最小的 $dis_{1,y}+dis_{x,y}+dis_{y,n}$。

但直接这么做的话,时间复杂度实在难以接受。但我们发现从 $x$ 到最优的 $y$ 的路径上贡献一定也是一直减少的,我们先钦定 $ans_x=dis_{1,x}+dis_{x,n}$,然后对于存在的边 $(u,v,w)$,讨论一下两点贡献有 $ans_v \le ans_u+w$,再求一遍最短路就好。

再上个线段树优化建图就行了。$O(n \log n)$。

2023 Day2T1 Belt Conveyor