hash应用以及vector的使用简介:POJ 3349 Snowflake Snow Snowflakes

时间:2023-03-10 03:02:39
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次,若还不相同,则说明这两片雪花在逆时针方向不等。

听了这么多,小盆友们是不是都会了呢?嘿嘿,附上代码:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 100010
#define pri 100007
vector<int> hash[pri];
int snow[maxn][];
int n;
int cmp(int a,int b)
{
for(int i=; i<; i++)
{
if(snow[a][]==snow[b][i%] )
if(snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%])
return ;
if(snow[a][]==snow[b][i%])
if(snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%] && snow[a][]==snow[b][(i+)%])
return ;
}
return ;
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=; i<n; i++)
{
scanf("%d%d%d%d%d%d",&snow[i][],&snow[i][],&snow[i][],&snow[i][],&snow[i][],&snow[i][]);
}
int sum,flag=,key;
for(i=; i<n&&flag!=; i++)
{
sum=;
for(j=; j<; j++)
sum+=snow[i][j];
key=sum%pri;
for(j=; j<hash[key].size(); j++)
{
if(cmp(i,hash[key][j]))
{
flag=;
puts("Twin snowflakes found.");
break;
}
}
hash[key].push_back(i);
}
if(flag==)
puts("No two snowflakes are alike.");
return ;
}

There is a meaning for wings that cannot fly,it's a previous memory of when you once flew through the sky.