首页 > 代码库 > poj 2785 hash

poj 2785 hash

2024-09-24 01:58:14   213人阅读

题意：

给出4个数组，每个数组里面挑一个数，和为0；

 

分析：

把前两个数组加起来，hash，枚举后两个数组加起来 的相反数

 

注意：multiset会超时；手写hash

技术分享
 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <set> 6 #include <vector> 7  8 using namespace std; 9 10 #define MAX 100000000011 #define size 2034567712 #define key 74513 14 int hash[size],sum[size];15 16 void hash_insert(int num) {17     int tmp = num;18     num = (num + MAX)%size;19     while(hash[num]!=MAX&&hash[num]!=tmp) {20         num = (num + key)%size;21     }22     hash[num] = tmp;23     sum[num]++;24 }25 26 int hash_Find(int num) {27     int tmp = num;28     num = (num + MAX)%size;29     while(hash[num]!=MAX&&hash[num]!=tmp) {30         num = (num + key)%size;31     }32     if(hash[num]==MAX) return 0;33     return sum[num];34 }35 36 int a[4040],b[4040],c[4040],d[4040];37 38 int main() {39     int n;40     scanf("%d",&n);41 42     for(int i=0; i<size; i++)43         hash[i] = MAX;44     memset(sum,0,sizeof(sum));45 46     for(int i=0; i<n; i++) {47         scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);48     }49 50     for(int i=0; i<n; i++) {51         for(int j=0; j<n; j++) {52             hash_insert(a[i]+b[j]);53         }54     }55 56     int ans = 0;57     for(int i=0; i<n; i++) {58         for(int j=0; j<n; j++) {59             ans+=hash_Find(-(c[i]+d[j]));60         }61     }62 63     cout<<ans<<endl;64     return 0;65 }
View Code

 

poj 2785 hash


联系
我们