• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3349 – Snowflake Snow Snowflakes

    ACM-POJ EXP 137阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    在n (n<100000)个雪花中判断是否存在两片完全相同的雪花,每片雪花有6个角,每个角的长度限制为1000000

    两片雪花相等的条件:

    雪花6个角的长度按顺序相等(这个顺序即可以是顺时针的也可以是逆时针的)

    解题思路

    Hash吧!连加求余法 求key 值,链地址法解决冲突

    设雪花6片叶子的长度为len1~len6

    key=( len1+len2+len3+len4+len5+len6)%prime

    =( len1%prime +len2%prime +len3%prime +len4%prime +len5%prime +len6)%prime

    为了避免出现大数,这里使用了同余模定理求key


    注意

    这里的key千万不能用平方和,本来这题时间就很紧凑了,乘法运算更加严重浪费时间,所以采用了连加求key,只要prime足够大,同样能够把地址冲突降低到最低,我取了10n(就是100W)内的最大的素数作为prime, prime=999983


    基本做法

    从上面的处理手法能够知道:

    当且仅当两片雪花的key值一样时,这两片雪花才有可能相同

    在输入第k个雪花信息的时候,先求出其key值,若在hash[]中key值没有出现过,则直接存放信息。但如果在hash[key]中已经保存有其他地址,说明此前出现过key值相同的其他雪花,这些雪花信息以链表的形式存放在hash[key]中,这时在为第k个雪花信息寻找存放空间的同时,必然在链表中逐一访问这些具有相同key值的雪花,所以我们就能在寻址的同时,顺便逐一比较第k个雪花与这些雪花的信息,一旦发现k与某个雪花是一样的,则标记,然后等待后续输入完成后,直接输出寻找到两片一样的雪花。

    但是当所有输入结束后都没有标记过,则说明不存在一样的雪花。


    这时肯定又会有同学有疑问

    Key值只能说明两片雪花的叶子长度之和相等,但是不能说明6片叶子分别相等,更加不能说明6片叶子按顺序相等。那么当我们寻找到key值相同的两片雪花时,我们该如何比较两片雪花?

    其实是可以的。假设有两片雪花,A 和B

    我们固定A,先按顺时针方向比较

    若A0==B0,则按顺序比较A1和B1………比较A5和B5

    只要当出现Ai != Bi,则把B顺时针转动一次,

    若A0==B1,则按顺序比较A1和B2………比较A5和B0

    。。。。。

    以此类推,直至B转动了5次,若还不相同,则说明这两片雪花在顺时针方向不等。

    再比较逆时针方向

    同样固定A,若A0==B5,则按顺序比较A1和B4………比较A5和B0

    只要当出现Ai != B(5-i),则把B逆时针转动一次,

    若A0==B4,则按顺序比较A1和B3………比较A5和B5

    。。。。。

    以此类推,直至B转动了5次,若还不相同,则说明这两片雪花在逆时针方向不等。

    如是者,比较两片雪花最坏的情况为要比较36*2 = 72 次!!!

    可想而知当n=10W时,若任意两片比较,则最坏要比较 72*(10W)^2次


    这里给出两条公式

    设i为A、B的第i片叶子,j为B当前顺时针转过的格数

    那么 A(i) —> B( (i+j)%6 )

    设i为A、B的第i片叶子,j为B当前逆时针转过的格数

    那么 A(i) —> B( (5-i-j+6)%6 )

    因此,为了尽可能第降低比较次数,那么我们就需要把雪花按key值分类,此时就务求prime在恰当的范围内尽可能大,使得地址冲突 (出现两个或以上key值相同的雪花) 的情况尽可能降到最低,最理想的情况就是:当且仅当两片雪花是相同的时候,他们的key值才相等。那么根据前面的算法思路(只对key值相同的两片雪花进行比较),在最理想情况下,我们最多仅需比较1次就能得到“存在雪花相同”结果,最少比较0次就能得到“不存在一样的雪花”的结果

    经过测试发现,prime取100W左右的素数时,key的离散程度是相对比较高的,冲突也就很少,prime再大,对离散化程度影响不大,而且会浪费空间。。

    而当prime取10W左右的素数时,出现key值相同的情况达到6K多个,此时Hash的优势根本体现不了。

    转载请注明:EXP 技术分享博客 » POJ3349 – Snowflake Snow Snowflakes

    喜欢 (1) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址