1 条题解

  • 2
    @ 2021-8-27 17:40:10

    选手答一波。

    枚举每一对生物编辑的代价。

    这样可以建立一个完全图,在这张图上跑 MST 就是答案。

    实际上,可以在建图的时候使用 bitset 卡常数。

    复杂度 O(T(n2logn+w1n2w2+L))O(T(n^2\log n+\dfrac{w_1n^2}{w_2}+\sum L))

    w1w_1 为字母种类,是 5252

    w2w_2 是 bitset 常数的倒数,为 3232

    最大的点跑进 90ms,可以说非常优秀了。

    信息

    ID
    186
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    15
    已通过
    6
    上传者