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

我咋感觉我没用什么特殊方法就过了。。。牛们帮我看看我用的叫什么方法。。谢谢。。哈希的是怎么写?

Posted by NARUTOACM at 2009-10-06 21:04:56 on Problem 3349
#include<iostream>
using namespace std;
const int MAXN=100001;
struct snowflake
{
	int part[7];
	int sum;
}snow[MAXN];
int cmp(const void *a,const void *b)
{
	return (*(snowflake *)a).sum-(*(snowflake *)b).sum;
}
bool comp(int i,snowflake a,snowflake b)
{
	int j=0,ii=i;
	bool s=false,n=false;
	for(i;j<=5;i++)
	{
		if(a.part[j++]!=b.part[i])
		{
			s=true;
			break;
		}
		if(i==5)
			i=-1;
	}
	j=0;
	for(ii;j<=5;ii--)
	{
		if(a.part[j++]!=b.part[ii])
		{
			n=true;
			break;
		}
		if(ii==0)
			ii=6;
	}
	if(s&&n)
		return false;
	return true;
}
bool compare(snowflake a,snowflake b)
{
	int i;
	for(i=0;i<=5;i++)
	{
		if(a.part[0]==b.part[i])
		{
			if(comp(i,a,b))
				return true;
		}
	}
	return false;
}
int main()
{
	int n,i,j,k;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d%d%d%d",&snow[i].part[0],&snow[i].part[1],&snow[i].part[2],&snow[i].part[3],&snow[i].part[4],&snow[i].part[5]);
		snow[i].sum=snow[i].part[0]+snow[i].part[1]+snow[i].part[2]+snow[i].part[3]+snow[i].part[4]+snow[i].part[5];
	}
	qsort(snow,n,sizeof(snow[0]),cmp);
	bool s=false;
	for(i=0;i<n;i++)
	{
		if(snow[i].sum!=snow[i+1].sum)
			continue;
		for(j=i;snow[j].sum==snow[i].sum;j++)
		{
			for(k=j+1;snow[k].sum==snow[i].sum;k++)
			{
				if(compare(snow[j],snow[k]))
				{
					s=true;
					printf("Twin snowflakes found.\n");
					break;
				}
			}
			if(s)
				break;
		}
		if(s)
			break;
		i=j-1;
	}
	if(!s)
		printf("No two snowflakes are alike.\n");
	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