题目描述

blablabla

样例

blablabla

算法1

(暴力枚举)

1.建立hash函数（积和和的和）
2.根据hash值构建一个从hash值到雪花的映射；
3.这里我们用一个Sn表示雪花结构体，里面是一个小数组，然后建立一个Sn类型的vector数组，里面同一下标表示hash值相同的多个Sn
4.和hash值相同的一一比较，看是否有相同
5.比较函数写法：枚举起点，分别顺时针和逆时针来一一对照
6.比较的部分可以简化一些，因为我这里是正反都比较了，实际上如果有相同部分，
那么a串只要枚举顺时针，和b串的顺逆时针都比较就可以了，因为相同情况下，两个串同时反转依然是相同的
blablabla

时间复杂度

参考文献

C++ 代码

//主要参考lyd GitHub上的代码
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,ll> P;
const int maxn=200000+100;
const ll mod=99991;  //为什么取这个更合适？

ll n,a[maxn],b[7],c[maxn];

bool f=1;
ll temp;

struct  Sn
{
    ll s[6];/* data */
};

vector<Sn> g[maxn];

ll ha() {
    ll sum=0,mul=1;
    for(int i=1;i<=6;i++) {
        sum=(sum+b[i])%mod;
        mul=mul*b[i]%mod;
    }
    sum=(sum+mul)%mod;
    return sum;
}
//1表示不相同
bool cmp(Sn c) {
    /*
        b[1]~b[6]
        c.s[0]~c.s[5]
    */
    for(int i=1;i<=6;i++) {
        for(int j=0;j<6;j++) {
            bool v1=1,v2=1;
            for(int k=0;k<=5;k++) {
                if(b[(i-1+k)%6+1] != c.s[(j+k)%6])  v1=0;
                if(b[(i-1+k)%6+1] != c.s[(j-k+6)%6] ) v2=0;
            }
            if(v1||v2) return 0;

            v1=1,v2=1;
            for(int k=0;k<=5;k++) {
                if(b[(i-1-k+6)%6+1] != c.s[(j-k+6)%6])  v1=0;
                if(b[(i-1-k+6)%6+1] != c.s[(j+k)%6])  v2=0; 
            } 
            if(v1||v2) return 0; 
        } 
    }
    return 1;
}

bool pd() {
    bool ff=0;
    for(int i=0;i<g[temp].size();i++) {
        if(cmp(g[temp][i])) continue; //b不相同
        else ff=1; 
    }
    Sn sn; 
    memcpy(sn.s,b+1,sizeof(sn.s));  
    g[temp].push_back(sn);
    if(ff) return 1;
    return 0;

}

int main() {
  //  freopen("1.in","r",stdin);
    cin>>n;
    bool you=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=6;j++) {
            cin>>b[j];
        }
        temp=ha(); 
        if(pd()) you=1; 
    }    
    if(you) cout<<"Twin snowflakes found."<<endl;
    else cout<<"No two snowflakes are alike."<<endl;
    return 0;
}