CF1206D:Shortest Path 题解

主要思路

刚开始以为是搞\(\log n\)个基底点,然后双向边上面做事情,最后发现找图上最小环的复杂度非常的高。所以 GG。

正解考虑把问题的规模进行缩小:也就是把一些答案预先特判掉。比如说,如果某一个位上有超过三个点连接,那么环的大小就可以被确定为是\(3\),也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。

再考虑剩下的情况。此时,\(n\)已经缩小了很多,所以我们暴力建图,用 Floyd 跑最小环即可。

继续阅读CF1206D:Shortest Path 题解

[Fortuna OJ]Aug 1st – Group A 解题报告

A – 水叮当的舞步

真的是玄妙重重。

我们先思考正常的暴力搜索:枚举每一次按下的颜色,然后检查继续更新。考虑用 IDA* 优化这个过程,首先估值函数就是剩下的颜色个数,因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。

继续阅读[Fortuna OJ]Aug 1st – Group A 解题报告