形式化题目

把每片雪花看成一个六元组 $f = (f_0, f_1, \dots, f_5)$，其中 $0 \leqslant f_t < 10^7$。定义两种改写方式：

• 旋转：$\rho_k(f) = (f_k, f_{k+1}, \dots, f_{k+5})$，下标对 6 取模，$k = 0, 1, \dots, 5$；
• 翻转：$\mathrm{rev}(f) = (f_5, f_4, \dots, f_0)$。

两片雪花形状相同，当且仅当其中一片可以通过若干次旋转和翻转变成另一片。等价地，定义等价类

则 $f \sim g \iff g \in S(f)$。

给定 $n$ 个六元组 $f_1, \dots, f_n$（$1 \leqslant n \leqslant 10^5$），判断是否存在 $i \ne j$ 使 $f_i \sim f_j$。这等价于问：这 $n$ 个等价类是否两两不同；存在则输出 Twin snowflakes found.，不存在则输出 No two snowflakes are alike.。

正解

思路

朴素做法与瓶颈

最直接的想法是枚举所有雪花对 $(i, j)$，对每一对枚举 12 种对齐方式，逐位比较 6 个角：

$n = 10^5$ 时这是 $3.6 \times 10^{11}$ 次基本操作（$\binom{10^5}{2} \times 12 \times 6 = 3.599964 \times 10^{11}$），即使每次只要 1 ns 也要约 6 分钟，远超 1000 ms。

问题出在把"形状"当成了两片雪花之间的关系来验证。其实形状是每片雪花自己的属性：第 $i$ 片的 12 种写法只跟第 $i$ 片有关，却在朴素做法里被重复展开、重复比较了近 $n$ 次。

只要给每片雪花先算出一个"形状编号"，判重就退化成集合判重，配对彻底消失。

关键观察：等价类只需要一个代表元

性质 1（等价类闭合）：若 $g \in S(f)$，则 $S(g) = S(f)$。

因为 $\rho_a \circ \rho_b = \rho_{a+b}$、$\mathrm{rev} \circ \rho_k = \rho_{6-k} \circ \mathrm{rev}$，"旋转 + 翻转"生成的变换群是闭合的：对 $f$ 再做一次群变换，结果仍然落在 $S(f)$ 里；两边互相包含即相等。

也就是说，同形状的雪花拥有完全相同的旋转集合。

性质 2（最小表示是精确指纹）：定义

（按六元组字典序取最小的那个）。那么

• 正向 $(\Rightarrow)$：若 $f \sim g$，由性质 1 有 $S(f) = S(g)$，两边取最小值自然相等。这保证不漏判。
• 反向 $(\Leftarrow)$：设 $t = \mathrm{key}(f) = \mathrm{key}(g)$。由 $t \in S(f)$ 和性质 1 得 $S(t) = S(f)$，同理 $S(t) = S(g)$，所以 $S(f) = S(g)$，即 $f \sim g$。这保证不误判。

反向这一步是关键：它说明最小表示是精确指纹，不像数值哈希那样需要讨论碰撞概率。两片雪花的 12 种写法只要有一个重合，它们的最小表示就必然相等。

样例推演

下面把样例第一片雪花 1 2 3 4 5 6 的全部 12 种等价写法列出（k 表示从第 k 个角开始读），加粗的是最小表示。

最小表示（形状指纹）是 1 2 3 4 5 6。

第二片雪花 4 3 2 1 6 5 表面上和第一片毫无共同之处，但它的第 逆时针 k=2 种写法恰好就是 1 2 3 4 5 6：

两片的最小表示都是 1 2 3 4 5 6，因此形状相同。

这两张表要一起看：第一张说明"12 种写法里挑最小"这个动作，第二张说明"看起来不同的两片可能挑出同一个最小表示"。注意逆时针也要取满 6 个起点——只取顺时针 6 个会漏掉第二片这种情况，这是本题最容易写错的地方。

算法流程

按输入顺序扫描，维护一个哈希集合 seen：

1. 读入一片雪花，算它的最小表示 key；
2. 若 key 已经在 seen 里，说明前面出现过同形状雪花，输出 Twin snowflakes found. 并立即结束（剩余输入不必再读）；
3. 否则把 key 放进 seen，继续下一片；
4. 循环正常结束都没命中，说明所有等价类互不相同，输出 No two snowflakes are alike.。

下表演示样例在 seen 上的推进过程。表格的行按输入顺序排列，"桶内已有"表示该最小表示之前是否被别的雪花占据：

第一片进入桶后，第二片算出同一个最小表示，查表立即命中——整个过程只做了两次 $O(1)$ 的集合操作。

实现细节

• 用 tuple 而不是 list 作为集合元素：元组可哈希，可以直接放进 set。
• 切片拼接 f[k:] + f[:k] 恰好就是 $\rho_k(f)$；翻转用 f[::-1]。
• 12 个候选里允许出现重复元组（0 0 0 0 0 0、1 2 1 2 1 2 这类自带对称性的雪花，12 个候选里只有 1 个、2 个不同写法），min 对重复不敏感，不必先去重——去重反而更慢。
• 读入用 islice(data, 6) 按 token 个数取 6 个整数，不依赖换行位置，输入被压成一行也能正确工作。

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:28
# update_at: 2026-10-01 11:36

import sys
from itertools import islice

TWIN = "Twin snowflakes found."
ALIKE = "No two snowflakes are alike."


