专栏文章

题解：P10439 [JOIST 2024] 逃生路线 2 / Escape Route 2

hhappybob
P10439题解参与者 2已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minhycnp
此快照首次捕获于
2025/12/02 02:42
3 个月前
此快照最后确认于
2025/12/02 02:42
3 个月前
查看原文
不难发现本质就是个贪心，只要 l→l+1l \rightarrow l+1 选的是哪个确定，后面的都可以直接贪心得到。
对称的，只要 r−1→rr-1 \rightarrow r 选的是哪个确定，前面的也不难贪心得到。
直接枚举 l,r−1l,r-1 中向下一个点的边数较小的一侧并记忆化，显然是 O(nn)O(n\sqrt n) 的枚举次数。
加个倍增查询贪心的结果就是 O(nnlog⁡n)O(n\sqrt n \log n) 的。
但是你既然都根号了，写个分块平衡复杂度就能做到 O(nn)O(n \sqrt n) 了。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...