BZOJ5017 - [SNOI2017] 炸弹

zhouyuheng2003 学长一天打完 CF 后给我做的一道他说是简单题的题,然而炒鸡难!!!

考虑暴力,每个炸弹向能引爆炸弹的连边,总数是 $n^2$ 级别的。之后跑 tarjan 缩点,并在 DAG 上统计答案。统计是,考虑合并来的点所对应的情况可能会有重点,因此需要开桶去重。这样的时空复杂度都是 $O(n^2)$ 的。

考虑优化,通过观察可以发现,能引爆的炸弹一定是连续的一整段区间。可以用线段树优化建边,统计答案时不需要开桶统计,而是统计能够炸掉的最左端的点和最右端的点。时间复杂度 $O(n \log n)$ ,空间复杂度 $O(n \log n)$。

同时

当然这并不是最优的,zhouyuheng2003 学长的博客中给出了一种时空复杂度均为 $O(n)$ 的做法。见 https://blog.csdn.net/zhouyuheng2003/article/details/83278984

又是一道非常水的黑题。给你一个双向图,你需要代替炎魔之王拉格纳罗斯(???)会净化图中的所有环,也就是除了链以外的强连通分量,成为一颗无根树。然后询问树上距离。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×