本文主要是介绍poj3349 Snowflake Snow Snowflakes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大致题意：
在n （n<100000)个雪花中判断是否存在两片完全相同的雪花，每片雪花有6个角,每个角的长度限制为1000000
两片雪花相等的条件：
雪花6个角的长度按顺序相等（这个顺序即可以是顺时针的也可以是逆时针的）
大概思路：
用连加求余法求key值（用同余定理简化），链地址法解决冲突
写好左旋转模块和右旋转模块，进行地址冲突之后的比较
边插入边比较，一旦有相同则停止处理，直到全都不同时候，输出没有俩相同的雪花
需要的几个模块
计算key值
顺时针比较
逆时针比较
插入（边插入边比较）
晕晕晕，这道题几乎没有地址冲突， 链地址法不用也可以。
午觉起来后发现我的代码在链地址查找完毕后仍未发现相同key的相同雪花后并没有新建链将这个雪花存进去都能AC，试着把整个链部分都删除掉，还是能AC
#include <iostream>
using namespace std;
#include <cstdlib>
#include <cstdio>
#include <string.h>
struct leafs
{__int64 len[6];
}leaf[100010];
const __int64 prime=999983;
class Hashtable
{public:__int64 len[6];Hashtable* next;Hashtable(){next=0;}
};
Hashtable* hash[prime+1];
__int64 computek(int k)
{__int64 key=0;for(int i=0;i<6;i++){key+=leaf[k].len[i]%prime;}key%=prime;return ++key;
}
bool clock(Hashtable* a,int k)
{int count=0;for(int j=0;j<6;j++){for(int i=0;i<6;i++){if(leaf[k].len[i]!=a->len[(i+j)%6])break;elsecount++;}if(count==6)return true;elsecount=0;}return false;
}
bool cclock(Hashtable* a,int k)
{int count=0;for(int j=0;j<6;j++){for(int i=0;i<6;i++){if(leaf[k].len[i]!=a->len[(11-i-j)%6])break;elsecount++;}if(count==6)return true;elsecount=0;}return false;
}
bool insert(int k)
{__int64 key=computek(k);if(!hash[key]){Hashtable* temp=new Hashtable;for(int i=0;i<6;i++)temp->len[i]=leaf[k].len[i];hash[key]=temp;return false;}else{Hashtable* temp=hash[key];if(clock(temp,k)||cclock(temp,k))return true;else{while(temp->next){temp=temp->next;if(clock(temp,k)||cclock(temp,k))return true;}return false;}}
}
int main()
{memset(leaf,0,sizeof(leaf));memset(hash,0,sizeof(hash));bool issame=false;int n;scanf("%d",&n);for(int i=0;i<n;i++){for(int j=0;j<6;j++)scanf("%d",&leaf[i].len[j]);if(!issame)issame=insert(i);}if(issame)printf("Twin snowflakes found.");elseprintf("No two snowflakes are alike.");return 0;
}
这篇关于poj3349 Snowflake Snow Snowflakes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
