文章出處
文章列表
4 Values whose Sum is 0
| Time Limit: 15000MS | Memory Limit: 228000K | |
| Total Submissions: 19322 | Accepted: 5778 | |
| 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 many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
（是不是先得翻譯 ）題意大概是給定四個長度為n的數組，求四個數組各取一個元素和為0的取法有幾種（考慮順序）
首先有兩種做法，一種二分，一種哈希
看一眼數據規模知道枚舉每一位的O（n^4）絕對超時
所以觀察題目，發現只要求和為0，那么考慮只枚舉出前兩個數組的任意元素和與后兩個數組任意元素和
這樣再枚舉一遍前兩個數組的任意元素和，檢查是否有對應元素和為0即可
接下來還要再優化
二分寫得很簡單，具體代碼在《挑戰程序設計競賽》第23頁不想寫
再來看哈希
把兩數組的元素和得出一個鍵值（就是哈希值）接下來鏈式儲存進去
什么叫鏈式呢？就是和鄰接表差不多
把哈希映射的數組當成head數組，把原值當成邊，存原值和next也就是哈希值相同的下一個值的為止
注意這道題還得再優化，多存一個同一數值的重復次數而不是分開存，不然會MLE沒錯這是省空間用的
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 const int mod=1000007;
5 typedef struct{
6 int val;
7 int num;
8 int next;
9 }node;
10 int data[4005][4];
11 int n,tot=0;
12 int hash[mod+1];
13 node all[16000000];
14 int abs(int num){
15 return num>0?num:(-1)*num;//考慮負數！考慮負數！考慮負數！
16 }
17 int get(int num){
18 return (abs(num))%mod;
19 }
20 int add(int num){
21 int tmp=get(num);
22 int p=1;
23 if(hash[tmp]){
24 for(p=hash[tmp];p!=0;p=all[p].next){
25 if(all[p].val==num){
26 all[p].num++;
27 break;
28 }
29 }
30 }
31 if((!hash[tmp])||(p==0)){
32 all[++tot].val=num;
33 all[tot].num=1;
34 all[tot].next=hash[tmp];
35 hash[tmp]=tot;
36 }
37 return 0;
38 }
39 int find(int num){
40 int tmp=get(num);
41 int p;
42 for(p=hash[tmp];p;p=all[p].next){
43 if(all[p].val==num)return all[p].num;
44 }
45 return 0;
46 }
47 int main(){
48 memset(hash,0,sizeof(hash));
49 memset(all,0,sizeof(all));
50 int n;
51 scanf("%d",&n);
52 for(int i=1;i<=n;i++)scanf("%d %d %d %d",&data[i][1],&data[i][2],&data[i][3],&data[i][4]);
53 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)add(data[i][1]+data[j][2]);
54 int ans=0;
55 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans+=find(-(data[i][3]+data[j][4]));
56 printf("%d",ans);
57 return 0;
2 #include<stdlib.h>
3 #include<string.h>
4 const int mod=1000007;
5 typedef struct{
6 int val;
7 int num;
8 int next;
9 }node;
10 int data[4005][4];
11 int n,tot=0;
12 int hash[mod+1];
13 node all[16000000];
14 int abs(int num){
15 return num>0?num:(-1)*num;//考慮負數！考慮負數！考慮負數！
16 }
17 int get(int num){
18 return (abs(num))%mod;
19 }
20 int add(int num){
21 int tmp=get(num);
22 int p=1;
23 if(hash[tmp]){
24 for(p=hash[tmp];p!=0;p=all[p].next){
25 if(all[p].val==num){
26 all[p].num++;
27 break;
28 }
29 }
30 }
31 if((!hash[tmp])||(p==0)){
32 all[++tot].val=num;
33 all[tot].num=1;
34 all[tot].next=hash[tmp];
35 hash[tmp]=tot;
36 }
37 return 0;
38 }
39 int find(int num){
40 int tmp=get(num);
41 int p;
42 for(p=hash[tmp];p;p=all[p].next){
43 if(all[p].val==num)return all[p].num;
44 }
45 return 0;
46 }
47 int main(){
48 memset(hash,0,sizeof(hash));
49 memset(all,0,sizeof(all));
50 int n;
51 scanf("%d",&n);
52 for(int i=1;i<=n;i++)scanf("%d %d %d %d",&data[i][1],&data[i][2],&data[i][3],&data[i][4]);
53 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)add(data[i][1]+data[j][2]);
54 int ans=0;
55 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans+=find(-(data[i][3]+data[j][4]));
56 printf("%d",ans);
57 return 0;
58 }
文章列表
全站熱搜
留言列表
