经典hash 好题不多说，直接上代码
1 #include<iostream>
2using namespace std;
3struct node
4   {
5 int a[6];
6 int sum;
7 };
8
9int n;
10node nod[100000];
11bool flag;
12int cmp(const void *a,const void *b)
13{
14 return (*(node *)a).sum-(*(node *)b).sum;
15}
16void solve();
17int main()
18{
19 int i,j;
20 cin>>n;
21 flag=false;
22 for(i=0;i<n;i++)
23  {
24 scanf("%d%d%d%d%d%d",&nod[i].a[0],&nod[i].a[1],&nod[i].a[2],&nod[i].a[3],&nod[i].a[4],&nod[i].a[5]);
25 nod[i].sum=0;
26 for(j=0;j<6;j++) nod[i].sum+=nod[i].a[j];
27 }
28 qsort(nod,n,sizeof(nod[0]),cmp);
29 solve();
30 if(flag) cout<<"Twin snowflakes found."<<endl;
31 else cout<<"No two snowflakes are alike."<<endl;
32 return 0;
33}
34void solve()
35{
36 int i,j,k,l;
37 int head=-1;
38 int tail;
39 while(++head<n)
40 {
41 tail=head+1;
42 while(nod[head].sum==nod[tail].sum&&tail<n) tail++;
43 tail--;
44 if(tail==head)
45 {
46 head=tail;
47 continue;
48 }
49 for(i=head;i<tail;i++)
50 {
51 for(j=i+1;j<=tail;j++)
52 {
53 for(k=0;k<6;k++)
54 {
55 if(nod[i].a[0]==nod[j].a[k])
56 {
57 for(l=1;l<6;l++)
58 {
59 if(nod[i].a[l]!=nod[j].a[(l+k)%6]) break;
60 }
61 if(l==6)
62 {
63 flag=true;
64 return;
65 }
66 for(l=1;l<6;l++)
67 {
68 if(nod[i].a[l]!=nod[j].a[(k-l+6)%6]) break;
69 }
70 if(l==6)
71 {
72 flag=true;
73 return;
74 }
75 }
76 }
77 }
78 }
79 head=tail+1;
80
81 }
82 flag=false;
83 return;
84}
85
|