AcWing 137. 雪花雪花雪花
原题链接
简单
作者:
G_A_TS
,
2019-07-27 14:23:10
,
所有人可见
,
阅读 967
hash
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
int arm[100010][7],prime=99983;
int check_same(int a,int b)
{
for(int i=0;i<6;i++)
{
if((
arm[a][0]==arm[b][i]&& arm[a][1]==arm[b][(i+1)%6]&&
arm[a][2]==arm[b][(i+2)%6]&& arm[a][3]==arm[b][(i+3)%6]&&
arm[a][4]==arm[b][(i+4)%6]&& arm[a][5]==arm[b][(i+5)%6])
||
( arm[a][0]==arm[b][i]&& arm[a][1]==arm[b][(i+5)%6]&&
arm[a][2]==arm[b][(i+4)%6]&& arm[a][3]==arm[b][(i+3)%6]&&
arm[a][4]==arm[b][(i+2)%6]&& arm[a][5]==arm[b][(i+1)%6]))
return true;
}
return false;
}
vector<int>v[100010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=0;j<6;j++)
{
scanf("%d",&arm[i][j]);
}
}
for(int i=1;i<=n;i++)
{
int sum=0,key;
for(int j=0;j<6;j++)
{
sum+=arm[i][j];
}
key=sum%=prime;
for(int j=0;j<v[key].size();j++)
{
if(check_same(v[key][j],i))
{
printf("Twin snowflakes found.\n");
return 0;
}
}
v[key].push_back(i);
}
printf("No two snowflakes are alike.\n");
}