POJ 2549 Sumsets hash值及下标

题目大意：
找到几何中的4个数字使他们能够组成 a+b+c=d , 得到最大的d值

我们很容易想到a+b = d-c

那么将所有a+b的值存入hash表中，然后查找能否在表中找到这样的d-c的值即可

因为4个数字都不能相同，那么我们同时要在hash表中记录相加两个数的下标，然后查找的时候还要进行下标判断

这里用二分查找也可以，但是能用hash还是hash快地多了

这里第一次写到对负数进行hash，还是傻傻地 val%MOD , 但是负数得到的模值为负，作为hash的下标会RE，所以RE了一发，还是看别人的题解才找到这个错误，要谨记

遇到负数要先取绝对值后再hash

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <climits>
 6 using namespace std;
 7 #define N 1010
 8 #define MOD 1000007
 9 #define base 31
10 
11 struct HashNode{
12     int val , next;
13     int x , y;
14 }_hash[MOD];
15 
16 int head[MOD+5] , k , a[N];
17 
18 void insertHash(int key , int x , int y)
19 {
20     int pos = ((key<0)?-key:key)%MOD;
21     _hash[k].val = key , _hash[k].next = head[pos] , _hash[k].x=x , _hash[k].y=y;
22     head[pos] = k++;
23 }
24 
25 bool searchHash(int key , int a , int b)
26 {
27     int pos = ((key<0)?-key:key)%MOD;
28     for(int i=head[pos] ; ~i ; i=_hash[i].next){
29         if(key == _hash[i].val){
30             if(a==_hash[i].x||a==_hash[i].y||b==_hash[i].x||b==_hash[i].y) continue;
31             return true;
32         }
33     }
34     return false;
35 }
36 
37 bool cmp(int a , int b)
38 {
39     return a>b;
40 }
41 
42 int main()
43 {
44     #ifndef ONLINE_JUDGE
45         freopen("a.in" , "r" , stdin);
46     #endif // ONLINE_JUDGE
47     int n;
48     while(scanf("%d" , &n) , n)
49     {
50         memset(head , -1 , sizeof(head));
51         k=0;
52         for(int i=0 ; i<n ; i++) scanf("%d" , &a[i]);
53         sort(a , a+n , cmp);
54         for(int i=0 ; i<n ; i++){
55             for(int j=i+1 ; j<n ; j++){
56                 int v = a[i]+a[j];
57                 insertHash(v , i , j);
58             }
59         }
60         int ret = INT_MIN;
61         for(int i=0 ; i<n ; i++){
62             for(int j=0 ; j<n ; j++){
63                 if(i==j) continue;
64                 int v = a[i]-a[j];
65                 if(searchHash(v , i , j)){
66                     ret = max(ret , a[i]);
67                     break;
68                 }
69             }
70             if(ret!=INT_MIN) break;
71         }
72         if(ret==INT_MIN) printf("no solution
");
73         else printf("%d
" , ret);
74     }
75     return 0;
76 }

POJ 2549 Sumsets hash值及下标

相关推荐