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

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

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