HDU (1895 Sum Zero 比较技巧型的模拟+hash)

spoiler posted @ 2011年5月11日 22:33 in 未分类 , 1402 阅读

题目大意:给你5组数,让你求A[0][i]+A[1][j]+A[2][k]+A[3][l]+A[4][m]=0的组数

题目分析:如果直接暴力枚举的话,唉,肯定超时,5重循环想都不用想了,我们看看这题的思路吧,我也是参考大牛的思路的,这里的优化很高效,大家注意分析哦{^_^};首先我们把5行中的4行 两两进行相加合成二行,然后我们这里只有3组数据,然后对数据进行稍微处理一下,首先把其中的两行进行排序,头两行进行从大到小的排序,最后一行从小到大排序,然后我们遍历第一行,作为外循环,然后从第二行的第一个开始(每次遍历都从第二行的第一个开始的),把tempt下标停到第三行足够大的位置上,也就是满足前面两个加上该位置的值大于等于0,因为前面两行数据都是递减排列的,前面不满足后面肯定不满足,所以下次讨论的时候只需要从tempt位置开始讨论,这样节约了很多不必要的时间。以后的讨论都从上次的tempt的位置开始,因为前面与第三个加起来小于0,我遍历下去的值肯定也是小于0,所以只需要从tempt开始。

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 302
using namespace std;
int B[N*N],s[3][N*N],A[5][N*N],cnt[5][N*N],num[5];
int get(int n,int k,int C[]){
	int i,j;
	for(i=0;i<=n;i++)
		cnt[k][i]=0;
	j=0;
	s[k][0]=C[0];
	cnt[k][0]=1;
	for(i=1;i<n;i++){
		if(s[k][j]!=C[i])
			s[k][++j]=C[i];
		cnt[k][j]++;//这个是记录各个情况的次数的
	}
	num[k]=j+1;
	return 0;
}
int cmp(int a,int b){
	return a>b;
}
int main(){
	int cas,n,i,j,tempt,pos,ans,k;
	int xx;
	scanf("%d",&cas);
	while(cas--){
		ans=0;
		for(j=0;j<=4;j++){
			scanf("%d",&n);
			num[j]=n;
			for(i=0;i<n;i++)
				scanf("%d",&A[j][i]);
		}
		sort(A[0],A[0]+num[0],cmp);
		get(num[0],0,A[0]);
		k=0;
		for(i=0;i<num[1];i++)
	 		for(j=0;j<num[2];j++)
				B[k++]=A[1][i]+A[2][j];
		num[1]=k;
		sort(B,B+num[1],cmp);
                //注意第三行是从小到大哦!
		get(num[1],1,B);
		k=0;
		for(i=0;i<num[3];i++)
			for(j=0;j<num[4];j++)
				B[k++]=A[3][i]+A[4][j];
		num[3]=k;
		sort(B,B+num[3]);
		get(num[3],2,B);
		tempt=0;
		for(i=0;i<num[0];i++){
			xx=s[0][i]+s[1][0];
			while(tempt<num[2]&&xx+s[2][tempt]<0)
				tempt++;
			if(tempt==num[2])
                    //这里说明没有任何一种情况的和是大于等于0的
                    //所以没必要讨论了 还是那句话,因为前两行   
                     //是从大到小排列的,前面的情况的和小于0后
                      //面就不用考虑了	
				break;
			if(xx+s[2][tempt]==0)
				ans+=cnt[0][i]*cnt[1][0]*cnt[2][tempt];
			pos=tempt;
			for(j=1;j<num[1];j++){
				xx=s[0][i]+s[1][j];
				while(pos<num[2]&&xx+s[2][pos]<0)
					pos++;
				if(pos==num[2])
						break;
				if(xx+s[2][pos]==0)
					ans+=cnt[0][i]*cnt[1][j]*cnt[2][pos];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter