---
title: "雪花雪花雪花"
created: 2025-11-28
tags:
  - 算法
---

# 雪花雪花雪花

## 题目 [雪花雪花雪花](https://www.acwing.com/problem/content/139/)

![[image-fe63f095.png]]

## 思路分析

本来又想故技重施 用find偷懒

但是发现雪花的数目不止2个

它给出n片雪花 问有没有两片是同构的

如果用find的话 得把每个都翻倍 然后每个都对其他n-1个进行find 显然不现实

那这里就很明显得用最小表示法了

把所有的雪花的最小表示法求出来

然后看有没有两片相同

注意有顺时针还有逆时针 不仅得顺序做一遍最小表示法 还得翻转过来 再做一次

然后对于这片雪花取的是俩者的更小值

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int snows[N][6],idx[N];

int n;

bool cmp_array(int a[], int b[])

{

    for (int i = 0; i < 6; i ++ )

        if (a[i] < b[i])

            return true;

        else if (a[i] > b[i])

            return false;

    return false;

}

bool cmp(int a, int b)

{

    return cmp_array(snows[a],snows[b]);

}

void get_min(int *b)

{

    static int a[12];

    for (int i = 0; i < 12; i ++ )

        a[i] = b[i % 6];

    int i = 0, j = 1, k;

    while (i < 6 && j < 6)

    {

        k=0;

        while( k < 6 && a[i + k] == a[j + k])

            k++;

        if (k == 6)

            break;

        if (a[i + k] > a[j + k])

            i += k + 1;

        else

            j += k + 1;

        if (i == j)

            j ++ ;

    }

    k = min(i, j);

    for (i = 0; i < 6; i ++ )

        b[i] = a[i + k];

}

int main()

{

    cin>>n;

    int snow[6], isnow[6];//顺时针 逆时针

    for (int i = 0; i < n; i ++ )

    {

        for (int j = 0, k = 5; j < 6; j ++, k -- )

        {

            scanf("%d", &snow[j]);

            isnow[k] = snow[j];

        }

        get_min(snow);//正着取一遍最小表示法

        get_min(isnow);//逆着也取一遍

        //结果取更小的

        if (cmp_array(snow, isnow))

            memcpy(snows[i], snow, sizeof snow);

        else

            memcpy(snows[i], isnow, sizeof isnow);

        idx[i] = i;

    }

    //因为不好直接两两相比 所以排好序后 两两比（如果有相同的肯定是临近的）

    //二维不太好排序 所以用idx存好索引 根据索引来排序

    sort(idx, idx + n, cmp);

    for (int i = 1; i < n; i ++ )

    {

        //cmp得到的是小于 加个！意味着大于等于

        //若i-1大于等于i 且 i大于等于i-1  表示i=i-1

        if (!cmp(idx[i], idx[i - 1]) && !cmp(idx[i - 1], idx[i]))

        {

            puts("Twin snowflakes found.");

            return 0;

        }

    }

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

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最小表示法|最小表示法]] 🏠 [[00-刷题理模型]] ➡️ [[项链|项链]]