國家集訓隊作業(yè)碼之道

1、周夢宇成都七中 etc.信息Important!信息論無所不在的比特小小的0和1The Mathematical Theory of Communication通信的數(shù)學理論By Claude E. Shannon （香農(nóng)）為信息論奠定了基礎電報、電話、廣播、遙控、雷達都是信息的傳輸系統(tǒng)信息論的研究對象理論模型通信系統(tǒng)模型通信系統(tǒng)模型噪聲源干擾信源消息信號信道信號+干擾消息信宿編碼器譯碼器信源編碼加密編碼信道編碼信道譯碼解密譯碼信源譯碼人生二進制，二進制生計算機，計算機包容萬物。The Tao of Coding碼之道淺談信息學競賽中的編碼與譯碼問題編碼譯碼常用思想與方法給出一個字符集S（|S

2、|!小于263）【問題一】求S上的所有全排列中字典序第k小的排列。【問題二】給出S的一個全排列，求它是字典序第幾小的。對S元素排序得出字典序最小排列不斷求出相鄰較大排列（可調(diào)用STL中的next_permutation算法）【問題一】譯碼調(diào)用(k-1)次便可得到目標字符串【問題二】編碼需要不斷調(diào)用并比較O(|S|*k)k可高達|S|!next_permutation算法具體實現(xiàn)字符串ss從右往左第一個滿足sisi+1的i將si和si+1交換將si+1及其右邊的所有字母顛倒過來。O(|s|)更優(yōu)算法問題二：對字符串編碼，既是求“不大于x的物體有多少個”，是一個計數(shù)問題。字典序順序的確定：由從前往

3、后第一個不一樣的位確定的。我們可以考慮用分類思想，一位一位地累加出編碼?！?2153”的編碼?1?2?3?4?41?42?421?42135421534!*3=723!*1=60!*2=2=8080的譯碼?1?2?3?4?41?42?421?42135421534?7242?78分類1?2?3?4?個數(shù)4!=244!=244!=244!=24累加24487296分類41?42?個數(shù)3!=63!=6累加7884所求字符串長度為n字符集大小為m每處理一位字符需要累加最多m個字符每次累加需要進行分類模板計數(shù)，時間復雜度為O(m)每處理一位字符需要O(m2)的時間總復雜度為O(m2n)。O(nm2)O

4、(n*n!)編碼譯碼常用思想與方法數(shù)論、組合計數(shù)幾類數(shù)學思想Twofive, IOI 2001Hexadecimal Numbers, CEOI 1997遞推動態(tài)規(guī)劃、枚舉搜索、排序、貪心和構造CUDAK, COCI 2007/2008 #3Zip, Zhejiang OI 2001A decorative fence, CEOI 2002堆、樹狀數(shù)組等特殊的數(shù)據(jù)結構HuffmanPrfer編碼譯碼具體應用例舉Huffman Code（哈夫曼編碼）Gray Code（格雷碼）Prfer Code（普呂弗編碼）Hash Function（哈希（散列）函數(shù)）編碼若宇。宇善容萬物而不亂，處萬物之所源

5、，故幾于道。Prfer編碼標號樹：頂點標號為1至n的有n個頂點的樹Cayley定理：不同的標號樹的數(shù)量是nn-2 1889 “A Theorem on Trees.”Prfer編碼：德國數(shù)學家Heinz Prfer1918年另一個建設性的證明Prfer序列（編碼）。編碼過程n個結點的標號樹T 不斷從T中移除當前標號最小的葉子，直到T只剩下兩個結點。第i次移除葉子的相鄰點的標號即為Prfer序列的第i項。Prfer編碼提供了n結點標號樹與每個元素在1,n內(nèi)的長(n-2)的整數(shù)序列的一個雙射。12346578, 2, 1, 3, 3, 51譯碼過程(a1, a2, , an-2)(a1, a2,

6、, ai, , an-2, n)(b1, b2, , bi, , bn-2, bn-1)minPrfer編碼應用【樹的計數(shù), HNOI2004 Day2】一個有n個結點的樹，設它的結點分別為v1, v2, , vn，已知第i個結點vi的度數(shù)為di，問滿足這樣的條件的不同的樹有多少棵。Prfer編碼應用注意到一棵標號樹的Prfer編碼中標號i會出現(xiàn)(di-1)次，于是每個點度數(shù)已知的n結點生成標號樹的個數(shù)為：RSA公鑰加密系統(tǒng)JEPG圖像壓縮標準MD5 SHAISBN Zip Code循環(huán)冗余校驗(CRC)碼游程 編碼 MH編碼LZW編碼算法電話手機號碼網(wǎng)絡信息傳輸安全通信 錯誤控制總結編碼譯碼就如同水一樣：水是生命之源，編碼譯碼是信息之源；水亦柔亦剛，編碼譯碼也同樣靈動。道可道，非常道。Thank y