HDU 4334 Trouble

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

这题首先想到的就是穷举每一行中的数字，相加看是否为0 。 ----别傻了，n⁵ 的循环，等着超时吧！

现在要做的事如何缩减循环次数。先枚举头两行相加的可能结果，发现有些数的和是重复的！也就是说，可能会有多余的循环存在。
于是可以先计算出头两行的所以和结果，再去重，再计算3、4行的和结果、去重，拿前面得到的两个数组再和最后一行枚举相加判断就
能得到结果。这样复杂度变为n³快了，但是还不够。可以再把之前得到的两个新数组排序下，枚举第5行，对于每次枚举,两个排序后的
数组，一个从小到大，一个从大到小查找，发现相加结果比0大，就把大的数组往小的方向移（如果要移小的数组，只可能增大结果）。
发现相加结果比0小，就把小的数组往大的方向移。可以AC了。

　　还有一种方法就是哈希。把头两行的所有和结果记录下来，可以设个数组初始为0，当出现一个和是，就把数组中下标为和的元素置1.
枚举后三行的所有和结果，发现存在和的负数为下标（下标当然有个偏移量，怎么可能为负）在数组中为1，则说明满足条件。
新的问题是数组开10¹⁵是会爆的，所以用取模哈希，为了处理哈希值重复的情况，每个数组元素都要接个链表，记录哈希重复的不同数值。

排序法：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include<algorithm>
 4 using namespace std;
 5 long long a[5][205];
 6 int hb(long long *a,long long *b,int na,int nb,long long *&t)
 7 {
 8     long long *temp=new long long[na*nb+1];
 9     int nn=0;
10     for (int i=0;i<na;++i)
11      for (int j=0;j<nb;++j)
12        temp[nn++]=a[i]+b[j];
13     sort(temp,temp+nn);
14     nn = unique(temp,temp+nn)-temp;
15     t=temp;
16     return nn;
17 }
18 int main()
19 {
20     int T;
21     scanf("%d",&T);
22     while (T--)
23     {
24         int n;
25         scanf("%d",&n);
26         for (int i=0;i<5;++i)
27          for (int j=0;j<n;++j) scanf("%I64d",&a[i][j]);
28          long long *t1,*t2;
29          int n1,n2;
30          n1=hb(a[0],a[1],n,n,t1);
31          n2=hb(a[2],a[3],n,n,t2);
32          bool fla=false;
33          for (int i=0;i<n&&!fla;++i)
34          {
35              int x=0,y=n2-1;
36              register long long tt=a[4][i];
37              while (x<n1 && y>=0)
38              {
39                  if (t1[x]+t2[y]+tt>0) --y;
40                  if (t1[x]+t2[y]+tt<0) ++x;
41                  if (t1[x]+t2[y]+tt==0) {fla=true;break;}
42              }
43          }
44          if (fla) printf("Yes\n"); else printf("No\n");
45          delete []t1;delete []t2;
46     }
47 }

哈希法：

 1 #include <stdio.h>
 2 #include <string.h>
 3 long long a[5][205];
 4 long long v[90000];
 5 int h[1000020],hn,ne[90000];
 6 int hash(long long  sum)
 7 {
 8     int k;
 9     if(sum>0) k=(int)(sum %  1000007);
10        else k=(int)(-sum % 1000007);
11     return k ;
12 }
13 void add(int k,long long sum)
14 {
15     v[hn] = sum;
16     ne[hn] = h[k];
17     h[k] =hn++;
18 }
19 
20 int main()
21 {
22     int T;
23     scanf("%d",&T);
24     while (T--)
25     {
26         int n;
27         scanf("%d",&n);
28         for (int i=0;i<5;++i)
29          for (int j=0;j<n;++j) scanf("%I64d",&a[i][j]);
30          hn=0;
31         for (int i=0;i<1000020;++i) h[i]=-1;
32         bool fla=false;
33         for (int q1=0;q1<n&&!fla;++q1)
34         for (int q2=0;q2<n&&!fla;++q2)
35         {
36             long long s=a[0][q1]+a[1][q2];
37             add(hash(s),s);
38         }
39         for (int q3=0;q3<n&&!fla;++q3)
40         for (int q4=0;q4<n&&!fla;++q4)
41         for (int q5=0;q5<n&&!fla;++q5)
42         {
43             long long s=a[2][q3]+a[3][q4]+a[4][q5];
44             for (int x=h[hash(-s)];x!=-1;x=ne[x])
45             {
46                 if (s+v[x]==0) {fla=true;break;}
47             }
48         }
49         if (fla) printf("Yes\n"); else printf("No\n");
50     }
51 
52 }

这题之前WA了好几次，思路是对的，就错在细节上：

1）输入储存数组的范围开小了，认为每行最多50个数~

2）用qsort()时，比较函数cmp 返回的是int ，但我拿两个long long 的差来返回，高位截断，排序就不对了