#最小表示法，哈希#poj 3349 Snowflake Snow Snowflakes

题目

求是否有两片雪花，按顺时针或逆时针方向相同（也就是说，可以方向相同，也可以方向相反），如样例我的附图所示，两片雪花是相等的

---

分析

这道题很容易会想到哈希，但是如何优化，可以用最小表示法12$12$合1$1$，表示为最小的序列，再用哈希（要复制1遍）

while (i<=12&&j<=12){
            for (k=0;k<=6&&a[i+k]==a[j+k];k++);
            if (k==6) break;
            if (a[i+k]>a[j+k]){
                i=i+k+1;
                if (i==j) i++;
            }else{
                j=j+k+1;
                if (i==j) j++;
            }
        }

---

代码

#include <cstdio>
#include <algorithm>
#define mod 160001
typedef unsigned uit;
unsigned long long h[mod]; uit a[19],n,cnt;
uit in(){
    uit ans=0; char c=getchar();
    while (c<48||c>57) c=getchar();
    while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
    return ans;
}
uit found(unsigned long long x){
    uit pos=x%mod,i=0;
    while (i<mod&&h[(pos+i)%mod]&&h[(pos+i)%mod]!=x) i++;
    return (pos+i)%mod;
}
bool has(uit x,uit y){
    bool ne=0; uit ans=x,p,pos; unsigned long long sum=0;
    for (p=0;p<6&&a[x+p]==a[y-p];p++);
    if (a[x+p]>a[y-p]) ans=y,ne=1;
    if (ne) for (register uit i=ans;i>ans-6;i--) sum=sum*13131+a[i];
    else for (register uit i=ans;i<ans+6;i++) sum=sum*13131+a[i];//顺时针逆时针合1
    if (h[(pos=found(sum))]==sum) return 1;//如果出现过
    h[pos]=sum; return 0;
}
int main(){
    n=in();
    while (n--){
        for (register uit i1=7;i1<=12;i1++) a[i1-6]=a[i1]=a[i1+6]=in();
        uit i=7,j=8,k,ans1,ans2;
        while (i<=12&&j<=12){//顺时针最小表示法
            for (k=0;k<=6&&a[i+k]==a[j+k];k++);
            if (k==6) break;
            if (a[i+k]>a[j+k]){
                i=i+k+1;
                if (i==j) i++;
            }else{
                j=j+k+1;
                if (i==j) j++;
            }
        }
        ans1=std::min(i,j); i=12; j=11;
        while (i>=7&&j>=7){//逆时针最小表示法
            for (k=0;k<=6&&a[i-k]==a[j-k];k++);
            if (k==6) break;
            if (a[i-k]>a[j-k]){
                i=i-k-1;
                if (i==j) i--;
            }else{
                j=j-k-1;
                if (i==j) j--;
            }
        }
        ans2=std::max(i,j);
        if (has(ans1,ans2)) return !printf("Twin snowflakes found.");//出现两片相同的雪花
    }
    return !printf("No two snowflakes are alike.");
}