Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「NOI2015」荷马史诗 - 哈夫曼树

    n n 种不同的单词,从 1 1 n n 进行编号。其中第 i i 种单词出现的总次数为 Wi W_i 。要用 k k 进制串 Si S_i 来替换第 i i 种单词,满足对于任意的 1i,jn, ij 1 \leq i,j \leq n,\ i \neq j ,都有:Si S_i 不是 Sj S_j 的前缀。

    1. 替换以后得到的新的长度最小为多少;
    2. 在确保总长度最小的情况下,最长的 Si S_i 的最短长度是多少?

    于  BZOJ, NOI, 哈夫曼树, , 数据结构 继续阅读