poj 2785 hash

题意:

给出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 1000000000
11 #define size 20345677
12 #define key 745
13
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 }

时间: 05-19

poj 2785 hash的相关文章

poj 2785 4 Values whose Sum is 0 哈希

题意: 给4个集合ABCD,问有多少种从中各取一个数和为0的方案. 分析: 枚举前两个数建哈希表,枚举后两个数查找即可. 代码: //poj 2785 //sep9 #include <iostream> using namespace std; const int maxN=4012; const int maxM=3999972; int a[maxN],b[maxN],c[maxN],d[maxN]; int hash[maxM+10]; int e; struct Edge { int

poj 2785

#include <stdio.h>#include <algorithm>#define N 4000using namespace std; int a[N],b[N],c[N],d[N],ab[N*N],cd[N*N]; int main(){int n,ans,i,j,k;while(scanf("%d",&n)!=EOF){ k=0; for(i=0;i<n;i++) scanf("%d %d %d %d",&

poj 3156 hash+记忆化搜索 期望dp

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m; #define N 32 #define mod 10007LL #define mod2 10000007 #define inf 0x3fffffff typedef long long ll; typedef double dd; int f[N]

poj 2785 4 Values whose Sum is 0(sort+二分)

题意: 给你ABCD四个集合,集合中数的个数都为N(N<=4000),如果分别在ABCD四个集合中取一个数,a b c d ,求有多少种可能使得a+b+c+d=0. 当然你可以尝试枚举所有的组合,绝对可以计算出结果,大概有N^4种吧,如果你有足够的时间还是可以算出来的,哈哈. 当然我不是用上面一种方法计算的,那样算肯定超时. 我的做法是求出所有a+b 到ab数组中, 和所有 c+d到cd数组中,然后排序,枚举每个ab,用二分在cd中查找有没有可能组成0.  有个问题就是二分只能返回一个结果,所以

poj 3349 hash的运用

哈希函数思想在查找中是非常重要的一个思想.在数据结构中我们学习的都只是一些简单的函数 比如: 相加取余 相乘取余 相除取余 .... 哈希函数在查找中可以在O(1)时间中查找到数据的位置. 哈希函数的关键在于函数的选取 , 然而不管选择怎么样的函数 , 一般都会存在冲突 , 但是如果函数选取得得当,那么冲突就会减小. poj 3349是一题简单的hash题 我们选取的函数是: 相加取余数 sort(b , b+6 ); x = 0; for(j = 0; j < 6; j++) x = (x*1

POJ 2785(4 Values whose Sum is 0)

[题意描述] 对于给定的四个序列,从每个序列中选出一个数,并让四个数相加,输出所有相加和为0的情况数目. [解题思路] 我们可以考虑前两列的数字相加之和一定与后两列相加和互为相反数,那么我们可以枚举出前两列数字之和,并且,枚举出后两列数据之和的相反数,并对之排序,然后利用二分法进行查找即可. [AC代码] #include<iostream> #include<algorithm> using namespace std; int n,ans,a[4040],b[4040],c[4

poj 2785 4 Values whose Sum is 0 (简单二分)

//每列选一个数相加为0的个数 # include <stdio.h> # include <algorithm> # include <string.h> using namespace std; int ab[4010*4010],cd[4010*4010]; int main() { int n,i,k,j,count,a[4010],b[4010],c[4010],d[4010]; while(~scanf("%d",&n)) { f

POJ 3274 HASH

题目链接:http://poj.org/problem?id=3274 题意+思路: 点击这里 补充:因为有减法运算,所以可能会造成运算后结果为负数,所以需要把结果统一转换成正数[不然数组下标访问不到负数位置],还有要先把0放入哈希表,不然会出现长度为1但是没有匹配的情况 比如:1 3   7 结果为1,如果没把0放进哈希表则结果为0 #include<iostream> #include<algorithm> #include<cstring> #include<

POJ 2785 4 Values whose Sum is 0 (对半分解 二分搜索)

4 Values whose Sum is 0 Time Limit: 15000MS   Memory Limit: 228000K Total Submissions: 17658   Accepted: 5187 Case Time Limit: 5000MS Description The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how