POJ - 3349 Snowflake Snow Snowflakes解题报告

哈希表好像远比我想象的要复杂得多啊 @_@~ loading。。。。 

又过了很久，大概看懂了一点这个哈希表是个什么意思：

对于这道题，我要做的就是，根据每个雪花的六个数（把他们映射到一个整数），把这些雪花分类，尽量多的分类，每一类里的雪花数量尽量少（在内存大小允许的前提下）。而且对于一个已知六条边长度的雪花，都是可以瞬间（以O(1)的时间复杂度）找到这个雪花应该在的类。然后就是如果有多个雪花的六个数都有相同的映射，一个很巧妙很巧妙的方法，现在想想之前的邻接表代码实现看不懂应该也是用了这个方法，就是用next数组表示同一类里面，第i个雪花的下一雪花的标号next[i];

去网上看了几个映射方法，然后因为第一次做哈希表的题，所有都没用过。现在暂时只讨论本题，因为我要考虑的是这六个数的围成的圈是否有重复的，所有这个映射方法至少应该满足的条件是：有可能围城相同的环的两组数一定要分到一个类里面。换句话说，就是不同组里面的两组数一定不可能围成相同的环。但是如何在满足这个的条件下使得每一类里面的数尽可能的少呢？也就是映射的尽量均匀。

#include<iostream>#include<string.h>#include<stdio.h>#define N 1000000using namespace std;int hash[N+500]={0};int next[N+500]={0};int snow[100500][6]={0};int n;void input(){	for(int i=1;i<=n;i++)	{		for(int j=0;j<6;j++)		{			scanf("%d",&snow[i][j]);		}	}}bool compare(int *a,int *b)//判断a数组和b数组是否可以围成相同的圈 {	for(int i=0;i<6;i++)	{		bool flag=1;		for(int j=0;j<6;j++)		{			if(a[j]!=b[(j+i)%6])			{				flag=0;break;			}		}		if(flag==1)return 1;	}	for(int i=0;i<6;i++)	{		bool flag=1;		for(int j=0;j<6;j++)		{			if(a[j]!=b[(i-j+5)%6])			{				flag=0;break;			}		}		if(flag==1)return 1;	}	return 0;}/*bool compare(int a,int b)//网友的compare函数 {    int i,j,k;    for(i=0;i<6;i++)    {        for(j=i,k=0;k<6;k++,j=(j+1)%6)//???,???????            if(snow[a][k]!=snow[b][j])break;        if(k==6)return true;        for(j=i,k=0;k<6;k++,j=(j+5)%6)//???            if(snow[a][k]!=snow[b][j])break;        if(k==6)return true;    }    return false;}*/int main(){	while(cin>>n)	{		input();		bool flag=0;		memset(hash,0,sizeof(hash));		memset(next,0,sizeof(next));		for(int i=1;i<=n;i++)		{			int x=0; 			for(int j=0;j<6;j++)//求出i对应的x 			{				x=(int)((x+(long long int)snow[i][j]*(long long int)snow[i][j])%N);			}			int l=hash[x];			//cout<<x<<endl;			while(l)//判断是否有与第i个相同的雪花 			{				if(compare(snow[i],snow[l]))				{					flag=1;					break;				}				l=next[l];			}			if(flag==1)break;			//把第i个加入类中 			next[i]=hash[x];			hash[x]=i;		}		if(flag==1)cout<<"Twin snowflakes found."<<endl;		else cout<<"No two snowflakes are alike."<<endl;	}}另外x=(x+snow[i][j]*snow[i][j])%N会runtime error。一定要强制类型转换成long long int。