首页 > 代码库 > hash应用以及vector的使用简介：POJ 3349 Snowflake Snow Snowflakes
hash应用以及vector的使用简介：POJ 3349 Snowflake Snow Snowflakes
今天学的hash。说实话还没怎么搞懂，明天有时间把知识点总结写了，今天就小小的写个结题报告吧！
题意：
在n （n<100000)个雪花中判断是否存在两片完全相同的雪花，每片雪花有6个角,每个角的长度限制为1000000
两片雪花相等的条件：
雪花6个角的长度按顺序相等（这个顺序即可以是顺时针的也可以是逆时针的）
解题思路：
hash：连加求余法 求key 值，链地址法解决冲突，连加求余法 求key 值挺简单，关于链地址法解决冲突可以通过c++中，vector容器可以较为方便的实现。
下面先介绍一下vector容器：（其实今天也第一次接触vector容器）
1 基本操作
(1)头文件#include<vector>.
(2)创建vector对象，vector<int> vec;
(3)尾部插入数字：vec.push_back(a);
(4)使用下标访问元素，cout<<vec[0]<<endl;记住下标是从0开始的。
(5)使用迭代器访问元素.
vector<int>::iterator it;for(it=vec.begin();it!=vec.end();it++) cout<<*it<<endl;
(6)插入元素： vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;
(7)删除元素： vec.erase(vec.begin()+2);删除第3个元素
vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始
(8)向量大小:vec.size();
(9)清空:vec.clear();
具体思路：
当且仅当两片雪花的key值一样时，这两片雪花才有可能相同。
求出一组的key值后，在该key值的容器中寻找是否有相同的雪花若存在，break出来即可。
那么当我们寻找到key值相同的两片雪花时，我们该如何比较两片雪花？
其实是可以的。假设有两片雪花，A 和B
我们固定A，先按顺时针方向比较：
若A0==B0，则按顺序比较A1和B1.........比较A5和B5
只要当出现Ai != Bi，则把B顺时针转动一次，
若A0==B1，则按顺序比较A1和B2.........比较A5和B0
以此类推，直至B转动了5次，若还不相同，则说明这两片雪花在顺时针方向不等。
再比较逆时针方向：
同样固定A，若A0==B5，则按顺序比较A1和B4.........比较A5和B0
只要当出现Ai != B（5-i），则把B逆时针转动一次，
若A0==B4，则按顺序比较A1和B3.........比较A5和B5
以此类推，直至B转动了5次，若还不相同，则说明这两片雪花在逆时针方向不等。
听了这么多，小盆友们是不是都会了呢？嘿嘿，附上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 #define maxn 100010 8 #define pri 100007 9 vector<int> hash[pri];10 int snow[maxn][6];11 int n;12 int cmp(int a,int b)13 {14 for(int i=0; i<6; i++)15 {16 if(snow[a][0]==snow[b][i%6] )17 if(snow[a][1]==snow[b][(i+1)%6] && snow[a][2]==snow[b][(i+2)%6] && snow[a][3]==snow[b][(i+3)%6] && snow[a][4]==snow[b][(i+4)%6] && snow[a][5]==snow[b][(i+5)%6])18 return 1;19 if(snow[a][5]==snow[b][i%6])20 if(snow[a][4]==snow[b][(i+1)%6] && snow[a][3]==snow[b][(i+2)%6] && snow[a][2]==snow[b][(i+3)%6] && snow[a][1]==snow[b][(i+4)%6] && snow[a][0]==snow[b][(i+5)%6])21 return 1;22 }23 return 0;24 }25 int main()26 {27 scanf("%d",&n);28 int i,j;29 for(i=0; i<n; i++)30 {31 scanf("%d%d%d%d%d%d",&snow[i][0],&snow[i][1],&snow[i][2],&snow[i][3],&snow[i][4],&snow[i][5]);32 }33 int sum,flag=1,key;34 for(i=0; i<n&&flag!=0; i++)35 {36 sum=0;37 for(j=0; j<6; j++)38 sum+=snow[i][j];39 key=sum%pri;40 for(j=0; j<hash[key].size(); j++)41 {42 if(cmp(i,hash[key][j]))43 {44 flag=0;45 puts("Twin snowflakes found.");46 break;47 }48 }49 hash[key].push_back(i);50 }51 if(flag==1)52 puts("No two snowflakes are alike.");53 return 0;54 }
There is a meaning for wings that cannot fly,it‘s a previous memory of when you once flew through the sky.