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