题目描述
有N片雪花,每片雪花由六个角组成,每个角都有长度。
第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1, ai,2, …, ai,6。
因为雪花的形状是封闭的环形,所以从任何一个角开始顺时针或逆时针往后记录长度,得到的六元组都代表形状相同的雪花。
例如ai,1, ai,2, …, ai,6和ai,2, ai,3 ,…, ai,6,ai,1就是形状相同的雪花。
ai,1, ai,2, …, ai,6和ai,6, ai,5, …, ai,1也是形状相同的雪花。
我们称两片雪花形状相同,当且仅当它们各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。
求这N片雪花中是否存在两片形状相同的雪花。
中文翻译可还行。
拿到题目,一看数据范围,1e5,如果我们直接暴力枚举,那肯定是超时了,于是乎就想到了hash,我们求出每一片雪花对应的hash值,比较一下,可以初步缩小一下范围(为什么不能直接就判断呢?因为可能有一些数据虽然hash值是相等的,但有可能顺序就不满足要求了),然后我们就在小范围内进行暴力,顺时针逆时针分别判断就可以了。
代码如下
#include<bits/stdc++.h> using namespace std; #define int long long int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*f; } const int P=99991; const int N=1e5+10; int n; int a[N][10]; vector<int> q[99991]; int h(int x) { int j=0,k=1; for(int i=0;i<6;i++) { j=(j+a[x][i])%P;//六个数的和 k=k*a[x][i]%P;//六个数的积 } return (j+k)%P;//如果这两个数加起来相等,说明原序列的数值一定是一样的 }//但值相等,顺序也可能出问题 int check(int x,int y)//暴力比对顺序 { for(int i=0;i<6;i++) { for(int j=0;j<6;j++) { int flag1=1; for(int k=0;k<6;k++) { if(a[x][(i+k)%6]!=a[y][(j+k)%6])//顺时针 { flag1=0; break; } } if(flag1) return 0; flag1=1;//重置 for(int k=0;k<6;k++) { if(a[x][(i+k)%6]!=a[y][(j-k)%6])//逆时针 { flag1=0; break; } } if(flag1) return 0 ; } } return 1; } signed main() { n=read(); int flag=1; for(int i=0;i<n;i++) { for(int j=0;j<6;j++) a[i][j]=read(); int sum=h(i);//依次计算每一列的hash值 if(flag) { if(q[sum].size()) { for(int j=0;j<q[sum].size();j++) { flag=check(q[sum][j],i); if(flag==0) break; } } q[sum].push_back(i);//存一下 } } if(flag==0) puts("Twin snowflakes found."); else puts("No two snowflakes are alike."); return 0; }
等等,别划走,还有更妙的的解法(但好像时间更久),这也是我写这篇题解的目的
方法二 最小表示法
意不意外,没错,我们只需要将每一个雪花都用最小表示,再进行比较,也可以过(但好像还是和hash有那么一点点关系),但要注意的是,我们还要将每一个雪花倒过来再求一遍最小表示,不要问我为什么,自己好好想想。
#include<bits/stdc++.h> using namespace std; #define uint unsigned long long int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*f; } const int N=6e5+10; const int P=1e7; int a[N][20]; int n; int ans; map<uint,bool> p; int work(int i) { int l=1,r=2,k; while(l<=6&&r<=6) { for(k=0;k<6&&a[i][l+k]==a[i][r+k];k++); if(k==6) break; if(a[i][l+k]>a[i][r+k]) { l=l+k+1; if(l==r) l++; } else { r=r+k+1; if(l==r) l++; } } return min(l,r); } signed main() { n=read(); n*=2; for(int i=1;i<=n;i++) { if(i%2) { for(int j=1;j<=6;j++) { a[i][j]=read(); a[i][j+6]=a[i][j]; } } else { for(int j=1;j<=6;j++) { a[i][j]=a[i][j+6]=a[i-1][7-j]; } } int ans=work(i); uint h=0; for(int j=1;j<=6;j++) h=(uint)a[i][j+ans]+h*P; if(p.find(h)!=p.end()) { printf("Twin snowflakes found."); return 0; } p[h]=1; } printf("No two snowflakes are alike."); return 0; }