HDU 1496 Equations 数值hash

HDU 1496 Equations 数值hash

题目:

Equations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5612    Accepted Submission(s): 2228

Problem Description

Consider equations having the following form:

a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0.

It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i ∈{1,2,3,4}.

Determine how many solutions satisfy the given equation.

Input
The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.
End of file.
Output
For each test case, output a single line containing the number of the solutions.
Sample Input
1 2 3 -4
1 1 1 1
Sample Output
39088 0
这个题目,如果直接去暴力枚举三重循环的话 ,会导致超时,因此 不能简单枚举来做, 想到另一个方法 我们可以把式子变为
a*x1*x1+b*x2*x2=-(c*x3*x3+d*x4*x4)

这样之后 ,我们可以先枚举 x1 x2求出 a*x1*x1+b*x2*x2的所有可能值出现的次数 并把次数存在数组里 num[a*x1*x1+b*x2*x2]=次数 然后 再用另一个二重循环枚举x3 x4 来看 c*x3*x3+d*x4*x4里有多少个值和之前重复且异号,然后 就可以直接将次数加上 不过 注意写好 由判断正负性来决定的存储在哪个数组的函数

本题开了两个数组 一个 hashpos存 正的结果 hashneg存负的结果,那么在循环 枚举x3x4的时候 ,就要判断好 什么时候域hashneg对应 什么时候与hashpos对应 我就是因为这个问题错了好几次  在我的这个代码下 应该是 当算出 c*x3^2+d*x4^2<0时 与hashpos对应 而 >=0与hashneg对应 这千万不要搞错!

AC代码如下

/*************************************************************************
    > File Name: 1496.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年12月06日 星期六 11时46分19秒
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int hashmaxsize=1000005;

int hashpos[hashmaxsize];
int hashneg[hashmaxsize];

int main(void)
{
	int a,b,c,d;
	while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
	{
		memset(hashpos,0,sizeof(hashpos));
		memset(hashneg,0,sizeof(hashneg));
		if(a>0 &&  b>0 && c>0 && d>0 || a<0 && b<0 && c<0 && d<0) printf("0n");
		else
		{
			int k;
			for(int i=1;i<=100;i++)
			{
				for(int j=1;j<=100;j++)
				{
					k=a*i*i+b*j*j;
					if(k>0) hashpos[k]++;
					else hashneg[-k]++;
				}
			}
			int sum=0;
			for(int i=1;i<=100;i++)
			{
				for(int j=1;j<=100;j++)
				{
					k=c*i*i+d*j*j;
					if(k>=0) sum+=hashneg[k];				//这里应该用 >=号 不能用 > 号
					else sum+=hashpos[-k];
				}
			}
			printf("%dn",sum*16);
		}
	}
	return 0;
}

改进策略 线性探测再散列+小数组

这个代码能够 AC 不过还有可以继续用hash改进的地方 因为数组开的很大的时候 需要初始化数组的时间也很长,而 两个数字枚举最多产生10000种不同的结果 所以考虑开小数组来节省空间并且用线性探测再散列技术(linear-re hash detection 不知道这么翻译标准么 有待确定) 来处理冲突 那么就有下面的代码了

/*************************************************************************
  > File Name: 1496-linear-rehash.cpp
  > Author: VOID_133
  > ################### 
  > Mail: ################### 
  > Created Time: 2014年12月16日 星期二 21时23分52秒
  > 线性探测再散列解决本题优化时间和空间
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int MOD=50021;				//设置模值

int hash[MOD];						//存储映射关系
int num[MOD];						//Store the num of this cnt;

int genhash(int n)
{
	int tmp=n%MOD;
	if(tmp<0) tmp+=MOD;
	//	else							//- - 迷之else  我是不是脑子发热了
	//	{
	while(hash[tmp]!=n && num[tmp]!=0)
	{
		tmp=(tmp+1)%MOD;
	}
	//	}
	return tmp;
}

//void printArray(int *A,int len)
//{
//
//}

int main(void)
{
	int a,b,c,d;
	while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
	{
		//memset(hash,-1,sizeof(hash));
		memset(num,0,sizeof(num));
		if(a>0 && b>0 && c>0 && d>0 || a<0 && b<0 && c<0 && d<0 )
		{
			printf("0n");
		}
		else
		{
			for(int i=1;i<=100;i++)
			{
				for(int j=1;j<=100;j++)
				{
					int t=a*i*i+b*j*j;
					int p=genhash(t);
					hash[p]=t;
					num[p]++;
				}
			}
			int res=0;
			for(int i=1;i<=100;i++)
			{
				for(int j=1;j<=100;j++)
				{
					int t=-(c*i*i+d*j*j);
					int p=genhash(t);
					res+=num[p];
				}
			}
			printf("%dn",res*16);
		}
	}
	return 0;
}

其中 用了两个数组,一个数组来存储hash映射关系 另一个存 hash(k)出现的次数  注意写好线性探测的循环条件 这个hash是通过一个函数既能查找到已有的映射关系又能建立新的映射关系,具体的代码说明见文章 hash算法基础(超链接)  这代码当时我写了好久然后发现样例不对,找了半天没找到问题后来发现是在散列函数里if后自己多写了个else = = SB了 改了就过了 时间由 1404MS->93MS 内存8988K->1566K hash大法好啊                 _(・ω・」 ∠)_

 

Leave a Reply

Your email address will not be published. Required fields are marked *

one × 3 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.