做的第一道hash题目,不知道什么情况该用什么方法hash
code
#include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) const int maxn = 1000002; const long long BigP=999983; const int INF = 0x3fffffff; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); const double eps= 1e-7; using namespace std; //采用相加取余大素数的hash int N; struct node{ bool use; int arm[6]; node *next; }snows[maxn]; void insert(int arm[],struct node *p){ if(!(p->use)){ FF(i,6){ p->arm[i]=arm[i]; } p->use=true; p->next= new node; p->next->use=false; }else{ p=p->next; insert(arm,p); } } LL hash(int arm[]){ LL t=0; FF(i,6){ t=(t+arm[i]%BigP)%BigP; } return t; } bool cmp(int a[],int b[]){//一共六个元素,就这样好了。。。囧。。。 if (a[0]==b[0]&&a[1]==b[1]&&a[2]==b[2]&&a[3]==b[3]&&a[4]==b[4]&&a[5]==b[5]) return 1; else if(a[0]==b[1]&&a[1]==b[2]&&a[2]==b[3]&&a[3]==b[4]&&a[4]==b[5]&&a[5]==b[0]) return 1; else if(a[0]==b[2]&&a[1]==b[3]&&a[2]==b[4]&&a[3]==b[5]&&a[4]==b[0]&&a[5]==b[1]) return 1; else if(a[0]==b[3]&&a[1]==b[4]&&a[2]==b[5]&&a[3]==b[0]&&a[4]==b[1]&&a[5]==b[2]) return 1; else if(a[0]==b[4]&&a[1]==b[5]&&a[2]==b[0]&&a[3]==b[1]&&a[4]==b[2]&&a[5]==b[3]) return 1; else if(a[0]==b[5]&&a[1]==b[0]&&a[2]==b[1]&&a[3]==b[2]&&a[4]==b[3]&&a[5]==b[4]) return 1; else return 0; } bool search(int arm[],struct node *p){ int arm2[6]; FF(i,6){ arm2[i]=arm[5-i]; } while(p->use){ int tmp[6]; FF(i,6) tmp[i]=p->arm[i]; if( cmp(tmp,arm) || cmp(tmp,arm2) ) return true; p=p->next; } return false; } void init(node a){ a.use=false; a.next=NULL; } int main() { SD(N); FOR(i,0,999983){ init(snows[i]); } int arm[6]; FOR(i,1,N){ FF(i,6) SD(arm[i]); LL k=hash(arm); struct node *p=&snows[k]; if( !search(arm,p) ) insert(arm,p); else{ printf("Twin snowflakes found.\n"); return 0; } } printf("No two snowflakes are alike.\n"); return 0; }