题目分析

这道题目要求我们判断在给定的多片雪花中是否存在两片相同的雪花。每片雪花由6个分支的长度组成，顺序可以是顺时针或逆时针，并且可以从任意分支开始。因此，判断两片雪花是否相同需要考虑所有可能的旋转和反转情况。

输入输出说明

• 输入：第一行是一个整数n（0 < n ≤ 100000），表示雪花的数量。接下来的n行，每行包含6个整数，表示一片雪花的6个分支的长度。
• 输出：如果存在两片相同的雪花，输出"Twin snowflakes found."；否则输出"No two snowflakes are alike."。

解题思路

1. 哈希表存储：使用哈希表来存储已经处理过的雪花，以便快速查找是否有重复。
2. 旋转和反转处理：对于每片雪花，生成其所有可能的旋转和反转形式（共12种情况），并检查这些形式是否已经在哈希表中存在。
3. 哈希函数设计：设计一个简单的哈希函数，将雪花的分支长度之和作为哈希值，以减少冲突。

标程代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int H = 1200007;
const int maxn = 1200010;

struct Node {
    int num[6];
    int next;
};

Node p[maxn];
int Hash[H];
int cnt;

void init() {
    cnt = 0;
    memset(Hash, -1, sizeof(Hash));
}

bool compare(int *a, int *b) {
    for (int i = 0; i < 6; i++) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

int getHash(int *a) {
    int hash = 0;
    for (int i = 0; i < 6; i++) {
        hash += a[i];
    }
    return hash % H;
}

void addHash(int *a, int hashNum) {
    for (int i = 0; i < 6; i++) {
        p[cnt].num[i] = a[i];
    }
    p[cnt].next = Hash[hashNum];
    Hash[hashNum] = cnt;
    cnt++;
}

bool searchHash(int *a) {
    int hashNum = getHash(a);
    for (int i = Hash[hashNum]; i != -1; i = p[i].next) {
        if (compare(a, p[i].num)) {
            return true;
        }
    }
    addHash(a, hashNum);
    return false;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        init();
        bool found = false;
        for (int i = 0; i < n; i++) {
            int snowflake[2][12];
            for (int j = 0; j < 6; j++) {
                scanf("%d", &snowflake[0][j]);
                snowflake[0][j + 6] = snowflake[0][j];
            }
            for (int j = 0; j < 6; j++) {
                snowflake[1][j] = snowflake[1][j + 6] = snowflake[0][5 - j];
            }
            if (!found) {
                for (int j = 0; j < 6; j++) {
                    if (searchHash(snowflake[0] + j) || searchHash(snowflake[1] + j)) {
                        found = true;
                        break;
                    }
                }
            }
        }
        if (found) {
            printf("Twin snowflakes found.\n");
        } else {
            printf("No two snowflakes are alike.\n");
        }
    }
    return 0;
}

代码解释

1. 初始化：init函数初始化哈希表和计数器。
2. 比较函数：compare函数比较两个雪花的分支长度是否完全相同。
3. 哈希函数：getHash函数计算雪花的哈希值，使用分支长度之和取模。
4. 添加和查找哈希表：addHash和searchHash函数分别用于向哈希表中添加雪花和查找雪花。
5. 主函数：读取输入数据，处理每片雪花的所有旋转和反转形式，使用哈希表检查是否有重复，最后输出结果。

该算法高效且准确，适用于题目给定的数据范围。通过哈希表快速查找和比较，确保在大量数据下仍能高效运行。