「SPOJ 4354」Snowflakes - Hash

发表于 分类于 ， 阅读次数： Disqus：

题意描述

SPOJ 链接

有 \(n (n \le 10^5)\) 个雪花。每个雪花是 \(6\) 个数组成的一个环。若两个环经过旋转（也可不旋转）后环上数字相等，则两个雪花相同。若两个环顺时针和逆时针数字相同则两个环也相同。判断是否有相同的雪花。

解题思路

这道题我们可以利用 Hash 判断两个环是否相等。由于一个雪花的 \(6\) 个数有顺序，我们可以先生成 \(6\) 个 Hash 值 \(\text{list}_i\) 表示顺序。每个雪花的 Hash 值为 \(\sum_{i = 1}^n{\text{list}_i a_i}\)。对于每个雪花，我们将其的顺时针和逆时针两种情况旋转 \(6\) 次，每个雪花用 unordered_map 存下 \(12\) 个 Hash 值，然后直接利用 unordered_map 判重即可。时间复杂度为 \(O(n)\)

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <random>
#include <vector>
#include <unordered_map>

const int MAXL = 1e7;

int main() {
    int n;

    scanf("%d", &n);

    std::mt19937 rng(std::random_device{}());
    auto rand = [&]() -> unsigned long long { return (1ull << (rng() % 31)) ^ rng(); };

    std::vector<unsigned long long> hash(MAXL + 1);
    for (int i = 0; i <= MAXL; i++) hash[i] = rand();
    std::vector<unsigned long long> list(6);
    for (int i = 0; i < 6; i++) list[i] = rand();

    std::unordered_map<unsigned long long, bool> vis;
    for (int i = 0; i < n; i++) {
        std::vector<int> a(12);
        for (int i = 0; i < 6; i++) {
            scanf("%d", &a[i]);
            a[i + 6] = a[i];
        }

        for (int j = 0; j < 6; j++) {
            unsigned long long res = 0;
            for (int k = 0; k < 6; k++) res += hash[a[j + k]] * list[k];
            if (vis[res]) {
                puts("Twin snowflakes found.");
                return 0;
            } else if (j == 0) vis[res] = true;
        }
        for (int j = 0; j < 6; j++) {
            unsigned long long res = 0;
            for (int k = 0; k < 6; k++) res += hash[a[j + 5 - k]] * list[k];
            if (vis[res]) {
                puts("Twin snowflakes found.");
                return 0;
            } else if (j == 0) vis[res] = true;
        }
    }

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

    return 0;
}