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

为什么要hash?

Posted by waterine at 2006-11-10 16:22:14 on Problem 1840
In Reply To:这题太坏了,wa无数次,发现这题加一组数据可以rejudge无数程序 Posted by:bluewind at 2006-08-08 23:58:43
> 用I64d
> 0 0 0 0 0
> 10000000000
> 不用I64d
> 0 0 0 0 0
> 1410065408   (越界的程序也能AC~~~)...
> 
> 偶的程序wa无数次,高手指点一下。(hash...)
> #include<stdio.h>
> #include<string.h>
> const __int64 M=55457;	//prim
> struct record
> {
> 	__int64 value;
> 	__int64 cnt;
> }hash[M];
> __int64 mypow[101];
> int main()
> {
> 	__int64 a1,a2,a3,a4,a5,i,j,k,ans,sum,value;
> 	unsigned __int64 p;
> 	for(i=-50;i<=50;i++)
> 	{
> 		mypow[i+50]=i*i*i;
> 	}
> 
> 	while(scanf("%I64d%I64d%I64d%I64d%I64d",&a1,&a2,&a3,&a4,&a5)!=EOF)
> 	{
> 		memset(hash,0,sizeof(hash));
> 
> 		for(i=-50;i<=50;i++)
> 		{
> 			if (!i) continue;
> 			for(j=-50;j<=50;j++)
> 			{
> 				if (!j) continue;
> 				value=-a1*mypow[i+50]-a2*mypow[j+50];
> 				p=unsigned __int64(value*value)%M;
> 				while(hash[p].cnt && hash[p].value!=value) p=(p+1)%M;
> 				if (!hash[p].cnt)
> 				{
> 					hash[p].value=value;
> 					hash[p].cnt++;
> 				}
> 				else hash[p].cnt++;
> 			}
> 		}
> 		ans=0;
> 		for(i=-50;i<=50;i++)
> 		{
> 			if (!i) continue;
> 			sum=a3*mypow[i+50];
> 			for(j=-50;j<=50;j++)
> 			{
> 				if (!j) continue;
> 				sum+=a4*mypow[j+50];
> 				for(k=-50;k<=50;k++)
> 				{
> 					if (!k) continue;			
> 					value=sum+a5*mypow[k+50];
> 					p=unsigned __int64(value*value)%M;
> 					while(hash[p].cnt && hash[p].value!=value) p=(p+1)%M;
> 					ans+=hash[p].cnt;
> 				}
> 				sum-=a4*mypow[j+50];
> 			}
> 		}
> 		printf("%I64d\n",ans);
> 	}
> 	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