首页 > 代码库 > poj3349（Snowflake Snow Snowflakes）
poj3349（Snowflake Snow Snowflakes）
题目地址：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 .*/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。