范浩强_wc2012谈谈各种数据结构

《范浩强_wc2012谈谈各种数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、从大象讲起——说说各种数据结构。范浩强自我介绍？●略吧。先从大象说起。●先不着急说数据结构的事。●先从大象那天说起。●23rdIOIDay2和动物在一起的一天。●鳄鱼crocodile●大象elephant●鹦鹉parrot最简单的鹦鹉。“”●为什么说是最简单呢？因为用到的数据结构只“”有数组。●为什么要给简单加引号呢？因为它并不简单。“”鹦鹉。●你有一群鹦鹉。每个鹦鹉可以记住8个二进制位，即，一个0～255之间的自然数。●你告诉了一些鹦鹉一些数，之后，让它们飞到另一个人那里。每个鹦鹉忠实地告诉了那个人（接收者）它记住

2、的数是多少。●你想通过这个方法传递一个消息。但是，鹦鹉有个小问题，就是鹦鹉到达的顺序是随机的。鹦鹉。●例如：●你发送了3只鹦鹉：●1998●到达接收者那里很可能变成了：●9819●你要在这种状况下，通过发送最少个数的鹦鹉来传递消息。消息可以视作一个N位的二进制数。鹦鹉？●这题出得不错。。。但是，怎么做呢？●主要矛盾：乱序到达？●●想法1：每个鹦鹉记住自己是第几个（发送位置码）。●每个鹦鹉记住一个数4x+y，其中y表示一个2位的消息(0/1/2/3)，x表示这个消息在原文中的位置。鹦鹉。●0131●=>051113●到达

3、接收者那里之后●513011●接收者把它们从小到大排序●051113●之后分别模4●0131，很神奇吧。。。嗯，很和谐。●通过这种方法最长能发送多长的消息呢？●X的取值是[0,64)，能最多标记64个位置，每个位置2位，所以最长128位，即16字节。●如果要发送N个字节（8N位）的消息，要用4N个鹦鹉。●这么做有多少分？●子任务1，2：很水，一共32分。●子任务3（18分）●N<=16●鹦鹉数不超过10N●哈哈，一共50分到手了！鹦鹉？。●子任务4（29分）●1<=N<=32●最多发送10N只鹦鹉。●这个怎么办？●如果

4、延续上面的思路，能否不用6个位来标识位置，而是用使用更多/更少的位来编码位置信息？但是。●计算一下各种情况下发送的最大长度。●0个位置码，1*8=8●1个位置码，2*7=14●2个位置码，4*6=24●3个位置码，8*5=40●4个位置码，16*4=64●5个位置码，32*3=96●6个位置码，64*2=128●7个位置码，128*1=128（囧了！）鹦鹉！。●于是，要另辟蹊径。●重新想想，接收者得到的信息的本质是什么？●21330●接收者：我得到了1只说“0”的鹦鹉，1只说“1”的鹦鹉，1只说“2”的鹦鹉，2只说“3

5、”的鹦鹉，没有其他的鹦鹉了。●->1112000......0●发送的信息的本质是一个unsignedint[256]！●使用的鹦鹉数=数组里的元素之和啊哈！●我有想法了。●把0~255视作256个频道。派出一个说x的鹦鹉->在频道x上发送1。●'ac'(0110000101100011)●->015681314●这样，不就可以发送256位的信息了？最多使用256只鹦鹉！相当和谐。●一共79分到手了。●还有哪里可以改进呢？●●●我干嘛在1个频道上只发送1只鹦鹉呢？相当和谐。●一共79分到

6、手了。●还有哪里可以改进呢？●●●我干嘛在1个频道上只发送1只鹦鹉呢？鹦鹉！。●想象：在3个频道上发送2只鹦鹉，一共有10种方法。●000●100●010●001●200●020●002●110●101●011●鹦鹉。●每组频道可以表示一个10进制位，我一共可以用最多170只鹦鹉发送85组频道，即85个十进制位，即282个2进制位。●●很好！不光鹦鹉用得少，消息也传得长了。再接再厉！。●4个频道一组，每组发送P=鹦鹉分数最多7只鹦鹉数/N519●一组有330种方法，可以用来编码一个字节。618●一共可以发送64字节，使

7、用鹦鹉数是7N717(哈●哈，98分了）●子任务4：1531-2P●N<=64剩下2分怎么办？●8个频道一组，发送11只鹦鹉，一共75582种方法，编码16个位，鹦鹉数/N=5.5。可以用bfs来产生各种方法。●如何满分？●16个频道一组，发送20只鹦鹉，一共7307872110种方法，可以编码32位，鹦鹉数/N=5●但是，只能用动态规划来编码，没法bfs，来不及写了。。。●这样，我就得了99分。。。最牛可以做到多少？●在256个频道上发送261只鹦鹉，方法数是●1468967922881709002768861963

8、9369503254590081548750394350441345795303638440595551569047171502630421770738179391387144426481189233947735091485000102045969606●可以编码64个字节●鹦鹉数/N=4.078125●嗯，很好，很好。。。啊，鹦