def shape_key(flake: tuple[int, ...]) -> tuple[int, ...]:
    """雪花的最小表示：顺时针 6 个旋转 + 逆时针 6 个旋转里最小的那个六元组。

    形状相同的两片雪花，12 个旋转组成的集合完全相同，取最小值后必然相等；
    反过来最小值相等就说明两个集合有公共元素，即形状相同。所以最小表示是
    “形状”的精确指纹，不含哈希碰撞。元组比较由 CPython 在 C 层完成，
    比在 Python 里手写数值哈希还快。
    """
    reverse = flake[::-1]                                        # 逆时针方向读到的序列
    return min(
        [flake[k:] + flake[:k] for k in range(6)]                # 顺时针 6 个旋转
        + [reverse[k:] + reverse[:k] for k in range(6)]          # 逆时针 6 个旋转
    )


def solve() -> None:
    data = map(int, sys.stdin.buffer.read().split())
    n = next(data)

    seen: set[tuple[int, ...]] = set()
    for _ in range(n):
        flake = tuple(islice(data, 6))  # 每行 6 个角，正好构成一片雪花
        key = shape_key(flake)
        if key in seen:
            print(TWIN)
            return
        seen.add(key)
    print(ALIKE)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:26
 * update_at: 2026-10-06 15:26
 */
// 雪花判重：把每片雪花 12 种写法（顺时针 6 个起点 + 逆时针 6 个起点）
// 规范化成字典序最小的六元组作为形状指纹，指纹相同当且仅当两片雪花同形状。
// 用哈希集合扫描判重，O(n)。

#include <cstdio>
#include <set>

typedef long long ll;

const int MAXN = 100005;

int n;
ll a[MAXN][6];  // a[i][j] 表示第 i 片雪花第 j 个角的长度（下标 0..5）

// 形状指纹：六元组最小表示，自定义比较直接放进 set
struct SnowKey {
    ll v[6];
};

bool operator<(const SnowKey &x, const SnowKey &y) {
    for (int i = 0; i < 6; ++i) {
        if (x.v[i] != y.v[i]) return x.v[i] < y.v[i];
    }
    return false;
}

std::set<SnowKey> seen;  // 已经出现过的形状指纹集合

// 计算第 idx 片雪花的最小表示，枚举 12 种写法取字典序最小
SnowKey make_key(int idx) {
    SnowKey best;
    bool first = true;
    // dir = 0 顺时针，dir = 1 逆时针；k 表示从第 k 个角开始读
    for (int dir = 0; dir < 2; ++dir) {
        for (int k = 0; k < 6; ++k) {
            SnowKey cur;
            for (int t = 0; t < 6; ++t) {
                int j;
                if (dir == 0)
                    j = (k + t) % 6;         // 顺时针：从 k 往后读
                else
                    j = (k - t + 6) % 6;     // 逆时针：从 k 往前读
                cur.v[t] = a[idx][j];
            }
            if (first || cur < best) {       // 取 12 种写法里字典序最小的
                best = cur;
                first = false;
            }
        }
    }
    return best;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 6; ++j) scanf("%lld", &a[i][j]);
        SnowKey key = make_key(i);
        // 指纹已经出现过，说明前面存在同形状的雪花
        if (seen.count(key)) {
            printf("Twin snowflakes found.\n");
            return 0;
        }
        seen.insert(key);
    }
    printf("No two snowflakes are alike.\n");
    return 0;
}

复杂度

时间复杂度 $O(n)$。每片雪花做常数次工作：构造 12 个候选六元组（12 次长度 6 的切片拼接）、取最小值、一次集合查询/插入。集合操作均摊 $O(1)$。整体 $O(n)$，代入 $n = 10^5$ 是 $10^5$ 量级。

空间复杂度 $O(n)$。seen 最多存 $n$ 个六元组。

实测（20 组真实数据全部通过）：$n = 10^5$ 的四组满规模数据耗时 0.20–0.25 s、峰值内存约 87 MB，均在 1000 ms / 128 MB 之内。

对比朴素做法：$n = 10^5$ 时需要约 $\binom{10^5}{2} \times 12 \times 6 \approx 3.6 \times 10^{11}$ 次操作，不可行。

总结

• 题目的核心是把"两两比较形状"转化为"给每片雪花算一个形状编号，再判重"。
• 形状编号取 12 种写法（顺时针 6 个 + 逆时针 6 个）中的字典序最小者，由性质 1、2 可知它是等价类的精确代表元，既不会漏判也不会误判。
• 翻转必须算进去，且逆时针方向要取满 6 个起点；漏掉任何一个都会在"只有翻转才相同"的数据上给出错误答案。
• 时间 $O(n)$、空间 $O(n)$，$n = 10^5$ 时 Python 也能轻松通过。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7
8输入 n 片雪花
`- 朴素做法的瓶颈: 两两比较 => O(n^2)，n=1e5 时约 3.6e11 次操作
   `- 关键观察: 形状是雪花自己的属性，不是两片之间的关系
      |- 每片雪花展开 12 种写法 (顺时针 6 + 逆时针 6)
      |  `- 取字典序最小 => 最小表示 key = 形状的唯一指纹
      `- 用哈希集合扫描判重
         |- key 已出现  => Twin snowflakes found.  (立即输出)
         `- 扫描结束    => No two snowflakes are alike.

先看瓶颈节点：它说明了为什么必须放弃配对。再看中间分支：最小表示把 $O(n^2)$ 的"比较关系"降维成 $O(n)$ 的"本地计算 + 集合查询"。最后两个叶子对应代码里的两条出口——if key in seen: print(TWIN); return 与循环结束后的 print(ALIKE)。