國(guó)家集訓(xùn)隊(duì)作業(yè)碼之道

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

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

3、后第一個(gè)不一樣的位確定的。我們可以考慮用分類思想，一位一位地累加出編碼。”42153”的編碼?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?個(gè)數(shù)4!=244!=244!=244!=24累加24487296分類41?42?個(gè)數(shù)3!=63!=6累加7884所求字符串長(zhǎng)度為n字符集大小為m每處理一位字符需要累加最多m個(gè)字符每次累加需要進(jìn)行分類模板計(jì)數(shù)，時(shí)間復(fù)雜度為O(m)每處理一位字符需要O(m2)的時(shí)間總復(fù)雜度為O(m2n)。O(nm2)O

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

5、，故幾于道。Prfer編碼標(biāo)號(hào)樹：頂點(diǎn)標(biāo)號(hào)為1至n的有n個(gè)頂點(diǎn)的樹Cayley定理：不同的標(biāo)號(hào)樹的數(shù)量是nn-2 1889 “A Theorem on Trees.”Prfer編碼：德國(guó)數(shù)學(xué)家Heinz Prfer1918年另一個(gè)建設(shè)性的證明Prfer序列（編碼）。編碼過程n個(gè)結(jié)點(diǎn)的標(biāo)號(hào)樹T 不斷從T中移除當(dāng)前標(biāo)號(hào)最小的葉子，直到T只剩下兩個(gè)結(jié)點(diǎn)。第i次移除葉子的相鄰點(diǎn)的標(biāo)號(hào)即為Prfer序列的第i項(xiàng)。Prfer編碼提供了n結(jié)點(diǎn)標(biāo)號(hào)樹與每個(gè)元素在1,n內(nèi)的長(zhǎng)(n-2)的整數(shù)序列的一個(gè)雙射。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編碼應(yīng)用【樹的計(jì)數(shù), HNOI2004 Day2】一個(gè)有n個(gè)結(jié)點(diǎn)的樹，設(shè)它的結(jié)點(diǎn)分別為v1, v2, , vn，已知第i個(gè)結(jié)點(diǎn)vi的度數(shù)為di，問滿足這樣的條件的不同的樹有多少棵。Prfer編碼應(yīng)用注意到一棵標(biāo)號(hào)樹的Prfer編碼中標(biāo)號(hào)i會(huì)出現(xiàn)(di-1)次，于是每個(gè)點(diǎn)度數(shù)已知的n結(jié)點(diǎn)生成標(biāo)號(hào)樹的個(gè)數(shù)為：RSA公鑰加密系統(tǒng)JEPG圖像壓縮標(biāo)準(zhǔn)MD5 SHAISBN Zip Code循環(huán)冗余校驗(yàn)(CRC)碼游程 編碼 MH編碼LZW編碼算法電話手機(jī)號(hào)碼網(wǎng)絡(luò)信息傳輸安全通信 錯(cuò)誤控制總結(jié)編碼譯碼就如同水一樣：水是生命之源，編碼譯碼是信息之源；水亦柔亦剛，編碼譯碼也同樣靈動(dòng)。道可道，非常道。Thank y