题目描述
雪花六元组顺时针逆时针任意一点开始的环序列都相等称作这两片雪花相等
样例
blablabla
自制哈希函数 多次哈希值
既然是hash了 那么肯定会有相同的hash的情况的 对于无穷尽的情况
所以为了能够可以在大量的数据面前hash code不冲突
那么我们可以用多个hash函数来对应一组数 (防止筛选垃圾邮箱失手思想)
我自己是定了三个hash函数 来保证嘛
1
当前值*下一个值 的和
2
(系数1+当前值)*(系数2+下一个值) 的和 (反着也要来一遍 不然因为系数的不同会导致顺时针逆时针的不同)
3
对角线乘积的和
时间复杂度
懒得算 大概nlogn加上乘点常数
C++ 代码
#include <bits/stdc++.h>
using namespace std;
long long snow[6]; //开个6的数组存就好 因为有乘积相加所以存的longlong
int main()
{
ios::sync_with_stdio(0); //输入加速
cin.tie(0);
int n;
cin>>n;
set<pair<pair<long long,long long>,long long>> s; //三个hash code的set
for(int i=0;i<n;i++)
{
for(int j=0;j<6;j++)
cin>>snow[j];
pair<long long,long long> p={0,0}; //初始化
pair<pair<long,long>,long long> pp={p,0};
for(int j=0;j<5;j++) //函数1
pp.first.first+=snow[j]*snow[j+1];
pp.first.first+=snow[5]*snow[0];
for(int j=0;j<5;j++) //函数2
pp.first.second+=(snow[j]+7)*(snow[j+1]+11);
pp.first.second+=(snow[5]+7)*(snow[0]+11);
for(int j=5;j>0;j--)
pp.first.second+=(snow[j]+7)*(snow[j-1]+11);
pp.first.second+=(snow[0]+7)*(snow[5]+11);
pp.second=snow[0]*snow[3]+snow[1]*snow[4]+snow[2]*snow[5]; //函数3
if(s.count(pp)){ //判断一下
cout<<"Twin snowflakes found.";
return 0;
}
s.insert(pp);
}
cout<<"No two snowflakes are alike.";
return 0;
}
6666