首页 > 代码库 > poj3349（Snowflake Snow Snowflakes）

poj3349（Snowflake Snow Snowflakes）

2024-07-13 10:33:32   223人阅读

题目地址：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.\n");110         else111             printf("No two snowflakes are alike.\n");112         for (i=0;i<N;i++)113             vc[i].clear();114     }115     return 0;116 }117 /*118 2119 1 2 3 4 5 6120 2 3 4 5 6 7121 2122 1 2 3 1 3 2123 1 3 2 1 2 3124 .*/
View Code


联系
我们