poj3349 散列表（hash）

就是散列表的应用，把每片哈希值相同的雪花排到一条链上去即可，每片雪花x的哈希值 hash(x)=sum(x的六角)+mul(x的六角)，会爆int

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100005

#define mod 99991

using namespace std;

struct Edge{

    int snow[],next;

}edge[maxn];

int n,tot,head[maxn];

int H(int *a){

    int sum=,mul=;

    for(int i=;i<;i++){

        sum=(sum+a[i])%mod;

        mul=((long long)mul*a[i])%mod;

    }

    return (mul+sum)%mod;

}

bool equal(int *a,int *b){//比较两片雪花是否相同

    for(int i=;i<;i++)

        for(int j=;j<;j++){

            bool eq=;

            for(int k=;k<;k++)

                if(a[(i+k)%]!=b[(j+k)%]) eq=;

            if(eq) return ;

            eq=;

            for(int k=;k<;k++)

                if(a[(i+k)%]!=b[(j-k+)%]) eq=;

            if(eq) return ;

        }

    return ;

}

void addedge(int u,int *a){

    ++tot;

    for(int i=;i<;i++) edge[tot].snow[i]=a[i];

    edge[tot].next=head[u];

    head[u]=tot;

}

bool insert(int *a){

    int val=H(a);//找到对应的那个散列

    for(int i=head[val];i;i=edge[i].next)//先看散列里面是否有相同的雪花

        if(equal(edge[i].snow,a)) return ;

    addedge(val,a);

    return ;

}

int main(){

    scanf("%d",&n);

    int a[];

    for(int i=;i<=n;i++){

        for(int j=;j<;j++) scanf("%d",&a[j]);

        if(insert(a)){

            puts("Twin snowflakes found.");

            return ;

        }

    }

    puts("No two snowflakes are alike.");

    return ;

}