SP4354 TWINSNOW - Snowflakes

最小表示法+hash

#include<cstdio>
#include<iostream>
#include<map>
#define ull unsigned long long
using namespace std;
const int BASE=131;
map<ull,int>m;
int a[8],n,s1[8],s2[8],flag;
int Min(int *s){
    int i=1,j=2,k=0;
    while(i<=6&&j<=6){
        while(s[(i+k)%6]==s[(j+k)%6]&&k<=6) k++;
        if(k==7) return i;
        if(s[i+k]>s[j+k]) i=i+k+1;
        else j=j+k+1;
        if(i==j) j++;
        k=0;
    }
    return i>j?j:i;
}
void Swap(int &x,int &y){ x^=y; y^=x; x^=y; }
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=6;++j) scanf("%d",&a[j]);//正着做一遍
        int pos1=Min(a),cnt=0; ull hash1=0,hash2=0;
        for(int j=pos1;j<=6;++j) s1[++cnt]=a[j],hash1=BASE*hash1+a[j];
        for(int j=1;j<pos1;++j) s1[++cnt]=a[j],hash1=BASE*hash1+a[j];//把正序结果存入s1,hash1
        for(int j=1;j<=3;++j) Swap(a[j],a[6-j+1]);//倒着再做一遍
        int pos2=Min(a);//最小表示法，不解释
        cnt=0;
        for(int j=pos2;j<=6;++j) s2[++cnt]=a[j],hash2=BASE*hash2+a[j];
        for(int j=1;j<pos2;++j) s2[++cnt]=a[j],hash2=BASE*hash2+a[j];//把逆序结果存入s2,hash2
        for(int j=1;j<=6;++j) if(s1[j]!=s2[j]) {hash1=(s1[j]<s2[j])?hash1:hash2;break;}//将两者比较，取最小的顺序
        m[hash1]++;
        if(m[hash1]==2) flag=1;
    }
    printf((flag)?"Twin snowflakes found.\n":"No two snowflakes are alike.\n");
    return 0;
}