Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

2172MS,一次通过好爽!!!附代码

Posted by zhangyu175cm at 2012-03-15 15:19:18 on Problem 3349
其他不多说,说说如何判重的,把两个数组中的一个复制后接在其后面,形成一个长度为12的长数组,然后另一个短数组与其进行匹配,考虑到顺逆时针的问题,需要把短数组逆置一下再匹配一次,如果有一次匹配成功说明是同一片雪花。 请指教!!

#include <stdio.h>
#define M 100003

struct node{
	int a[6];
	struct node* next;
};
typedef node snowflake;
// 哈希函数
unsigned int hash(int a[]){
	int i=0,cnt=0;
	for(i=0;i<6;i++){
		cnt+=a[i];
	}
	return cnt%M;
}
// 判重函数
int judge(int a[6],int b[6]){
	int c[12]={0};
	int i,j,k;
	for(i=0;i<6;i++){
		c[i]=c[6+i]=a[i];
	}
	//for(i=0;i<12;i++)  printf("%d ",c[i]);
	for(i=0;i<=6;i++){
		j=0;
		for(k=i;k<=(i+5);k++){
			if(c[k]==b[j++]) continue;
			else break;
		}
		if(j==6) return 1;
	}
	return 0;
}
// 逆置函数
int* reverse(int a[6]){
	int i;
	for(i=0;i<3;i++){
		a[i]=a[i]^a[5-i];
		a[5-i]=a[5-i]^a[i];
		a[i]=a[i]^a[5-i];
	}
	return a;
}

int main()
{ 
	snowflake* table[M]={NULL};
	snowflake* temp;
	snowflake snow[M];
	int i,j,k,n;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<6;j++) scanf("%d",&(snow[i].a[j]));
	}
	for(i=0;i<n;i++){
		k=hash(snow[i].a);
		if(table[k]==NULL){
			snow[i].next=table[k];
			table[k]=&snow[i];
		}
		else{
			temp=table[k];
			while(temp!=NULL){
				if(judge(temp->a,snow[i].a)==0&&judge(temp->a,reverse(snow[i].a))==0){
					temp=temp->next;
				}
				else{
					
					printf("%s\n","Twin snowflakes found.");
					return 0;
				}
			}
			snow[i].next=table[k];
			table[k]=&snow[i];
		}
	}
    printf("%s\n","No two snowflakes are alike.");
	return 0;
}




Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator