首页 > 代码库 > POJ 3349 Snowflake Snow Snowflakes 哈希(链式解决冲突)
POJ 3349 Snowflake Snow Snowflakes 哈希(链式解决冲突)
题意:n个数列 每个数列6个元素a[i],a[i]<=1e7,两个数列只要,经过若干次循环移动能相等则定义为相似.
n<=1e5,问n个数列中 是否存在两个数列相似?
每个数列只有6个数,则相似的最多12种,对每个数列算出其hash值 相同hash值插入同一个链表中.
查看新输入的数列插入时是否产生冲突即可 O(n*12)
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; typedef long long ll; typedef pair<int,int> ii; const ll mod=1200007; const ll inf=1e18; const int N=2e6+20; int head[N],ip; void init() { memset(head,-1,sizeof(head)); ip=0; } struct node{ int num[6]; int next; }e[N]; int get_hash(int *num)//hash?μ { int h=0; for(int i=0;i<6;i++) h+=num[i]; return h%mod; } void insert_hash(int *num,int h) { for(int i=0;i<6;i++) e[ip].num[i]=num[i]; e[ip].next=head[h]; head[h]=ip++; } bool compare(int *a,int *b) { for(int i=0;i<6;i++) { if(a[i]!=b[i]) return false; } return true; } bool search_hash(int *num) { int h=get_hash(num); for(int i=head[h];i!=-1;i=e[i].next) { if(compare(num,e[i].num)) return true; } insert_hash(num,h); return false; } int main() { init(); int n,num[2][15]; bool flag=false; scanf("%d",&n); while(n--) { for(int i=0;i<6;i++) scanf("%d",&num[0][i]),num[0][i+6]=num[0][i];//clockwisze if(flag) continue; for(int i=0;i<6;i++) num[1][i]=num[1][i+6]=num[0][5-i]; for(int i=0;i<6;i++)//ê?·?ó?2úéú3?í? { if(search_hash(num[0]+i)||search_hash(num[1]+i)) { flag=true; break; } } } if(flag) printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); return 0; }
POJ 3349 Snowflake Snow Snowflakes 哈希(链式解决冲突)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。