tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> IT/计算机 >>

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


etc.
?
? ?

周梦宇 Moony Chou 成都七中 zmy90320@gmail.com

信息

信息论
? ? ? ? ?

?

电报、电话、广播、遥控、雷达…… 无所不在的比特——小小的0和1 都是信息的传输系统 The Mathematical Theory of Communication 信息论的研究对象 《通信的数学理论》 理论模型——通信系统模型 By Claude E. Shannon (香农) 为信息论奠定了基础

通信系统模型
信 源
消 息

编 码 器

信 号

信 道

信 号 干 扰

译 码 器

消 息

信 宿

+

信源编码 加密编码 信道编码

干 扰

信道译码 解密译码 信源译码

噪声源

THE TAO OF CODING

码之道
浅谈信息学竞赛中的编码与译码问题

编码译码常用思想与方法
给出一个字符集S(|S|!小于263) ? 【问题一】求S上的所有全排列中字典序第 k小的排列。 ? 【问题二】给出S的一个全排列,求它是字 典序第几小的。

对S元素排序得出字典序最小排列
不断求出相邻较大排列 (可调用STL中的next_permutation算法)

O(|S|*k) k可高达|S|!
【问题二】——编码 【问题一】——译码

调用(k-1)次便可得到目标字符串 需要不断调用并比较

更优算法
?

?

?

问题二:对字符串编码,既是求“不大于x 的物体有多少个”,是一个计数问题。 字典序顺序的确定:由从前往后第一个不 一样的位确定的。 我们可以考虑用分类思想,一位一位地累 加出编码。

”42153”的编码
?????

1????

2????

3???? 41???

4???? 42???

4!*3=72 3!*1=6 0!*2=2 ∑=80

421?? 42135 42153

?
? ?

2) O(nm
? ? ?

所求字符串长度为n 字符集大小为m 每处理一位字符需要累加最多m个 字符 每次累加需要进行分类模板计数, 时间复杂度为O(m) 每处理一位字符需要O(m2)的时间 总复杂度为O(m2n)。

O(n*n!)

编码译码常用思想与方法
?
?

数论、组合计数几类数学思想
[Twofive, IOI 2001][Hexadecimal Numbers, CEOI 1997]…

?

递推动态规划、枚举搜索、排序、 贪心和构造
[CUDAK, COCI 2007/2008 #3][Zip, Zhejiang OI 2001][A decorative fence, CEOI 2002]…

?

?
?

堆、树状数组等特殊的数据结构
[Huffman][Prüfer]…

编码译码具体应用例举
? ? ?

?

Huffman Code(哈夫曼编码) Gray Code(格雷码) Prüfer Code(普吕弗编码) Hash Function(哈希(散列)函数)

Prüfer编码
? ?

?

标号树:顶点标号为1至n的有n个顶点的树 Cayley定理:不同的标号树的数量是nn-2 1889 “A Theorem on Trees.” Prüfer编码:德国数学家Heinz Prüfer 1918年另一个建设性的证明 Prüfer序列(编码)。

编码过程
? ?

?

?

n个结点的标号树T 不断从T中移除当前标号最小的叶子,直到 T只剩下两个结点。 第i次移除叶子的相邻点的标号即为Prüfer 序列的第i项。 Prüfer编码提供了n结点标号树与每个元素 在[1,n]内的长(n-2)的整数序列的一个双射。

1

2 3

4

6 5 7

{} ,}2,}1,}3,}3,}5} 1

8

Prüfer编码应用
【树的计数, HNOI2004 Day2】 一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满 足这样的条件的不同的树有多少棵。

Prüfer编码应用
?

注意到一棵标号树的Prüfer编码中标号i会 出现(di-1)次,于是每个点度数已知的n结点 生成标号树的个数为:

(n - 2)! (d1 - 1)!(d2 - 1)!...(d - 1)! n

总结
编码译码就如同水一样:水是生命 之源,编码译码是信息之源;水亦 柔亦刚,编码译码也同样灵动。

道可道,非常道。



推荐相关:

国家集训队2008论文集浅谈最短路径问题中的

园主想建一道 栅栏围住主楼,但是有一 个条件:栅栏不能离建筑 太近.更确切的...国家集训队2008论文集 码... 23页 免费 国家集训队2007论文集6... 15页...


国家集训队2008论文集浅谈信息学中状态的合

国家集训队2008论文集浅谈信息学中状态的合_IT/计算机_专业资料。国家集训队2008...问题分析: 问题分析这题是一道模平方根( Modular Square Roots )的问题, 有...


国家集训队2008论文集非完美算法初探——任

算法和上面的贪心算法相同,随机算法也是使用较多的一种算法.下面我们来 看一道...国家集训队2008论文集 码... 23页 免费 国家集训队2008论文集浅... 21...


国家集训队2007论文集1.杨弋《Hash在信息学

除了 MD5,常用的 CRC32 校验码和 SHA-1 算法 ...这道题目就这样通过了, 但是这样的改动是不是太...国家集训队2008论文集部... 9页 免费 国家集训...


国家集训队2005论文集 黄源河

国家集训队2005论文集 黄源河_IT/计算机_专业资料。...第四部分通过一道例题,说明左偏树在当今信息学竞赛...至于编程复杂度,两者都十分的低,不过斜堆的代 码...


国家集训队2006论文集 王赟

国家集训队2006论文集 王赟_IT/计算机_专业资料。国家集训队2006论文集 ...分析】 【分析】乍一看,这道题与例 1 不是一模一样的吗?其实不然.与例 1...


国家集训队2001论文集 江鹏

国家集训队2001论文集 江鹏 - 从一道题目的解法试谈网络流的构造与算法 福建师大附中 江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法...


国家集训队2007论文集2.古楠《平面嵌入》

国家集训队2007论文集2.古楠《平面嵌入》_IT/...1.MergeBiconnectedComponent伪码 ---13 2.walkup伪...其实对外部面的遍历我们是不需要一直知 道到底是逆...


国家集训队2007论文集9.周冬《生成树的计数

这也是一道生成树的计数问题.但是,由于必选边的存在,使得我们无法直 接应用 ...国家集训队2008论文集 p... 14页 1下载券 国家集训队2007论文集 陈......


国家集训队2007论文集8.陈瑜希《多角度思考

因此,在平时的练习中,当对一道题目束 手无策时,可从多个角度思考,创造新...国家集训队2008论文集 p... 40页 免费 国家集训队2004论文集 朱... 66页...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com