题目描述

有N片雪花，每片雪花由六个角组成，每个角都有长度。

第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

例如ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6，ai,1就是形状相同的雪花。

ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1也是形状相同的雪花。

我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。

求这N片雪花中是否存在两片形状相同的雪花。

输入格式

第一行输入一个整数N，代表雪花的数量。

接下来N行，每行描述一片雪花。

每行包含6个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。

同行数值之间，用空格隔开。

输出格式

如果不存在两片形状相同的雪花，则输出：

No two snowflakes are alike.

如果存在两片形状相同的雪花，则输出：

Twin snowflakes found.

数据范围

1≤n≤100000,
0≤ai,j<10000000

样例

输入样例：

2
1 2 3 4 5 6
4 3 2 1 6 5

输出样例：

Twin snowflakes found.

主要做法:用哈希值表示一片雪花

实现:从每一个角向两边延伸求哈希值,然后用其中最大值来判重(我之前写过一个只求一遍最大值然后延伸的方法，这是有误的，因为一片雪花中可能有重复的值)

神奇代码(最好别这样写，虽然AC了但想法错误)

#include<algorithm>
#include<stdio.h>
#define ll unsigned long long
#define P 131
using namespace std;
ll ans[100001];
int t,n,a[100001][7];
int main(){
    scanf("%d",&n);
    bool flag=false;
    for(int i=1;i<=n;i++){
        int ma=0,wz;
        for(int j=1;j<=6;j++){
            scanf("%d",&a[i][j]);
            if(ma<a[i][j]){
                ma=a[i][j];
                wz=j;
            }
        }
        int k1=wz+7,k2=wz+7;
        ll s1=0,s2=0;//求两次哈希值
        for(int j=1;j<=6;j++){
            if(k1%7==0) k1=1;
            if(k2%7==0) k2=6;
            s1=a[i][k1%7]+s1*P;
            s2=a[i][k2%7]+s2*P;
            k1++,k2--;
        }
        ans[i]=min(s1,s2);//将最小值存入数组
    }
    sort(ans+1,ans+n+1);//排序找相同
    for(int i=1;i<n;i++) if(ans[i]==ans[i+1]){
        flag=true;
        printf("Twin snowflakes found.\n");
        break;
    }
    if(!flag) printf("No two snowflakes are alike.\n");
    return 0;
}

正确代码(临时爆肝写完，出了不少错误，嘤嘤嘤)

#include<algorithm>
#include<stdio.h>
#define ll unsigned long long
#define P 131
using namespace std;
ll ans[100001];
int t,n,a[7];
int main(){
    scanf("%d",&n);
    bool flag=false;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=6;j++) scanf("%d",&a[j]);
        ans[i]=0;
        for(int k=1;k<=6;k++){
            int k1=k+7,k2=k+7,o=6;
            ll s1=0,s2=0;
            while(o--){
                if(k1%7==0) k1=1;
                if(k2%7==0) k2=6;
                s1=a[k1%7]+s1*P;
                s2=a[k2%7]+s2*P;
                k1++,k2--;
            }
            ans[i]=max(max(s1,s2),ans[i]);
        }
    }
    sort(ans+1,ans+n+1);
    for(int i=1;i<n;i++) if(ans[i]==ans[i+1]){
        flag=true;
        printf("Twin snowflakes found.\n");
        break;
    }
    if(!flag) printf("No two snowflakes are alike.\n");
    return 0;
}