HDU 1496 Equations hash HDU上排名第一！

看题传送门：

http://acm.hdu.edu.cn/showproblem.php?pid=1496

题目大意：

给定a,b,c,d。a*x1^2+b*x2^2+c*x3^2+d*x4^2=0

其中x1~x4 在 [-100,100]区间内， a,b,c,d在[-50,50] 区间内。

求满足上面那个式子的所有解的个数。

思路：

这题用hash的思想很巧妙，先对x1和x2进行枚举，存在的存进hash表中，然后接下来枚举x3和x4，如果恰好和前面的为相反数，那么答案+上前面出现的次数.

提高效率的方法：

1.用枚举1~100而负半区域不考虑，节省枚举数，最后答案因为四个数全部都是正的，而实际上都有每个数都有正有负，故答案*16

2.把平方运算结果存下来。

3.位运算优化hash取模

4.同号的剪枝

普通的hash：

#include<cstdio>

#include<cstring>

const int MAXN=50*100*100*2+10;

int hash_pos[MAXN]; //positive

int hash_neg[MAXN];   //negative

int res[101];

int main()

{

	int a,b,c,d	;

	for(int i=1;i<=100;i++)

		res[i]=i*i;

	while(~scanf("%d%d%d%d",&a,&b,&c,&d))

	{

		if(a>0 && b>0 && c>0 && d>0||a<0 && b<0 && c<0 && d<0)

		{

			printf("0\n");

			continue;

		}

		memset(hash_pos,0,sizeof(hash_pos));

		memset(hash_neg,0,sizeof(hash_neg));

		for(int i=1;i<=100;i++)

		{

			for(int j=1;j<=100;j++)

			{

				int x=res[i]*a+res[j]*b;

				if(x >=0)

					hash_pos[x]++;

				else

					hash_neg[-x]++;

			}

		}

		int cnt=0;

		for(int i=1;i<=100;i++)

		{

			for(int j=1;j<=100;j++)

			{

				int x=res[i]*c+res[j]*d;

				if(x >0)

					cnt+=hash_neg[x];

				else

					cnt+=hash_pos[-x];

			}

		}

		printf("%d\n",cnt<<4);

	}

	return 0;

}

采用开散列+位运算优化的取模运算！

//0 MS 476K

//By hr_whisper 2013/12/27

#include<cstdio>

#include<cstring>

const int mod=1<<15;

struct edge

{

	int val,next,cnt;

}edge[mod];

int head[mod];

int len=0;

inline int gethash(int x)

{

	return (x+ mod) & (mod-1);

}

inline void insert(int x)

{

	int id=gethash(x);

	for(int i=head[id]; i != -1;i=edge[i].next)

	{

		if(edge[i].val==x)

		{

			edge[i].cnt++;

			return;

		}

	}

	edge[len].cnt=1;

	edge[len].next=head[id];

	edge[len].val=x;

	head[id]=len++;

}

inline int search(int x)

{

	int id=gethash(x);

	for(int i=head[id] ; i!=-1;i=edge[i].next)

	{

		if(edge[i].val==x)

			return edge[i].cnt;

	}

	return 0;

}

int res[101];    

int main()

{

	int a,b,c,d ;

	for(int i=1;i<=100;i++)

		res[i]=i*i;  

	while(~scanf("%d%d%d%d",&a,&b,&c,&d))

	{

		if(a>0 && b>0 && c>0 && d>0||a<0 && b<0 && c<0 && d<0)

		{

			printf("0\n");

			continue;

		}  

		memset(head,-1,sizeof(head));

		len=0;

		for(int i=1;i<=100;i++)

		{

			for(int j=1;j<=100;j++)

			{

				int x=res[i]*a+res[j]*b;

				insert(x);

			}

		}  

		int cnt=0;

		for(int i=1;i<=100;i++)

		{

			for(int j=1;j<=100;j++)

			{

				int x=res[i]*c+res[j]*d;

				cnt+=search(-x);

			}

		}  

		printf("%d\n",cnt<<4);

	}

	return 0;

}

巴特西

HDU 1496 Equations hash HDU上排名第一！

最新文章

热门文章