这是一份针对 NOI 竞赛选手的标准题解。本题的核心考点在于哈希表的应用与环形序列同构的判定。

一、 题解标准代码 (C++14)

此代码采用拉链法哈希，结合严谨的 12 种同构情况校验。

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

// 哈希表长度选择一个较大的质数，减少碰撞概率
const int MAXN = 100005;
const int MOD = 999983; 

struct Snowflake {
    int len[6];
};

// 存储所有的雪花，雪花以拉链法挂在 hash_table 下
vector<Snowflake> hash_table[MOD];

// 核心判定函数：比较两个雪花是否可能相同
bool is_same(const Snowflake& s1, const Snowflake& s2) {
    for (int i = 0; i < 6; ++i) { // 枚举 s2 的起始位置
        // 情况 1: 顺时针方向旋转
        bool match = true;
        for (int j = 0; j < 6; ++j) {
            if (s1.len[j] != s2.len[(i + j) % 6]) {
                match = false;
                break;
            }
        }
        if (match) return true;

        // 情况 2: 逆时针方向旋转（翻转）
        match = true;
        for (int j = 0; j < 6; ++j) {
            // (i - j + 6) % 6 是逆时针索引处理的技巧
            if (s1.len[j] != s2.len[(i - j + 6) % 6]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

// 设计哈希函数：将6个数映射为一个索引
// 易错点：仅用 Sum 可能会造成大量哈希碰撞，建议结合 Sum 和 XOR 或 Prod
int get_hash(const Snowflake& s) {
    long long sum = 0;
    long long xor_val = 0;
    for (int i = 0; i < 6; ++i) {
        sum += s.len[i];
        xor_val ^= s.len[i];
    }
    // 使用 sum 和 xor 组合减少冲突，最后对大质数取模
    return (int)((sum + xor_val) % MOD);
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    bool found = false;
    for (int i = 0; i < n; ++i) {
        Snowflake current;
        for (int j = 0; j < 6; ++j) {
            scanf("%d", &current.len[j]);
        }

        if (found) continue; // 如果已经找到了，则只读不处理

        int h = get_hash(current);

        // 在对应的哈希桶中查找
        for (const auto& existing : hash_table[h]) {
            if (is_same(current, existing)) {
                found = true;
                break;
            }
        }

        // 若没找到，放入桶中
        if (!found) {
            hash_table[h].push_back(current);
        }
    }

    if (found) {
        printf("Twin snowflakes found.\n");
    } else {
        printf("No two snowflakes are alike.\n");
    }

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度

• 读取与哈希计算：$O(n \times 6)$。
• 哈希冲突判定：
  • 平均情况：假设哈希函数足够随机且均匀，每个桶的平均长度为 $n / MOD$。每次插入时进行 is_same 比较，该函数常数为 12。总期望复杂度为 $O(n \times 12 \times \frac{n}{MOD})$。当 $MOD \approx n$ 时，接近 $O(n)$。
  • 最坏情况：所有雪花的特征值全部相同（碰撞到同一个桶），复杂度退化为 $O(n^2)$。在 NOI 竞赛中，若遇到精心构造的数据，需小心。
• 结论：在常规数据下，该算法表现为 $O(n)$，能轻松通过 $10^5$ 的数据。

2. 空间复杂度

• 存储开销：hash_table 存储了 $n$ 个 Snowflake 结构体，每个结构体 6 个 int。
• 分析：$10^5 \times 6 \times 4$ 字节 $\approx 2.4$ MB。加上 vector 的额外指针开销，总空间远小于题目常见的 128MB 或 256MB 限制。

三、 时间复杂度优化建议

1. 最小表示法 (Minimal Representation)： 对于每个雪花序列，求出其字典序最小的循环同构串。例如 3 4 1 2 的最小表示是 1 2 3 4。
   • 将每片雪花的正向和反向序列共 12 种情况中，字典序最小的那一个作为该雪花的“标准态”。
   • 优化后：可以直接对这 $n$ 个“标准态”序列进行排序 ($O(n \log n)$) 或直接存入哈希表，省去了 is_same 中繁琐的循环比对。
2. 更强的哈希函数： 为了防止被 hack（最坏情况），可以使用双哈希（Double Hashing）或者使用 std::array 配合更复杂的特征值。
3. 手写链表： 在 NOI 这种对时间极其敏感的比赛中，使用 vector 可能会有额外的常数开销。可以使用静态数组模拟链表（Head/Next 数组）来进一步压低常数。

四、 读题理解关键词总结

在处理此类“序列判定”或“同构”题目时，务必关注以下词汇：

• "Order around" (环形顺序)：暗示这是一个环，首尾相接。
• "Clockwise or counter-clockwise" (顺时针或逆时针)：暗示序列可以反转 (Reverse)。
• "Start from any" (任意起始)：暗示序列可以循环移位 (Rotation)。
• "Corresponding" (对应相同)：意味着只要有一种位置对应的可能性成立，两个个体即为相同（无需所有排列组合）。
• $n \le 100,000$：该数量级意味着你的算法必须优于 $O(n^2)$。任何包含双重 $n$ 循环的暴力逻辑都必须通过哈希或排序来剪枝。