题目链接

算法竞赛进阶指南-51.雪花雪花雪花

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

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

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

例如 $a_{i,1},a_{i,2},…,a_{i,6}$ 和 $a_{i,2},a_{i,3},…,a_{i,6}，a_{i,1}$ 就是形状相同的雪花。

$a_{i,1},a_{i,2},…,a_{i,6}$ 和 $a_{i,6},a_{i,5},…,a_{i,1}$ 也是形状相同的雪花。

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

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

输入格式

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

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

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

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

输出格式

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

No two snowflakes are alike.

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

Twin snowflakes found.

数据范围

$1 \le N \le 100000$,
$0 \le a_{i,j} <10000000$

输入样例：

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

输出样例：

Twin snowflakes found.

Method : Hash

不难观察到，对于两片形状相同的雪花，其相邻差值绝对值、总和、乘积是一样的。
因此可以计算相邻差值绝对值、总和、乘积，来作为雪花的唯一标识，作为hash表的判重依据。

#include <unordered_map>
#include <map>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

const int MOD = 13331;   // 不加MOD也可以

struct SnowFlake {
    LL dif = 0;  // 相邻差值绝对值
    LL sum = 0;  // 和
    LL prod = 1; // 积
};

struct SnowFlakeHash {
    int operator()(const SnowFlake& p) const {
        return p.dif ^ (p.sum << 1) ^ (p.prod << 2);
    } 
};
struct SnowFlakeEqual {
    bool operator()(const SnowFlake& p1, const SnowFlake& p2) const {
        return p1.dif == p2.dif && p1.sum == p2.sum && p1.prod == p2.prod;
    }
};

int n;
unordered_map<SnowFlake, int, SnowFlakeHash, SnowFlakeEqual> ht;

int main() {
    cin >> n;
    bool flag = false;
    for (int i = 0; i < n; i ++) {
        SnowFlake sf; 
        int a[6];
        for (int j = 0; j < 6; j ++) {
            scanf("%d", &a[j]);
        }
        // 计算相邻差值绝对值、总和、乘积
        for (int j = 0; j < 6; j ++) {
            sf.dif = (sf.dif + abs(a[j % 6] - a[(j - 1 + 6) % 6])) % MOD;
            sf.sum = (sf.sum + a[j]) % MOD;
            sf.prod = (sf.prod * a[j]) % MOD;
        }
        
        if (ht.count(sf)) {
            flag = true;
            cout << "Twin snowflakes found." << endl;
            break;
        }
        ht[sf] ++;
    }
    
    if (flag == false) {
        cout << "No two snowflakes are alike." << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(1)}$，理论上是均摊$O(1)$。

• 空间复杂度：${O(n)}$。

---

最初版，只计算相邻差值和总和不能过最后一个测试点

#include <unordered_map>
#include <map>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

struct SnowFlake {
    LL dif; // 差值绝对值
    LL sum; // 和
};

struct SnowFlakeHash {
    int operator()(const SnowFlake& p) const {
        return p.dif ^ (p.sum << 1);
    } 
};
struct SnowFlakeEqual {
    bool operator()(const SnowFlake& p1, const SnowFlake& p2) const {
        return p1.dif == p2.dif && p1.sum == p2.sum;
    }
};

int n;
unordered_map<SnowFlake, int, SnowFlakeHash, SnowFlakeEqual> ht;

int main() {
    // 计算两两之间的差值， 再计算一个sum
    cin >> n;
    bool flag = false;
    for (int i = 0; i < n; i ++) {
        SnowFlake sf; 
        sf.sum = 0, sf.dif = 0;
        int a[6];
        for (int j = 0; j < 6; j ++) {
            scanf("%d", &a[j]);
        }
        for (int j = 0; j < 6; j ++) {
            sf.dif += abs(a[j % 6] - a[(j - 1 + 6) % 6]);
            sf.sum += a[j];
        }
        // cout << sf.dif << " " << sf.sum << endl;
        if (ht.count(sf)) {
            flag = true;
            cout << "Twin snowflakes found." << endl;
            break;
        }
        ht[sf] ++;
    }
    
    if (flag == false) {
        cout << "No two snowflakes are alike." << endl;
    }
    
    
    return 0;
}

Method：最小表示法