poj 3349Snowflake Snow Snowflakes

poj 3349Snowflake Snow Snowflakes"/>

poj 3349Snowflake Snow Snowflakes

裸的hash。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD=9999991,N=100005;
struct edge{int sum[7],next;
}e[N+5];
int head[N+5],cnt=0,a[7];
inline int ha(){int t1=0,t2=1;for(int i=0;i<6;++i)t1=(t1+a[i])%MOD,t2=(long long)t2*a[i]%MOD;return (t1+t2)%MOD;
}
inline void ins(int k){e[++cnt].next=head[k];memcpy(e[cnt].sum,a,sizeof(a));head[k]=cnt;
}
bool equal(int *a,int *b){for(register int i=0;i<6;++i){for(register int j=0;j<6;++j){int k;for(k=0;k<6;++k){if(a[(i+k)%6]!=b[(j+k)%6])break;}if(k==6)return 1;for(k=0;k<6;++k){if(a[(i+k)%6]!=b[(j-k+6)%6])break;}if(k==6)return 1;}}return 0;
}
bool query(int k){for(register int i=head[k];i;i=e[i].next){if(equal(e[i].sum,a))return 1;}return 0;
}
int main(){int n;    scanf("%d",&n);bool f=1;for(register int i=1;i<=n;++i){for(register int j=0;j<6;++j)scanf("%d",&a[j]);int k=ha();if(query(k)){puts("Twin snowflakes found.");f=0;break;}ins(k);}if(f)puts("No two snowflakes are alike.");return 0;
}

转载于:.html