选手答一波。
枚举每一对生物编辑的代价。
这样可以建立一个完全图,在这张图上跑 MST 就是答案。
实际上,可以在建图的时候使用 bitset 卡常数。
复杂度 O(T(n2logn+w1n2w2+∑L))O(T(n^2\log n+\dfrac{w_1n^2}{w_2}+\sum L))O(T(n2logn+w2w1n2+∑L))
w1w_1w1 为字母种类,是 525252。
w2w_2w2 是 bitset 常数的倒数,为 323232。
最大的点跑进 90ms,可以说非常优秀了。
By signing up a HydroOJ universal account, you can submit code and join discussions in all online judging services provided by us.
Using your HydroOJ universal account