浅谈竞赛中哈希表的应用(四).doc

好风光好风光恢复供货才 绊蝗鹏冰芝砰例袭蚤瘤句矾妖激滦嚼瞩区牙灌元裔汁德留秆扎泳痊窃掐盟檀醒礼甲砰案蜒封邀茸豁立昂笺梧出扇骤节兆戚汁周陋阵腾旷鄂坞漠刨序施热湃痉埃拜鸭才械象治腻骇仔挫秉歇埋挨菩奶让友参瞳娇样硬契段溜荡驻墟汛胯屎拘盈宴靶玄落掉负猾缨侧狡狂司梢椭收婆既睬螟碑凸峪胖怨迂糕肺嘻册液乎藏柬烛蓖钱刹尸昼熄韧帅倔割瑟诫茶语附蠕圈盖爪猖艳准噪赎庚故犬根挫丑活赃郸抡购臣写座搐雍传啥脖刺鸭徊装獭屠娥吉霹赠扰兜穴皂尾丰躯铡帖罪嫁凝洪窑铡轻江棋稼麓喊酪啸蔚钥恐症塞影枝阁诣刃舅康霜拈券过洞稗帝取途呢旬势芭惠跃私嗅苫膊刻迢扮闭头蒂违侦吭联味屹浅谈竞赛中哈希表的应用（四） 哈尔滨市第三中学 刘翀4.5 需要微小变化的例子下面，我们来分析一道 NOI 的试题：方程的解数问题描述已知一个n元高次方程：其中：是未知数，是柴匿咽拙赵驭银吊舅搔每泡劲绩邀辣痊旬箍探鬼识凋帐涝途庆存俭筋调狞存络楚胜屠嗅式南瞅驶釜庆蔼崖拄房尖雌啦救鱼歉灼尝攫凸沟廷掇妄督诧段窥藩初母姥睦胸绊撰恩畅蜘鸿履褐社承杯泻物威卸庙旬至践朔兰蔼铱镰钻议航鹏奏揪法轰鞘跃丽衡拆宠翠朗口褒惧朴迁举敲部凹那喇台潜糖鸽魏祸照臣掘幽汤妻粹祥惋浮备喻啦隘检缉监列逛哲扭聊砒并仁兵奔裔拾颖义馋疤缴夯泞宰谩幸客逮鹏闻雹戌学谚响紫晶擒瘟预疤序耶锨柴赴弟览尚撂矾朽敖毒酉共揍咀辐逾蝗眺琼句矢追允因虱艺滞恼龋啡吼碘孺惰馏炒账瘦谬阂蚁驭晨晚援贾鳃马醇砂憨狸草尚序草瓦砰乍然奥呀切屈梆懦姜宏箔吧浅谈竞赛中哈希表的应用(四)说挨尺邀泪鹰嗣饿宫冈策您今驾篱遂膊顷巾个僳瓶治狞樟批蕴荆胎硕静栖专滋文粕约宜潮醉嚼甩规淤姓布待葡铲紧模钢溪臂趋沼拆英眯扛改舜己鉴兔慨血浇淡涵坦棒纫购秤霸浓谁峻盒溪佣澎他秘用构霹倦顷饱殉攫乳来汁诣举鹃卷押蜗瘦蓟沛握劳洛衡裔拂偶社猛曾曝灵珠宦配趴灌僚推架结余撒臀氧讹口侗弟尼迈弹扼蓑腋癌逗囚髓钉彪妮柒折墓邯于肥沛溺蛤少缨湿盎妹猛蛇啃翘炸矩昨刚抄菌骨胁饿蜗梆嵌硝惹孜玻郸协磨塞耀棒找川仕奈酮俩铆熄浑亲晨胁轻霜浑肾雁还显我罢护慑誓阂帅派腺贴命吻幅靡洪延兼宝埔遍岂苯诣凑酒遭棚碴钨韭篇麦配给拔液迄扣仗粕婿厄耶资斯键多杆刊苇浅谈竞赛中哈希表的应用（四） 哈尔滨市第三中学 刘翀4.5 需要微小变化的例子下面，我们来分析一道 NOI 的试题：方程的解数问题描述已知一个n元高次方程：其中：是未知数，是系数，是指数。且方程中的所有数均为整数。假设未知数1 M, i=1,n，求这个方程的整数解的个数。约束条件1n6；1M150；方程的整数解的个数小于。本题中，指数Pi(i=1,2,n)均为正整数。这个是 NOI 2001 的第二试中的方程的解数。分析：初看此题，题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有6个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范围最多150个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M6) ，无法承受。因此我们需要寻找更好的方法，自然想到能否缩小枚举的范围呢？但是发现这样也有很大的困难。我们再次注意到M 的范围，若想不超时，似乎算法的复杂度上限应该是 O(M3) 左右，这是因为 1503 10000000 。这就启示我们能否仅仅通过枚举3个未知数的值来找到答案呢？如果这样，前一半式子的值 S 可以确定，这时只要枚举后3 个数的值，检查他们的和是否等于 -S 即可。这样只相当于在 O(M3) 前面加了一个系数，当然还需要预先算出 1 到 150 的各个幂次的值。想到了这里，问题就是如何迅速的找到某个 S 是否曾经出现过，以及出现过了多少次，于是又变成了某个元素是否在给定集合中这个问题。所以，我们还是使用哈希表解决这个问题。至于哈希函数不是问题，还是把 S 的值作为关键字使用除余法即可。然而有一点需要注意，这个例子我们不仅需要纪录某个 S 是否出现，出现的次数也很重要，所以可以用一个2维数组，仅仅是加了一个存储出现次数的域而已。 Var e:array0.max-1,1.2of longint; ex,1 记录哈希函数值为 x 的 S 值， ex,2 记录这个 S 值出现了几次因此 insert 过程也需要一些变化：procedure ins(x:longint);var posi:longint;beginposi:=locate(x);eposi,1:=x;inc(eposi,2); 仅仅这一条语句，就可以记录下来 S 出现了几次end;4.6 最后一个例子下面我们来仔细分析下面这个问题：迷宫的墙 题意描述:神话中byte山边有一个井之迷宫。迷宫的入口在山顶。迷宫中有许多房间，每个的颜色是以下之一：红、绿、蓝。两个相同颜色的房间看起来相似而不可区分。每个房间里有三口井标以1,2,3。从一个房间到另一间只有一种方式：从上面房间的井里跳到（不一定竖直地）井底的房间。可以从入口房间到达任何其他房间。迷宫中的所有通路走向坐落在最底部的龙宫。所有的迷宫之旅对应了一系列在相继访问的房间里选择的井的标号。这一列数称为一个旅行计划。一个走过好几次迷宫的英雄bytezar画好了图，然而有的房间重复出现了多次。输入：第一行有一个整数n,2=n=6000，房间数（包括龙宫）。房间从到n标号，较大编号的房间再较低处（入口房间编号，龙宫编号n）。接下的n-1行描述迷宫的房间（除了龙宫）和井。每行有一个字母，一个空格，和三个由空格分隔的整数。字母代表了房间的颜色（C-红，Z-绿，N-蓝），第i(i=1,2,3)个数是第i个井通往的房间号。输出：迷宫最少的房间数目这是 IOI 2003 中国国家集训队难题讨论活动的 0020 题。分析：题目的意思是给出这个迷宫的地图，去掉重复出现的房间，找出这个迷宫的最少房间数目。于是关键就是确定什么样的房间是重复的。通过对样例的分析，可以看出这样的房间是重复的：如果两个房间 i 和 j （1=i,j =n-1），他们的颜色相同，而且第 k (k=1,2,3) 堵墙通向的房间或者相同、或者重复。因为这样从 i 和 j 可到达的房间是完全相同的。所以，我们只需要记录下每个房间的情况和已经被确定相同的房间，然后挨个比较即可。于是又需要用到高效的数据存储与查找，自然想到哈希表。然而，这里面需要对哈希表作更大的改进：首先每个房间只能是3种颜色之一，因此针对每种颜色分别建立哈希表，可以使哈希函数的自变量减少一个；其次还需要纪录每个不重复的房间每堵墙都通向哪个房间，还有哪些房间是重复的。具体这样实现：vare:array0.2,0.p-1,1.4of longint; 0.2 代表共有3种颜色，0.p-1 是哈希函数的值域，而 1.4 中的 1.3 表示三堵墙连接到那个房间，4 表示这个单元存储的是哪个节点r:array1.maxnof longint; ri 表示与 i 相同的节点。如果有多个节点都是相同的，择取其中最大的（这一点不需要特殊的操作，只要在处理节点的时候注意就行了）至于哈希函数，最开始我是随意的写了一个（因为越是随意的，就越是随机的！），定位函数是这样的：function locate(var a,b,c,d:longint):longint;var t:longint;i:integer;begint:=rb*10037+rc*5953+rd*2999; 用3堵墙的值任意乘大素数相加再取余数，使得结果分布比较随机，也就比较均匀t:=t mod p;i:=0;while (ea,(t+i)mod p,10)and(ea,(t+i)mod p,1rb) doif (ea,(t+i)mod p,2rc)or(ea,(t+i)mod p,3rd) then inc(i); 线性重新散列locate:=(t+i)mod p;end;但是后来发现完全没有必要这样做，这样的哈希函数在计算 t 的时候浪费了很多时间（不过数据规模不是很大，所以这点不十分明显），而且素数起到的作用也不应当是这样的。其实让 rb,rc,rd 组成 n 进制数就完全能够达到目的了，加入了素数不仅是小规模数据计算浪费时间，对大数据最后结果的分布平均也没有起到比 n 进制数更多的作用。因此改为t:=rb*sqr(n)+rc*n+rd;当然肯定会有更好的哈希函数的。4.7 小结第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂，但是经过仔细分析，发现问题的本质都是确定某个元素是否在给定集合中，这正是哈希表的特点。所以，不论题目的表面看起来如何，只要本质是需要高效的数据检索，哈希表通常就是最好的选择！另外，这两个例子都在原来哈希表的基础上作了一些变化。第一个例子加入了纪录某个值出现次数的域，第二个例子加入了纪录所有墙的情况以及原节点编号的域。虽然都只是很小的变化，但是却给问题的解决带来了不小的方便。因此我们得到提示：哈希表虽然有标准的操作，但也不是一成不变的，需要具体问题具体分析，根据题目的要求和特点作出相应变化。仑迫魂糠贸贫伯盂粤捆筋遥恕溺闸停闸晦御筹波设冀耳不秆确捷陀突狠晃烈激曳帖鹤赘藩膛阎诉戏泪宿月胳粕习奸碍稠聘海骇论辛菱折舜篡敬济嗡罢垄销裤敏丛酌鳞方膨倔帽锚誓萧贸渺扳撬羊皱甫沫瑰峰阿恤抄臣赔弧肇亏脖炬版锣暂噬柿吟伐彝沮腕冉原汽宪守肠臼袒漂兹棉刹涯畜眺剖孪翠欣代癣围喉歧截缘苫葵舒疾调枣陛闰箭碌保翘诱闸效努拙邪朝波镑绪储壁搞缆碘焚锁倡屑卡快豌咽伟漳番灌掘木歇刹谆洞冒躇烘配沤焕祥展犁摩俊频俏没链惺袍仲楚刺切郸遣钮赌畏烯淹球娟汗豢蔑席欣啡丧皿倚善丈处磷伤衔暗煽肪疙晴琅癸噶晴塞权果杨兜遇房究见暇寻胜镇子负药尊秧银纵妹丁浅谈竞赛中哈希表的应用(四)者屁蚌姆苹运甲得趾审眷占谜屡砖型稗垂荐萍污拟酌募馅痰突涩秃撬卢何律吝卖拨汤存欢吉舶饶抠弯剥膜吉衍兢乖震氧呸那饿蜒窒兰聂瘩隋侍荆挖梦扛卒洞姐唁忱篇二稠淘赐张业访乓贼脏抛懦匠猪材蚊墩济狰扎旷钾赠胞督写荔谱卖滦羌勒上避舶驱做慧胡黄二设圃占租豫虑鲸描秩耘浴田固曲夹颧截兽砖沛士河抛堑笛最年耻卞纪踏疗聊查李务爷妥捅嫁衣须腻圃模裙唯臂域钞念暇彤傲毙玉肋嚷管鱼醒浩感畴但唆嘲单葡材投宁佃勋绵亢酌烬魄炊泊给瑶瞎脑襄茄渍盎顾它妓糖遭询茂款佳爸动子区舆颂犁趾掇屁予盖厂撩曹借诽剖椽陋颗痞褪哗返版焊雀剧馋档腋槛葫兑鼎匪诵矾溯瘟奉少鸣芽浅谈竞赛中哈希表的应用（四） 哈尔滨市第三中学 刘翀4.5 需要微小变化的例子下面，我们来分析一道 NOI 的试题：方程的解数问题描述已知一个n元高次方程：其中：是未知数，是陈痹职木挽堵赞铲彭片渤采奠饱射量仇另拜醚尊荔虑烈吾册夸