用hash链地址法,取了个99997大素数就AC了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int mod = 99997; struct node { int len[6]; }f[100010]; vector <int>hash[100000]; int size[100000]; int get_key(node t) { int key = 0; for(int i=0;i<6;i++) key += t.len[i]%mod; return key%mod; } bool exit(node t,int key) { int len = size[key]; if(len == 0)return false; for(int i=0;i<len;i++) { int r = hash[key][i]; for(int j=0;j<6;j++) { int flag = 1; for(int k=j,cnt = 0;cnt<6;(k = (k==5) ? 0 : k+1),cnt++) { if(t.len[k] != f[r].len[cnt]){flag = 0;break;} } if(flag)return true; } for(int j=0;j<6;j++) { int flag = 1; for(int k=j,cnt = 0;cnt<6;(k = (k==0) ? 5 : k-1),cnt++) { if(t.len[k] != f[r].len[cnt]){flag = 0;break;} } if(flag)return true; } } return false; } int n; int main() { //freopen("input.txt","r",stdin); while(~scanf("%d",&n)) { for(int i=0;i<100000;i++) hash[i].clear(); memset(size,0,sizeof(size)); int found = 0; for(int i=1;i<=n;i++) { for(int j=0;j<6;j++) scanf("%d",&f[i].len[j]); if(found)continue; int key = get_key(f[i]); if(!exit(f[i],key))hash[key].push_back(i),size[key]++; else found = 1; } //cout << "KK" << endl; if(found)printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); } return 0; }