HDU （1895 Sum Zero 比较技巧型的模拟+hash）

题目大意：给你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;
}