2022-03-02
對於哈夫曼樹和哈夫曼編碼已經有所認識，此題相當於使用多叉樹的哈夫曼編碼方式。對於k叉樹，我們可以不用樹形結構而用佇列來做，會更方便，哈夫曼編碼又需要選擇最小的k個值來結合，故我們使用優先佇列，在標頭檔案queue中，名為
這個stl的使用方法：
預設從大到小：priority_queuea;
從小到大：priority_queue< int,vector,greater> b;
如果是自定義的資料結構：
structtmp1
bool
operator
<(const tmp1& a) const
};
注意operator要 < ，優先佇列規定的
push()：插入至首位
top():首位元素
pop:刪除
利用優先佇列進行哈夫曼編碼如下：
1 #include2 #include3#define ll long long
4using
namespace
std;
5int
n, k;
6ll sum;
7 typedef struct
treecode
15 inline bool
operator
<(const treecode &a)const
1621
}htree;
22 priority_queueforest;
23inline ll read()
2430
int main(void)31
40for (int i = 1;i <= n;i++)
4145 n +=cnt;
46while (n > 1)47
56 sum +=ans;
57 forest.push(htree(maxlen + 1
, ans));
58 n = n - k + 1;59
}60 cout << sum <61 cout << forest.top().len - 1;62
return0;
63 }
NOI2015 荷馬史詩
傳送門 to luogu 點此檢視有意思的東西 哈夫曼編碼。其證明是非常有意思的。接下來是正文 感謝大佬的部落格提供了思路與 這道題其實就是一道 k kk叉哈夫曼樹。其證明過程，完全可以仿照普通哈夫曼樹的證明。於是我們直接建立哈夫曼樹即可。至於最長的最小這一限制 只需要存一個樹高即可。我在這裡進行簡...
NOI2015 荷馬史詩
點此看題 這道題正解是哈夫曼樹，我們定義每個元素有兩個關鍵字，分別是 出現次數和樹的高度 把每個元素看成一顆樹 自小到大排序，然後取出最小的k kk個元素，將它們合併為一顆樹，合併後的出現次數是這k kk個元素出現次數之後，深度是最大深度加1，塞回資料結構，下面給出貪心的正確性證明 每次合併操作會消...
NOI 2015 荷馬史詩
追逐影子的人，自己就是影子。荷馬 allison 最近迷上了文學。她喜歡在一個慵懶的午後，細細地品上一杯卡布奇諾，靜靜地閱讀她愛不釋手的 荷馬史詩 但是由 奧德賽 和 伊利亞特 組成的鴻篇鉅製 荷馬史詩 實在是太長了，allison 想通過一種編碼方式使得它變得短一些。一部 荷馬史詩 中有 n 種不...
NOI2015 荷馬史詩
在寫題解之前先扯一些閒話 初識這題是在hzwer的部落格上，他寫的一篇類似於回憶錄中提到了這題。其實oi中有很多類似於哈夫曼的知識 它們看起來看起來不是那麼重要，但是如果一旦用到，對於那些不知道的人便是 滅頂之災 oi這玩意，很多時候，真的有一部分運氣的成分，五六場比賽，不能出現一絲錯誤，雖然不乏奇...
NOI2015 荷馬史詩
k叉哈夫曼樹。需要保證權值儘量小的前提下深度最小。我們可以把k個節點合併成一個節點，最後合成一個。所以如果n 1不是k 1的倍數，就補起來。最後就是先取k個最小的,用一個假的節點連起來,然後把這k個東西當成一個新的節點,節點的權值是k個點的權值和。include include include in...
NOI2015 荷馬史詩
顯然一個huffman樹，然後改成 k 叉的就好。但是我不會huffman樹，於是學學拓寬知識面。首先這個 k 叉樹就是一個類似字典樹的東西，但是不對應目標串的點都是非葉結點 不然不滿足字首關係的限制 容易證明，每個點帶 k 1 個葉子是最優的。考慮計算總權值時的深度乘以權值改為它到根的鏈上都加上它...
NOI2015 荷馬史詩
嘟嘟嘟 在luogu上看到這是一道藍題，結果自己想了一個多點也沒做出來 但是自己概括的題意還是很準的 構建一棵最多有 k 個叉的 n 個葉子節點的樹，每一個葉子節點有一個給定的權值，使每一個葉子節點的權值 到根節點的距離之和最小。當時只發現瞭如果把權值從大到小排序，那麼他們距樹根的距離一定是單調不減...
NOI 2015 荷馬史詩
追逐影子的人，自己就是影子 荷馬 allison 最近迷上了文學。她喜歡在一個慵懶的午後，細細地品上一杯卡布奇諾，靜靜地閱讀她愛不釋手的 荷馬史詩 但是由 奧德賽 和 伊利亞特 組成的鴻篇鉅製 荷馬史詩 實在是太長了，allison 想通過一種編碼方式使得它變得短一些。一部 荷馬史詩 中有n種不同的...
NOI 荷馬史詩
追逐影子的人，自己就是影子 荷馬 allison最近迷上了文學。她喜歡在一個慵懶的午後，細細地品上一杯卡布奇諾，靜靜地閱讀她愛不釋手的 荷馬史詩 但是由 奧德賽 和 伊利亞特 組成的鴻篇鉅製 荷馬史詩 實在是太長了，allison想通過一種編碼方式使得它變得短一些。一部 荷馬史詩 中有 n 種不同的...
洛谷P2168 荷馬史詩 NOI2015
追逐影子的人，自己就是影子 荷馬 allison 最近迷上了文學。她喜歡在一個慵懶的午後，細細地品上一杯卡布奇諾，靜靜地閱讀她愛不釋手的 荷馬史詩 但是由 奧德賽 和 伊利亞特 組成的鴻篇鉅製 荷馬史詩 實在是太長了，allison 想通過一種編碼方式使得它變得短一些。一部 荷馬史詩 中有n種不同的...