poj 3349 Snowflake Snow Snowflakes (利用hash分组)

题意:有n个雪花,每个雪花有6瓣,给出每一瓣的长度,问是否有两个雪花相同。(雪花相同的条件是:存在某个顺序使得两个雪花的每一瓣长度对应相等)

思路:一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针,逆时针都存了一次,那么如果有一个雪花顺时针和逆时针相同,就会出现错误的结果(虽然这个我应该判掉了。。。但是还是WA orz)

归根结底我是没有搞定当hash相同的时候,如何判定这两个不是一组orz。

看了很多题解。。。(为什么大家这道题的代码都写得这么丑啊。。。。?

思路有:hash或者最小表示法,或者最小表示法+hash

思路是,把六瓣的长度求和,作为hash的key值。。。

然后。。。只在key相同的里面找一样的。。。

其实是根据这个和分了组。。。

因为和相同的,未必雪花一样,但是雪花的一样的,和一定相同,极大的缩小了范围。

也让我对hash有了新的理解:

hash未必可以唯一确定某个值,但是可以帮助缩小范围。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz