Acwing：137. 雪花雪花雪花（Hash表）

有N片雪花，每片雪花由六个角组成，每个角都有长度。

第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6ai,1,ai,2,…,ai,6。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

例如ai,1,ai,2,…,ai,6ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6，ai,1ai,2,ai,3,…,ai,6，ai,1就是形状相同的雪花。

ai,1,ai,2,…,ai,6ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1ai,6,ai,5,…,ai,1也是形状相同的雪花。

我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。

求这N片雪花中是否存在两片形状相同的雪花。

输入格式

第一行输入一个整数N，代表雪花的数量。

接下来N行，每行描述一片雪花。

每行包含6个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。

同行数值之间，用空格隔开。

输出格式

如果不存在两片形状相同的雪花，则输出：

No two snowflakes are alike.

如果存在两片形状相同的雪花，则输出：

Twin snowflakes found.

数据范围

1≤n≤1000001≤n≤100000,
0≤ai,j<100000000≤ai,j<10000000

输入样例：

2

1 2 3 4 5 6

4 3 2 1 6 5

输出样例：

Twin snowflakes found.

算法：Hash表

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e5+;

const int mod = ;

int arr[], snow[maxn][], head[maxn], Next[maxn];

int tot;

int getHash(int *a) {

    int sum = ;

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

        sum = (sum + a[i]) % mod;       //取模也是一种Hash方法

    }

    return sum;

}

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

    sort(a, a + );

    sort(b, b + );

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

        if(a[i] != b[i]) {

            return false;

        }

    }

    return true;

}

bool insert(int *a) {

    int pos = getHash(a);

    for(int i = head[pos]; i; i = Next[i])  {

        if(equal(snow[i], a)) {

            return true;

        }

    }

    tot++;

    memcpy(snow[tot], a, sizeof(int) * );      //此函数时读一块内存里的数据复制到另一块内存中

    Next[tot] = head[pos];      //连接上一个结点

    head[pos] = tot;            //更新头结点

    return false;

}

int main() {

    int T;

    int mark = ;

    scanf("%d", &T);

    while(T--) {

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

            scanf("%d", &arr[i]);

        }

        if(insert(arr)) {

            mark = ;

            break;

        }

    }

    if(mark) {

        printf("Twin snowflakes found.\n");

    } else {

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

    }

    return ;

}

巴特西