POJ3349_Snowflakes

原来看到过字符串hash

这次碰到了一个数值型hash就在比赛的时候放弃了，果然还是太弱，需要多学习

暴力的话，n平方的算法，而且需要顺时针和逆时针判断12次，肯定TLE

暴力不行才会需要想别的方法：

对所有的值进行HASH是分了对值进行分类，分类最正常也是最一般的想法就是%一个质数

质数选择很重要：几万左右的比较好

如果在一组的话，那么就使用暴力匹配，顺时针和逆时针判断12次，如果至少有1次匹配成功就说明正确

否则，当所有数据读完之后都没有，那就是没有结果

#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

const int maxn=15000;
const int maxm=50;

struct node{
	int a[6];
}snow[maxn][maxm];

int m[maxn];

int hash(node x){
	int key=0;
	for(int i=0;i<6;i++)
		key+=x.a[i];
	key%=14997;
	return key;
}

int cmp(node x,node y){
	int st,i,j;
	for(st=0;st<6;st++){
		for(i=st,j=0;j<6;j++,i=(i+1)%6)
			if (x.a[i]!=y.a[j])  break;
		if (j==6) return 1;
		for(i=st,j=0;j<6;j++,i=(i+5)%6)
			if (x.a[i]!=y.a[j])  break;
		if (j==6) return 1;
	}
	return 0;
}

int main(){
	//input;
	int i,j,pos,n;
	node SNOW;
	scanf("%d",&n);
	memset(m,0,sizeof(m));
	for(i=1;i<=n;i++){
		for(j=0;j<6;j++) scanf("%d",&SNOW.a[j]);
		pos=hash(SNOW);
		for(j=0;j<m[pos];j++){
			if (cmp(SNOW,snow[pos][j])){
				puts("Twin snowflakes found.");
				return 0;
			}
		}
		snow[pos][m[pos]]=SNOW;
		m[pos]++;
	}
	puts("No two snowflakes are alike.");
	return 0;
}

只要存在一组马上就可以退出返回，不需要继续查询了