开始按hash做的 交上去就wa 但是和标称拍了半天也没有不一样的 可能是生成的数据太水了吧... #include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 #define mod 10000007 #define ll long long using namespace std; ll ha; int n,a[maxn][6],base,J[7]; bool f[mod+10]; int init() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int main() { while(cin>>n) { memset(f,0,sizeof(f));int falg=0; for(int i=1;i<=n;i++) for(int j=0;j<=5;j++) a[i][j]=init(); J[1]=17;J[2]=107;J[3]=117;J[4]=1007;J[5]=10007;J[6]=100007; base=a[1][0]; for(int i=1;i<=n;i++) { int c[20],num=0; for(int j=0;j<=5;j++) if(a[i][j]==base) { ha=0; for(int k=j,r=1;r<=6;k++,r++)ha+=a[i][k%6]*J[r]; if(ha<0)ha=-ha;ha%=mod;c[++num]=ha; ha=0; for(int k=j,r=1;r<=6;k--,r++)ha+=a[i][(k+6)%6]*J[r]; if(ha<0)ha=-ha;ha%=mod;c[++num]=ha; } for(int j=1;j<=num;j++) if(f[c[j]]==1) { printf("Twin snowflakes found. "); falg=1;break; } if(falg)break; for(int j=1;j<=num;j++)f[c[j]]=1; } if(falg)continue; printf("No two snowflakes are alike. "); } return 0; }
/* 看许多人博客里说啥不用判断结构也能过.... 数据有问题吧...说说正解 最小表示法 是解决同构问题的一种方法 然而并没有看懂 暴力求得（不知道为啥比标称的算法求跑的还快） 然后每个雪花用最小表示法唯一表示 最后排序找相邻的有没有相同的 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #define maxn 100010 using namespace std; int n,a[maxn][6],falg,c[6]; int init() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int mycmp(int *a,int *b) { for(int i=0;i<6;i++) if(b[i]<a[i])return 1; else if(a[i]<b[i])return 0; return 0; } int cmp(const void *a,const void *b) { int *x = (int*)a, *y = (int *)b; for(int i=0;i<6;i++) { if(*(x+i)<*(y+i))return -1; if(*(x+i)>*(y+i))return 1; } falg=1; return 0; } void Insert(int k) { int ti[6]; for(int i=0;i<6;i++) ti[i]=c[i]; for(int s=0;s<6;s++) { int t[6]; for(int i=s,r=0;r<6;r++,i++)t[r]=c[i%6]; if(mycmp(ti,t)) for(int i=0;i<6;i++)ti[i]=t[i]; for(int i=s,r=0;r<6;r++,i--) t[r]=c[(i+6)%6]; if(mycmp(ti,t)) for(int i=0;i<6;i++)ti[i]=t[i]; } memcpy(a[k],ti,sizeof(int)*6); } int main() { while(cin>>n) { falg=0; for(int i=0;i<n;i++) { for(int j=0;j<6;j++)c[j]=init(); Insert(i); } qsort(a,n,sizeof(a[0]),cmp); if(falg==1)printf("Twin snowflakes found. "); else printf("No two snowflakes are alike. "); } return 0; }