关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年4月15日
初学数据结构:哈希表的运用 — POJ 3349 Snowflake Snow Snowflakes

哈希表?

2018.3.10 链表考试 解题报告 中的第一题,所用到的就是哈希表

哈希表,Hash表,又称散列表,是一种基础数据结构,我们使用这个结构是为了让我们在查找或者比对的时候缩小范围以优化时间

其原理大致为,我们将我们要插入的数据经过一些运算并对大质数取模后(哈希函数)得到一个数,我们会直接在head数组中查找其是否存在,存在后在进行比对,不存在则插入

如果哈希函数后的值碰撞了怎么办?

所以我们需要使用链表,对每一个哈希值我们都建一个链表,然后进行查找即可,在哈希函数碰撞少的时候,其查询与插入时间最优复杂度为O(1),平均复杂度是O(n/p)其中n是哈希过后的最大值,p是我们将要取模的大整数

Snowflake Snow Snowflakes

题目链接:[http://poj.org/problem?id=3349]

实际上看到这个题目我第一秒想到的是Snow Halation

简单翻译


我们要寻找相同的雪花

雪花有六个边,边长只要按顺时针或者逆时针顺序比对出来任意一个相同我们就说两个雪花相同(开头不一定在第一个数

简单思路


很明显,这是一道哈希表的问题,但是我们应当注意的是我们需要创建一个哈希函数

首先因为有多个物品,那么求和是肯定的,但是还是有可能产生碰撞,所以我们应当加一个求积的可能,所以我们的哈希函数公式为: \$[J\alpha(x) = \sum{m=0}^\infty \frac{(-1)^m}{m! \Gamma (m + \alpha + 1)} {\left({ \frac{x}{2} h(a)=a1+a2+a3+……+a[n]+a[1a2]a[n]+a[i-n);

程序


#include <cstdio>
#define P 99991// 取与n最接近的质数,以减少碰撞可能
using namespace std;

const int MAXSIZE=110000;// 最大值
int head[MAXSIZE],next[MAXSIZE],snow[MAXSIZE][6],a[6];
// head[i] 哈希后结果为i的表头
// next[i] 链表的下一个项
//snow[][6] 储存雪花
// a 读入雪花用
int n;
int cnt1,tot;
//int P=99991;
long long cnt2;
// n 次数
// cnt1,cnt2 哈希函数
int H(int *a){// 哈希函数// 不想解释
    cnt1=0;cnt2=1;
    for(int i=0;i<6;i++){
        cnt1+=a[i];
        cnt1%=P;
        cnt2*=a[i];
        cnt2%=P;
    }
    return (cnt1+cnt2)%P;
}

bool same(int *a,int *b){// 判断是否相同
// 暴力法
    for(int i=0;i<6;i++){//转a的开头点
        for(int j=0;j<6;j++){// 转b的开头点
            bool x=false;
            for(int k=0;k<6;k++){// 顺时针
                if(a[(i+k)%6]!=b[(j+k)%6]) x=true;
            }
            if(!x) return true;
            x=false;
            for(int k=0;k<6;k++){// 逆时针
                if(a[(i+k)%6]!=b[(j-k+6)%6]) x=true;
            } 
            if(!x) return true; 
        }
    }
    return false;
}

bool insert(int *a){// 插入雪花
    int val=H(a);// 求哈希值
    for(int i=head[val];i!=0;i=next[i]){// 遍历链表
        if(same(snow[i],a)) return true;
    }
    tot++;//没有的话新建一个链表并插入
    for(int i=0;i<6;i++) snow[tot][i]=a[i];
    next[tot]=head[val];
    head[val]=tot;
    return false;
}

int main(){
    scanf("%d",&n);// 读入
    for(int i=1;i<=n;i++){
        for(int j=0;j<6;j++)scanf("%d",&a[j]);
        if(insert(a)){// 插入
            printf("Twin snowflakes found.");// 如果有相同的输出相同
            return 0;// 退出程序
        }
    }
    printf("No two snowflakes are alike.");// 如果一直没有相同雪花的话,那么输出没有
}

End


textsms