https://www.acwing.com/problem/content/139/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int a[20];
ull ha[20];
ull mod = 1e6 + 7;
unordered_map<ull, vector<vector<int> > > m;
bool check(ull key, vector<int> &vec) {
auto vi = m.find(key);
if(vi == m.end())
return false;
for(auto v : (vi->second)) {
bool suc = 1;
for(int i = 0; i < 7; ++i) {
if(v[i] != vec[i]) {
suc = 0;
break;
}
}
if(suc)
return true;
}
return false;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
srand(time(0));
for(int i = 0; i < 12; ++i) {
ha[i] = rand();
ha[i] = (ha[i] << 16) | rand();
ha[i] = (ha[i] << 16) | rand();
ha[i] = (ha[i] << 16) | rand();
}
int n;
scanf("%d", &n);
vector<ull> vec;
vector<int> vv(7);
while(n--) {
for(int i = 0; i < 6; ++i) {
scanf("%d", &a[i]);
a[i + 6] = a[i];
}
vec.clear();
for(int j = 0; j < 6; ++j) {
ull cur = 0;
for(int i = 0; i < 6; ++i) {
cur += (ha[i] + ((a[i + j] << 32) | a[i + j]));
}
vec.push_back(cur);
}
reverse(a, a + 12);
for(int j = 0; j < 6; ++j) {
ull cur = 0;
for(int i = 0; i < 6; ++i) {
cur += (ha[i] + ((a[i + j] << 32) | a[i + j]));
}
vec.push_back(cur);
}
sort(vec.begin(), vec.end());
ull key = 0;
for(int j = 0; j < 12; ++j) {
key = (key << 4) ^ (ha[j]) ^ (vec[j]);
}
sort(a, a + 6);
vv[0] = 0;
for(int i = 0; i < 6; ++i) {
vv[i + 1] = a[i];
vv[0] += a[i];
}
if(check(key, vv)) {
puts("Twin snowflakes found.");
return 0;
}
m[key].push_back(vv);
}
puts("No two snowflakes are alike.");
}
AcWing - 137 - 雪花雪花雪花 = 哈希
标签：
原文地址：https://www.cnblogs.com/Inko/p/11729785.html
