0x14 Hash

雪花雪花雪花

有 片雪花，每片雪花由六个角组成，每个角都有长度。
第 片雪花六个角的长度从某个角开始顺时针依次记为 。
因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。
例如 和 就是形状相同的雪花。
和 也是形状相同的雪花。
我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。
求这 片雪花中是否存在两片形状相同的雪花。
输入格式
第一行输入一个整数 ，代表雪花的数量。
接下来 行，每行描述一片雪花。
每行包含 个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。
同行数值之间，用空格隔开。
输出格式
如果不存在两片形状相同的雪花，则输出：
No two snowflakes are alike.
如果存在两片形状相同的雪花，则输出：
Twin snowflakes found.
数据范围
,

输入样例：

2
1 2 3 4 5 6
4 3 2 1 6 5

输出样例：

Twin snowflakes found.

设计一个哈希函数，尽可能的降低碰撞率。

const int P = 99991;
int H(){
    int sum = 0,mul = 1;
    for(int i=0;i<6;i++){
        sum = (sum + a[i]) % P;
        mul = 1ll * mul * a[i] % P;
    }
    return (sum + mul) % P;
}

上述哈希函数对雪花中的 6 个值的和与积加起来取模。为什么 P = 99991，因为这是一个不怎么大的质数，可以方便的用数组去存每一个雪花。
因此，计算每个雪花的哈希值，并插入该哈希值对应的链表中去。如果链表中已有雪花，那么就一一对比看是否存在两个一样的雪花。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,tot,P = 99991;
int snow[N][6],head[N],nxt[N];
int a[6];
int H(){
    int sum = 0,mul = 1;
    for(int i=0;i<6;i++){
        sum = (sum + a[i]) % P;
        mul = 1ll * mul * a[i] % P;
    }
    return (sum + mul) % P;
}
bool equal(int *a,int *b){
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            bool eq = 1;
            for(int k = 0;k < 6;k++){
                if(a[(i+k) % 6] != b[(j+k) % 6]) eq = 0;
            }
            if(eq)return 1;
            eq = 1;
            for(int k = 0;k < 6;k++){
                if(a[(i+k) % 6] != b[(j - k + 6) % 6])eq = 0;
            }
            if(eq)return 1;
        }
    }
    return 0;
}
bool insert(){
    int val = H();
    //cout << val << endl;
    for(int i=head[val];i;i=nxt[i]){
        if(equal(snow[i],a))return 1;
    }
    ++tot;
    memcpy(snow[tot],a,6 * sizeof(int));
    nxt[tot] = head[val];
    head[val] = tot;
    return 0;
}
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()){
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
    return 0;
}

另外一种实现风格，采用 STL 中的 array 对象，并结合 unordered_map 哈希表。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 100010, P = 99991; 
int n;
array<int, 6> a;
unordered_map<int, vector<array<int, 6>>> mp;
int H(){
    int sum = 0, mul = 1;
    for(int i = 0; i < 6; i++){
        sum = (sum + a[i]) % P;
        mul = 1ll * mul * a[i] % P;
    }
    return (sum + mul) % P;
}
bool equal(array<int, 6> &a, array<int, 6> &b) {
    rep(i, 0, 5) {
        rep(j, 0, 5) {
            bool eq = true;
            rep(k, 0, 5) {
                if(a[(i + k) % 6] != b[(j + k) % 6]) eq = false;
            }
            if(eq) return true;
            eq = true;
            rep(k, 0, 5) {
                if(a[(i + k) % 6] != b[(j - k + 6) % 6]) eq = false;
            }
            if(eq) return true;
        }
    }
    return false;
}
bool insert() {
    int val = H();
    for(auto &b : mp[val]) {
        if(equal(a, b)) return true;
    }
    mp[val].emplace_back(a);
    return false;
}
int main(){
    scanf("%d", &n);
    rep(i, 1, n) {
        rep(j, 0, 5) scanf("%d", &a[j]);
        if(insert()){
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
    return 0;
}