题意:传送门
题解:这个题本来是用于hash的,吴书上讲的很好,本次附上另外一中解法,用字符串的最小表示法解答:周源论文,本题中加了一种翻转操作,那么可以把不翻转和翻转的两个最小表示法再取最小,最后通过排序查找即可。
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=100000+5;
int n,snows[N][6],idx[N],snow[6],isnow[6];
void get_min(int *b)
{
static int a[12];
for(int i=0;i<12;i++)a[i]=b[i%6];
int i=0,j=1,k;
while(i<6&&j<6){
for(k=0;k<6&&a[i+k]==b[j+k];k++);
if(k==6)break;
if(a[i+k]>b[j+k]){
i+=k+1;
if(i==j)i++;
}else{
j+=k+1;
if(i==j)j++;
}
}
k=min(i,j);
for(i=0;i<6;i++)b[i]=a[k+i];
}
bool cmp(int *a,int *b)
{
for(int i=0;i<6;i++){
if(a[i]<b[i])return true;
else if(a[i]>b[i])return false;
}
return false;
}
bool cmp2(int a,int b)
{
if(cmp(snows[a],snows[b]))return true;
}
int main()
{
n=read();
for(int i=0;i<n;i++){
for(int j=0,k=5;j<6;j++,k--){
snow[j]=read();
isnow[k]=snow[j];
}
get_min(snow);
get_min(isnow);
if(cmp(snow,isnow))memcpy(snows[i],snow,sizeof(snow));
else memcpy(snows[i],isnow,sizeof(isnow));
idx[i]=i;
}
sort(idx,idx+n,cmp2);
bool flag=false;
for(int i=1;i<n;i++){
if(!cmp(snows[idx[i-1]],snows[idx[i]])&&!cmp(snows[idx[i]],snows[idx[i-1]])){
flag=true;
break;
}
}
if(flag)puts("Twin snowflakes found.");
else puts("No two snowflakes are alike.");
return 0;
}