uva 1152 ——4 Values whose Sum is 0

我不是女神ヾ 2022-08-10 00:48 122阅读 0赞

题意：给定4个n元素集合，要求从每个集合中选择一个数，使得A+B+c+d==0，问存在多少种方法。

思路：枚举+hash判断。直接枚举4次方的算法会超，那么只需要枚举ab，然后在c+d的和中查找等于-（a+b）的值（用mp或hash，n2logn的算法）。

Code：

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=4005;
    int a[N],b[N],c[N],d[N];
    struct Hash_map
    {
        static const int m=0x7fffff;
        int p[m+1],q[m+1];
        void cls(){for (int i=0;i<=m;i++) q[i]=0;}
        int& operator[] (int k)
        {
            int i;
            for (i=k&m;q[i]&&p[i]!=k;i=(i+1)%m);
            p[i]=k;
            return q[i];
        }
    }has;
    int main()
    {
        int T,n;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d",&n);
            for (int i=1;i<=n;i++) scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
            int ans=0;has.cls();
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    has[a[i]+b[j]]++;
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    ans+=has[-(c[i]+d[j])];
                printf("%d\n",ans);
                if (T) puts("");
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2785 4 Values whose Sum is 0

题目： POJ 2785 4 Values whose Sum is 0 ，哈哈，我们今天来看一道稍微简单的二分题嘛，这是选自POJ上的一道题，好了，我们一起来看看题...

客官°小女子只卖身不卖艺/ 2024年04月20日 07:15/ 0 赞/ 57 阅读

相关 UVA 1152 --4 Values whose Sum is 0（枚举--中途相遇法）

4 Values whose Sum is 0 Time Limit:9000MS Memory Limit:0KB 64bit IO Format:%lld & %ll

「爱情、让人受尽委屈。」/ 2024年02月17日 22:44/ 0 赞/ 45 阅读

相关 POJ 2785-4 Values whose Sum is 0（a+b+c+d=0-折半枚举）

4 Values whose Sum is 0 <table> <tbody> <tr> <td><strong>Time Limit:</strong>&

雨点打透心脏的1/2处/ 2022年09月21日 05:33/ 0 赞/ 95 阅读

相关折半枚举（双向搜索） —— 4 Values whose Sum is 0 POJ - 2785 题解

题目链接 > https://vjudge.net/problem/POJ-2785 题目简述 > 有ABCD四个数组，从每个数组中选取出一个元素，求和为0的所有

﹏ヽ暗。殇╰゛Y/ 2022年09月03日 00:23/ 0 赞/ 14 阅读

相关近期简单题目小结 UVA 100+HDU 2007+URAL 1084+Poj 1152+UVA 10042+UVA 11752+UVA 10780

新年练习赛(http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40140\overview密码password)和之前

我不是女神ヾ/ 2022年08月24日 14:18/ 0 赞/ 166 阅读

相关 uva 11997——K Smallest Sums

题意：给定k个含k个数的数列，然后每次从每个序列中取出一个相加，然后问所有的数中前k小的。思路：将每个表排序后然后插入优先队列中，依次是a\[0\]+b\[0\]

喜欢ヅ旅行/ 2022年08月21日 04:17/ 0 赞/ 20 阅读

相关 uva 1152 ——4 Values whose Sum is 0

题意：给定4个n元素集合，要求从每个集合中选择一个数，使得A+B+c+d==0，问存在多少种方法。思路：枚举+hash判断。直接枚举4次方的算法会超，那么只需要枚举a

我不是女神ヾ/ 2022年08月10日 00:48/ 0 赞/ 123 阅读

相关 UVA 11235-Frequent values（RMQ）

Frequent values ![20160808170630404][] 题目意思：给出一个非降序排列的整数数组A，对于一系列询问（L,R），求出AL~A

浅浅的花香味﹌/ 2022年07月19日 02:00/ 0 赞/ 101 阅读

相关 poj 2785 4 Values whose Sum is 0

4 Values whose Sum is 0 <table> <tbody> <tr> <td><strong>Time Limit:</strong>&

你的名字/ 2022年06月16日 10:57/ 0 赞/ 111 阅读

相关 RangeError (index): Invalid value: Valid value range is empty: 0

场景最近在学习flutter,运行时碰到了这个错误。 I/flutter (25300): ══╡ EXCEPTION CAUGHT BY WIDGETS LIBR

快来打我*/ 2022年02月24日 17:14/ 0 赞/ 556 阅读