poj3349（Snowflake Snow Snowflakes）

题目大意：

给你N个雪花，每个雪花由6个长度构成，让你判断N哥雪花中是否有两个或两个以上的雪花是相似的，相似的规则是：有两个雪花a、b。b在任意位置顺时针或者逆时针转和a的大小顺序相同即为相似的雪花。

解题思路；

一般的方法如果时间复杂度是O（n^2）的都会超时，所以要尽量让N小，所有用个简单哈希。将6个数的和对N取余存到一个vector。然后再在vector里找看是否有相似的雪花。

代码：

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <string>
  8 #include <bitset>
  9 #include <vector>
 10 #include <queue>
 11 #include <stack>
 12 #include <cmath>
 13 #include <list>
 14 //#include <map>
 15 #include <set>
 16 using namespace std;
 17 /***************************************/
 18 #define ll long long
 19 #define int64 __int64
 20 /***************************************/
 21 const int INF = 0x7f7f7f7f;
 22 const double eps = 1e-8;
 23 const double PIE=acos(-1.0);
 24 const int d1x[]= {0,-1,0,1};
 25 const int d1y[]= {-1,0,1,0};
 26 const int d2x[]= {0,-1,0,1};
 27 const int d2y[]= {1,0,-1,0};
 28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
 29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
 30 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/
 31 /***************************************/
 32 void openfile()
 33 {
 34     freopen("data.in","rb",stdin);
 35     freopen("data.out","wb",stdout);
 36 }
 37 /**********************华丽丽的分割线,以上为模板部分*****************/
 38 const int N=999;
 39 int n;
 40 typedef struct
 41 {
 42     int a[6];
 43     long long sum;
 44 } Node;
 45 Node node;
 46 vector <Node>vc[N];
 47 int cmp2(int a1[],int a2[])
 48 {
 49     int i,j;
 50     int cnt1=0,cnt2=0;
 51     for(i=0; i<6; i++)
 52     {
 53         if (a1[0]==a2[i])
 54         {
 55             for(cnt1=0,j=1; j<6; j++)
 56             {
 57                 int v=i+j;
 58                 if (v>=6)
 59                     v-=6;
 60                 if (a1[j]==a2[v])
 61                     cnt1++;
 62             }
 63             if (cnt1==5)
 64                 return 1;
 65             for(cnt2=0,j=1; j<6; j++)
 66             {
 67                 int v=i-j;
 68                 if (v<0)
 69                     v+=6;
 70                 if (a1[j]==a2[v])
 71                     cnt2++;
 72             }
 73             if (cnt2==5)
 74                 return 1;
 75         }
 76     }
 77     return 0;
 78 }
 79 int cmp1()
 80 {
 81     int i,j,k;
 82     for(i=0; i<N; i++)
 83     {
 84         for(j=0; j<vc[i].size(); j++)
 85             for(k=j+1; k<vc[i].size(); k++)
 86             {
 87                 if (vc[i][j].sum==vc[i][k].sum&&cmp2(vc[i][j].a,vc[i][k].a))
 88                     return 1;
 89             }
 90     }
 91     return 0;
 92 }
 93 int main()
 94 {
 95     while(scanf("%d",&n)!=EOF)
 96     {
 97         int i,j;
 98         for(i=0; i<n; i++)
 99         {
100             node.sum=0;
101             for(j=0; j<6; j++)
102             {
103                 scanf("%d",&node.a[j]);
104                 node.sum+=node.a[j];
105             }
106             vc[node.sum%N].push_back(node);
107         }
108         if (cmp1())
109             printf("Twin snowflakes found.
");
110         else
111             printf("No two snowflakes are alike.
");
112         for (i=0;i<N;i++)
113             vc[i].clear();
114     }
115     return 0;
116 }
117 /*
118 2
119 1 2 3 4 5 6
120 2 3 4 5 6 7
121 2
122 1 2 3 1 3 2
123 1 3 2 1 2 3
124 .*/

View Code

屌丝终有逆袭日，*******。