当前位置:威尼斯 > 威尼斯人登录网站 > 先求出来前两列和后两列的和,当一个数列中有

先求出来前两列和后两列的和,当一个数列中有

文章作者:威尼斯人登录网站 上传时间:2019-09-23

4 Values whose Sum is 0

传送门:http://poj.org/problem?id=2785

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 .

Time Limit:15000MS

Description

Input

Memory Limit:228000K

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 .

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 2 28 ) that belong respectively to A, B, C and D .

Total Submissions:29243

Input

Output

Accepted:8887

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 .

For each input file, your program has to write the number quadruplets whose sum is zero.

威尼斯,Case Time Limit:5000MS

Output

Sample Input

Description

For each input file, your program has to write the number quadruplets whose sum is zero.

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

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 .

Sample Input

Sample Output

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
5

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 .

Sample Output

Hint

Output

5

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).

For each input file, your program has to write the number quadruplets whose sum is zero.

Hint

题意:求四个数的和为0的情况有几种

Sample Input

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). 

题解:折半枚举+sort,,很重要的小技巧:upper_bound(a,a+n,s)-low_bound(a,a+n,s)表示a数组(已排序)里等于s的个数,

6-45 22 42 -16-41 -27 56 30-36 53 -37 77-36 30 -75 -4626 -38 -10 62-32 -54 -6 45

 

刚开始用if(all[lower_bound(all,all+n*n,-a[i]-b[j])-all]==-a[i]-b[j])处理wa了,发现原来是因为只算了一个相等的情况,要是有几个同时等于就漏了

Sample Output

 

威尼斯 1威尼斯 2

5

给你一个数字n,然后有n组每组4个数,求每一列取出一个数,使最终四个数的和为0,求有多少种组合方式

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007

using namespace std;

const double g=10.0,eps=1e-9;
const int N=4000+5,maxn=10000+5,inf=0x3f3f3f3f;

ll a[N],b[N],c[N],d[N];
ll all[N*N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 //   cout<<setiosflags(ios::fixed)<<setprecision(2);
    ll n;
    while(cin>>n){
        for(ll i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i]>>d[i];
        for(ll i=0;i<n;i++)
        {
            for(ll j=0;j<n;j++)
            {
                all[i*n+j]=c[i]+d[j];
            }
        }
        sort(all,all+n*n);
        ll ans=0;
        for(ll i=0;i<n;i++)
        {
            for(ll j=0;j<n;j++)
            {
                ans+=upper_bound(all,all+n*n,-a[i]-b[j])-lower_bound(all,all+n*n,-a[i]-b[j]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Hint

 

View Code

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).题意:ABCD四个数列,每个数列抽一个数字,使得和为0,问一共有几组。当一个数列中有多个相同的数字时,把他们作为不同的数字看待。思路:直接爆搜肯定会超时,将它们对半分成AB和CD再考虑就可以解决。比如在AB中取出a,b后,CD中要取出-a-b,因此先把CD中所有取数字的情况n*n种给纪录下来,然后排序,用二分查找次数。

解题思路:先求出来前两列和后两列的和,然后二分就可以了,对于这道题来说结果没有去重

 

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<cstdlib>#include<queue>#include<set>#include<vector>using namespace std;#define INF 0x3f3f3f3f#define eps 1e-10typedef long long ll;const int maxn = 4002;const int mod = 1e9 + 7;int gcd(int a, int b) {    if (b == 0) return a;  return gcd(b, a % b);}int n;int a[maxn],b[maxn],c[maxn],d[maxn];int cd[maxn*maxn];void solve(){    for(int i=0;i<n;i++)        for(int j=0;j<n;j++)        {            cd[i*n+j]=c[i]+d[j];        }    sort(cd,cd+n*n);    ll res=0;    for(int i=0;i<n;i++)        for(int j=0;j<n;j++)        {            int ab=-(a[i]+b[j]);            res+=upper_bound(cd,cd+n*n,ab)-lower_bound(cd,cd+n*n,ab);        }    cout<<res<<endl;}int main(){    scanf("%d",&n);    for(int i=0;i<n;i++)        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);        solve();}
 1 #include<vector>
 2 #include<set>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 vector <int > a;
 8 vector <int > b;
 9 vector <int > c;
10 vector <int > d;
11 vector <int > sum1;
12 vector <int > sum2;
13 int main()
14 {
15     int n, i, j, a1, b1, c1, d1, sum;
16     while(scanf("%d", &n)!=EOF) {
17         sum = 0;
18         for(i = 0; i < n; i++)
19         {
20             scanf("%d%d%d%d", &a1, &b1, &c1, &d1);
21             a.push_back(a1);
22             b.push_back(b1);
23             c.push_back(c1);
24             d.push_back(d1);
25         }
26         for(i = 0; i < n; i++) {
27             for(j = 0; j < n; j++) {
28                 sum1.push_back(a[i] + b[j]);
29                 sum2.push_back(c[i] + d[j]);
30             }
31         }
32             
33     /*    for(i = 0; i < sum1.size(); i++) {
34             for(j = 0; j < sum2.size(); j++) {
35                 if(sum1[i]+sum2[j] == 0) {
36                     sum++;
37                 }
38             }
39         }*/
40         n = sum2.size();
41         sort(sum2.begin(),sum2.end());
42         
43         for(i = 0; i < n; i++) {
44             int l = 0, r = n-1, mid;
45             while(l <= r) {
46                 mid = (l + r) / 2;
47                 if(sum1[i] + sum2[mid] == 0) {
48                     sum++;
49                     for(j = mid + 1; j < n; j++) {
50                         if(sum1[i] + sum2[j] != 0) 
51                             break;
52                         else 
53                             sum++;
54                     }
55                     for(j = mid - 1; j >= 0; j--) {
56                         if(sum1[i] + sum2[j] != 0) 
57                             break;
58                         else 
59                             sum++;
60                     }
61                     break;
62                 }
63                 if(sum1[i] + sum2[mid] < 0) 
64                     l = mid + 1;
65                 else 
66                     r = mid - 1;
67             }
68         }
69         printf("%dn", sum);
70     }
71     return 0;
72 }

 

 

本文由威尼斯发布于威尼斯人登录网站,转载请注明出处:先求出来前两列和后两列的和,当一个数列中有

关键词: