有N片雪花,每片雪花由六个角组成,每个角都有长度。
第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6ai,1,ai,2,…,ai,6。
因为雪花的形状是封闭的环形,所以从任何一个角开始顺时针或逆时针往后记录长度,得到的六元组都代表形状相同的雪花。
例如ai,1,ai,2,…,ai,6ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6,ai,1ai,2,ai,3,…,ai,6,ai,1就是形状相同的雪花。
ai,1,ai,2,…,ai,6ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1ai,6,ai,5,…,ai,1也是形状相同的雪花。
我们称两片雪花形状相同,当且仅当它们各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。
求这N片雪花中是否存在两片形状相同的雪花。
输入格式
第一行输入一个整数N,代表雪花的数量。
接下来N行,每行描述一片雪花。
每行包含6个整数,分别代表雪花的六个角的长度(这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到)。
同行数值之间,用空格隔开。
输出格式
如果不存在两片形状相同的雪花,则输出:
No two snowflakes are alike.
如果存在两片形状相同的雪花,则输出:
Twin snowflakes found.
数据范围
1≤n≤1000001≤n≤100000,
0≤ai,j<100000000≤ai,j<10000000
输入样例:
2
1 2 3 4 5 6
4 3 2 1 6 5
输出样例:
Twin snowflakes found.
思路
举例可知,每朵雪花通过旋转和对称可以得到12种形态
那么可以用字符串hash记录其中最特殊的一种形态(如字典序最大或者最小的),然后找是否有两片一样的。(可以sort或者map标记找)
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 131;
const int N = 1e6+5;
ll ans[N];
int main(){
int n;
cin>>n;
bool flag=false;
for(int i=0;i<n;i++){
int a[7];
for(int j=0;j<6;j++) cin>>a[j];
for(int k=0;k<6;k++){
int k1=k,k2=k,o=6;
ll s1=0,s2=0;
while(o--){
s1=a[k1%6]+s1*P;
s2=a[(k2+6)%6]+s2*P;
k1++,k2--;
}
ans[i]=max(max(s1,s2),ans[i]);
}
}
sort(ans,ans+n);
for(int i=0;i<n-1;i++) if(ans[i]==ans[i+1]){
flag=true;
printf("Twin snowflakes found.\n");
break;
}
if(!flag) printf("No two snowflakes are alike.\n");
return 0;
}