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

×