哈希 | hz2016Blog

Snowflake Snow Snowflakes
这题的话就是明显可以用哈希表来做啦，对于两篇形状相同的雪花，那么他们的乘积也是一样的，但是又为了避免偶然，所以哈希函数的计算中增加了他们的和， $Hash(x)=sum(x)+mul(x)$ 这样就可以很好的做统计了。

#include<set>
#include<map>
#include<list>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define qread(x) x=read()
#define mes(x,y) memset(x,y,sizeof(x))
#define mpy(x,y) memcpy(x,y,sizeof(x))
#define Maxn 100000
#define Maxs 6
#define HashMod 99991
#define INF 2147483647
inline int read(){
    int f=1,x=0;char ch;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
int tot,snow[Maxn+1][Maxs],head[Maxn+1],next[Maxn+1];
int Hash(int *a){
    int sum=0,mul=1;
    for(int i=0;i<Maxs;i++){
        sum=(sum+a[i])%HashMod;
        mul=(long long)mul*a[i] % HashMod;
    }
    return (sum+mul)%HashMod;
}
bool bk;
bool Check(int *a,int *b){
    for(int i=0;i<Maxs;i++){
        for(int j=0;j<Maxs;j++){
            bk=true;
            for(int k=0;k<Maxs;k++){
                if(a[(i+k)%Maxs]!=b[(j+k)%Maxs]){
                    bk=false;break;
                }
            } 
            if(bk==true)return true;
            bk=true;
            for(int k=0;k<Maxs;k++){
                if(a[(i+k)%Maxs]!=b[(j-k+Maxs)%Maxs]){
                    bk=false;break;
                }
            } 
            if(bk==true)return true;
        }
    }
    return false;
}
int tmp;
bool insert(int *a){
    tmp=Hash(a);
    for(int k=head[tmp];k>0;k=next[k]){
        if(Check(snow[k],a)==true){
            return true;
        }
    }
    tot++;
    mpy(snow[tot],a);
    next[tot]=head[tmp];
    head[tmp]=tot;
    return false;
}
int n,a[Maxs];
int main(){
    //freopen("poj-3349.in","r",stdin);
    //freopen("poj-3349.out","w",stdout);
    qread(n);
    tot=0;
    for(int i=1;i<=n;i++){
        int a[Maxs];
        for(int j=0;j<Maxs;j++)qread(a[j]);
        if(insert(a)==true){
            printf("Twin snowflakes found.");
            return 0;
        }
    }
    printf("No two snowflakes are alike.");
}

#include<set>

#include<map>

#include<list>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define qread(x) x=read()

#define mes(x,y) memset(x,y,sizeof(x))

#define mpy(x,y) memcpy(x,y,sizeof(x))

#define Maxn 100000

#define Maxs 6

#define HashMod 99991

#define INF 2147483647

inline int read(){

int f=1,x=0;char ch;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return f*x;

}

int tot,snow[Maxn+1][Maxs],head[Maxn+1],next[Maxn+1];

int Hash(int *a){

int sum=0,mul=1;

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

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

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

}

return (sum+mul)%HashMod;

}

bool bk;

bool Check(int *a,int *b){

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

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

bk=true;

for(int k=0;k<Maxs;k++){

if(a[(i+k)%Maxs]!=b[(j+k)%Maxs]){

bk=false;break;

}

if(bk==true)return true;

bk=true;

for(int k=0;k<Maxs;k++){

if(a[(i+k)%Maxs]!=b[(j-k+Maxs)%Maxs]){

bk=false;break;

}

if(bk==true)return true;

}

return false;

}

int tmp;

bool insert(int *a){

tmp=Hash(a);

for(int k=head[tmp];k>0;k=next[k]){

if(Check(snow[k],a)==true){

return true;

}

tot++;

mpy(snow[tot],a);

next[tot]=head[tmp];

head[tmp]=tot;

return false;

}

int n,a[Maxs];

int main(){

//freopen("poj-3349.in","r",stdin);

//freopen("poj-3349.out","w",stdout);

qread(n);

tot=0;

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

int a[Maxs];

for(int j=0;j<Maxs;j++)qread(a[j]);

if(insert(a)==true){

printf("Twin snowflakes found.");

return 0;

}

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

}

分类：哈希

兔子与兔子

「算进」[基构]HASH

Snowflake Snow Snowflake