uva 1152 ——4 Values whose Sum is 0

我不是女神ヾ 2022-08-10 00:48 109阅读 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 条评论，109人围观）

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

相关阅读

相关 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 赞/ 32 阅读

相关 DioError [DioErrorType.DEFAULT]: RangeError (index): Invalid value: Only valid value is 0:

问题：dio发送post请求一直报错 DioError [DioErrorType.DEFAULT]: RangeError (index): Invalid v

谁践踏了优雅/ 2023年02月19日 09:28/ 0 赞/ 9 阅读

相关 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 赞/ 84 阅读

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

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

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

相关近期简单题目小结 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 赞/ 151 阅读

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

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

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

相关 UVA 11235-Frequent values（RMQ）

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

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

相关 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 赞/ 98 阅读

相关 UVA 400 Unix Is

The computer company you work for is introducing a brand new computer line and is develo

女爷i/ 2022年06月07日 00:40/ 0 赞/ 135 阅读

相关 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 赞/ 545 阅读