题目分析

本题要求判断是否存在两个“相似”的雪花，这里的“相似”指的是一个雪花可以通过旋转得到另一个雪花。我们通过将每个雪花旋转后得到其最小表示形式作为唯一标识，使用哈希表存储这些标识，若发现重复则说明存在相似雪花。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL; 

const int N = 110000;
const ULL P = 1003331;  // 用于计算唯一标识的基数

int snow[7], isnow[7];    // 存储雪花的6个数字，isnow为snow的反向
map<ULL, int> snow_map;  // 存储雪花最小表示的唯一标识

// 计算雪花的最小旋转表示（唯一标识）
ULL get_min_rotation(int a[]) {
    int b[13];  // 扩展数组，方便处理旋转（避免取模）
    for (int i = 1; i <= 12; ++i) {
        b[i] = a[(i % N == 0) ? 6 : i % 6];  // 循环取6个元素
    }
    int i = 1, j = 2, k;
    while (i <= 6 && j <= 6) {
        for (k = 0; k < 6 && b[i + k] == b[j + k]; ++k);  // 比较旋转后的数组
        if (k == 6) break;  // 完全相同，找到最小旋转
        // 根据比较结果移动i或j
        b[i + k] > b[j + k] ? i += k + 1 : j += k + 1;
        if (i == j) j++;  // 避免i和j重合
    }
    k = min(i, j);  // 最小旋转的起始位置
    ULL ans = 1;
    for (int i = 1; i <= 6; ++i) {
        ans = ans * P + b[i + k];  // 计算唯一标识（多项式哈希）
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    bool found = false;  // 标记是否找到相似雪花

    for (int i = 0; i < n; ++i) {
        // 读入当前雪花的6个数字
        for (int j = 1; j <= 6; ++j) {
            scanf("%d", &snow[j]);
        }
        // 生成反向雪花（旋转180度）
        for (int j = 1; j <= 6; ++j) {
            isnow[6 - j + 1] = snow[j];
        }

        if (found) continue;  // 已找到相似雪花，跳过后续处理

        // 计算当前雪花的最小旋转标识
        ULL curr = get_min_rotation(snow);
        if (snow_map.count(curr)) {
            found = true;  // 存在重复标识，找到相似雪花
        } else {
            snow_map[curr] = 1;  // 存入哈希表
        }

        // 计算反向雪花的最小旋转标识
        ULL rev = get_min_rotation(isnow);
        if (curr != rev) {  // 若标识不同，检查反向标识是否重复
            if (snow_map.count(rev)) {
                found = true;
            } else {
                snow_map[rev] = 1;
            }
        }
    }

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

代码说明

1. 唯一标识生成：通过get_min_rotation函数，将雪花的6个数字循环旋转，找到字典序最小的旋转作为唯一标识（使用多项式哈希计算）。
2. 反向雪花处理：将雪花数组反向后计算其最小旋转标识，若与原标识不同，则需额外检查反向标识是否重复。
3. 哈希表存储：使用map存储每个雪花的唯一标识，通过count方法快速判断是否存在重复标识，从而确定是否找到相似雪花。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL; 
const int N=110000;
const ULL P=1003331;
int snow[7],isnow[7];
map <ULL , int >s;
ULL get_min(int a[])
{
    int b[13];
    for(int i=1;i<=12;i++)b[i]=a[(i%6==0)?6:i%6];
    int i=1,j=2,k;
    while(i<=6&&j<=6)
    {
        for(k=0;k<6 && b[i+k]==b[j+k] ;k++);
        if(k==6)break;
        b[i+k]>b[j+k]?i+=k+1:j+=k+1; 
        if(i==j)j++;
    }
    k=min(i,j);
    ULL ans=1;
    for(int i=1;i<=6;i++)ans=ans*P+b[i+k];
    return ans;
}
int main()
{
    int n;scanf("%d",&n);
    bool bk=False;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=6;j++)scanf("%d",&snow[j]),isnow[6-j+1]=snow[j];
        if( bk) continue;
        ULL x=get_min(snow);
		if(s[x]>0) bk=True; else s[x]++;  
        ULL y=get_min(isnow); 
        if(x!=y) { if(s[y]>0) bk=True; else s[y]++;  }
        
    }
    
    if(bk)printf("Twin snowflakes found.\n");
    else printf("No two snowflakes are alike.\n");
    return 0;
}