POJ-3349 Snowflake Snow Snowflakes

Posted by

  是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
  我们可以通过一个简单的例子来了解一下:
  记得桶排序么?其实它就是一个简单的哈希表。我们读入一组数据,然后把它存在一个一维数组里,当我们需要查找这个值时,我们只需在数组中寻找其下表内有没有值即可。
  但是,如果你的数组里面,出现了几个重复的数,那么在桶排序中,你只能再其下标下++,并不能把他展开。在哈希表中我们称之为碰撞。即为元素重复。在哈希表中,我们会采取这样的一种存储结构:如果有重复了,那么我们这个一维数组里面存的就是这个元素的地址,在它的下面(比较抽象),我们加一条链子,就是一个链表,来把这些相同的元素串起来。这样就不会发生碰撞了。
  好了,了解完毕,我们来看看一道“比较”简单的题:(又逢POJ)
  题目来源:http://poj.org/problem?id=3349
  题目:
这道题大概意思就是,寻找相同的雪花。 相同的雪花满足6条边的长度相同。比如,长度为1,2,3,4,5,6和1,2,3,4,5,6相同,或者他与3,2,1,6,5,4也相同,你可以把它想成一个环,1与6相接,3与4相接,其余都是按顺序,所以与1,2,3,4,5,6是相同的。 如果他是相同的,那么就满足他们所有边的和与所有边的乘积的和相同。 我们就可以以此设置哈希函数,来判定是否相同。我们来看代码:
#include 
#include <string.h>
#define p 99991
int a[10000001],num,snow[1000001][7],head[1000001],next[1000001],n;
int Hash(int *a)
{
    int sum=0,mul=1;
    for(int i=0;i<=5;i++)
    {
        sum=(sum+a[i])%p;
        mul=(long long)mul*a[i]%p;
    }
    return (sum+mul)%p;
}
bool same(int *a,int *b)
{
    for(int i=0;i<=5;i++)
        for(int j=0;j<=5;j++)
        {
            bool flag=true;
            for(int k=0;k<=5;k++) if(a[(i+k)%6]!=b[(j+k)%6]) flag=false;
            if(flag) return 1;
            flag=1;
            for(int k=0;k<=5;k++) if(a[(i+k)%6]!=b[(j-k+6)%6]) flag=false;
            if(flag) return 1;
        }
    return 0;
}
bool pd(int a[])
{
    int v=Hash(a);
    for(int i=head[v];i;i=next[i]) if(same(snow[i],a)) return 1;
    ++num;
    for(int i=0;i<=5;i++) snow[num][i]=a[i];
    next[num]=head[v];
    head[v]=num;
    while(1) num++;
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int a[11];
        for(int j=0;j<=5;j++) scanf("%d",&a[j]);
        if(pd(a))
        {
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
    return 0;
}
嘿嘿嘿,(逃 体会我这邪恶的笑容(hua_ji 有代码不懂的地方可以私我,我的qq邮箱是2396389683@qq.com,可以发邮件给我。 再见。
]]>