POJ3349-Snowflake Snow Snowflakes-Hash

题意：

给出n朵六角雪花的六条边长，

问：是否存在相同的两片雪花

思路：利用Hash，保存每多雪花的边长总和和编号。

AC代码：

 1 #include<stdio.h>
 2 #include<cmath>
 3 #include<queue>
 4 #include<vector>
 5 #include<string.h>
 6 #include<algorithm>
 7 using namespace std;
 8 #define PI acos(-1.0)
 9 #define inf 0x3f3f3f3f
10 
11 const int mod=1e5+7;//14997,素数即可
12 int a[100020][10];
13 vector<int>hash[mod];
14 
15 bool w(int x,int y)//传入需要比较是否相同的两片雪花的编号
16 {
17     for(int i=0; i<6; i++)
18     {
19         if(a[x][0]==a[y][i])
20         {
21             int j;
22             for(j=1; j<6; j++) //顺时针
23             {
24                 if(a[x][j]!=a[y][(i+j)%6])
25                     break;
26             }
27             if(j==6)
28                 return 1;
29                 
30             for(j=1; j<6; j++) //逆时针
31             {
32                 if(a[x][6-j]!=a[y][(i+j)%6])
33                     break;
34             }
35             if(j==6)
36                 return 1;
37         }
38     }
39     return 0;
40 }
41 
42 bool judge()//对在hash值相同的雪花两两比较。
43 {
44     for(int k=0; k<mod; k++)
45     {
46         int p=hash[k].size();
47         for(int i=0; i<p; i++)
48         {
49             for(int j=i+1; j<p; j++)
50             {
51                 if(w(hash[k][i],hash[k][j]))
52                     return 1;
53             }
54         }
55     }
56     return 0;
57 }
58 
59 int main()
60 {
61     int n;
62     scanf("%d",&n);
63     for(int i=0; i<n; i++)
64     {
65         int sum=0;
66         for(int j=0; j<6; j++)
67         {
68             scanf("%d",&a[i][j]);//i即代表雪花编号
69             sum+=a[i][j];
70         }
71         int u=sum%mod;
72         hash[u].push_back(i);//保存哈希值及其对应雪花编号
73     }
74     bool flag=judge();
75     if(flag)
76         printf("Twin snowflakes found.
");
77     else
78         printf("No two snowflakes are alike.
");
79     return 0;
80 }

View Code