国家集训队2008论文集 码之道

《国家集训队2008论文集 码之道》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、周梦宇MoonyChou成都七中zmy90320@gmail.cometc.信息Important!信息论无所不在的比特——小小的0和1TheMathematicalTheoryofCommunication《通信的数学理论》ByClaudeE.Shannon（香农）为信息论奠定了基础电报、电话、广播、遥控、雷达……都是信息的传输系统信息论的研究对象理论模型——通信系统模型通信系统模型噪声源干扰信源消息信号信道信号+干扰消息信宿编码器译码器信源编码加密编码信道编码信道译码解密译码信源译码人生二进制，二进制生计算机，计算机包容万物。TheT

2、aoofCoding码之道浅谈信息学竞赛中的编码与译码问题编码译码常用思想与方法给出一个字符集S（

3、S

4、!小于263）【问题一】求S上的所有全排列中字典序第k小的排列。【问题二】给出S的一个全排列，求它是字典序第几小的。对S元素排序得出字典序最小排列不断求出相邻较大排列（可调用STL中的next_permutation算法）【问题一】——译码调用(k-1)次便可得到目标字符串【问题二】——编码需要不断调用并比较O(

5、S

6、*k)k可高达

7、S

8、!next_permutation算法具体实现字符串ss从右往左第一个满足s[i]

9、将s[i]和s[i+1]交换将s[i+1]及其右边的所有字母颠倒过来。O(

10、s

11、)更优算法问题二：对字符串编码，既是求“不大于x的物体有多少个”，是一个计数问题。字典序顺序的确定：由从前往后第一个不一样的位确定的。我们可以考虑用分类思想，一位一位地累加出编码。”42153”的编码?????1????2????3????4????41???42???421??42135421534!*3=723!*1=60!*2=2∑=8080的译码?????1????2????3????4????41???42???421??42135421534???

12、?——7242???——78…………分类1????2????3????4????个数4!=244!=244!=244!=24累加24487296分类41???42???个数3!=63!=6累加7884所求字符串长度为n字符集大小为m每处理一位字符需要累加最多m个字符每次累加需要进行分类模板计数，时间复杂度为O(m)每处理一位字符需要O(m2)的时间总复杂度为O(m2n)。O(nm2)O(n*n!)编码译码常用思想与方法数论、组合计数几类数学思想[Twofive,IOI2001][HexadecimalNumbers,CEOI1997]…递

13、推动态规划、枚举搜索、排序、贪心和构造[CUDAK,COCI2007/2008#3][Zip,ZhejiangOI2001][Adecorativefence,CEOI2002]…堆、树状数组等特殊的数据结构[Huffman][Prüfer]…编码译码具体应用例举HuffmanCode（哈夫曼编码）GrayCode（格雷码）PrüferCode（普吕弗编码）HashFunction（哈希（散列）函数）编码若宇。宇善容万物而不乱，处万物之所源，故几于道。Prüfer编码标号树：顶点标号为1至n的有n个顶点的树Cayley定理：不同的标号树的

14、数量是nn-21889“ATheoremonTrees.”Prüfer编码：德国数学家HeinzPrüfer1918年另一个建设性的证明Prüfer序列（编码）。编码过程n个结点的标号树T不断从T中移除当前标号最小的叶子，直到T只剩下两个结点。第i次移除叶子的相邻点的标号即为Prüfer序列的第i项。Prüfer编码提供了n结点标号树与每个元素在[1,n]内的长(n-2)的整数序列的一个双射。12346578{,2,1,3,3,5}1}}}}}}译码过程(a1,a2,…,an-2)(a1,a2,…,ai,…,an-2,n)(b1,b2,…

15、,bi,…,bn-2,bn-1)minPrüfer编码应用【树的计数,HNOI2004Day2】一个有n个结点的树，设它的结点分别为v1,v2,…,vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。Prüfer编码应用注意到一棵标号树的Prüfer编码中标号i会出现(di-1)次，于是每个点度数已知的n结点生成标号树的个数为：RSA公钥加密系统JEPG图像压缩标准MD5SHAISBNZipCode循环冗余校验(CRC)码游程编码MH编码LZW编码算法电话手机号码网络信息传输安全通信错误控制总结编码译码就如同水一样：

16、水是生命之源，编码译码是信息之源；水亦柔亦刚，编码译码也同样灵动。道可道，非常道。Thankyou!感谢父母对我无私的关爱感谢张君亮老师的认真辅导感谢各位教练和我的朋友们给我的帮助感谢CCF给