8-3 4Values Whose Sum is Zero 和为0的四个值

给定四个n元素集合 ABCD   要求分别从中取一个元素 abcd   使得他们的合为0   问有多少中取法

map果然炸了

#include<bits/stdc++.h>

using namespace std;

#define N 100000000

int a[N];

int b[N];

int c[N];

int d[N];

map<int,int>mp;

int main()

{

    int cas;cin>>cas;

    while(cas--)

    {   mp.clear();

        int n;cin>>n;

        for(int i=;i<=n;i++)

         scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i])

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

           mp[ a[i]+b[j] ]++;

        int cnt=;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

        {

            int t=-c[i]-d[j];

            cnt+=mp[t];

        }

        printf("%d\n",cnt);

    }

    return ;

}

用hash  但是不知道怎么放入哈希表里  因为每个元素最大值为2 28  总的为2 29  数组根本开不下

然后可以直接从小到大存入数组。。。

并且活用 upper-bound 和low bound ！！！   值得学习！

#include<bits/stdc++.h>

using namespace std;

#define  N 10000

int a[N];

int b[N],c[N],d[N];

int sum[N*N];

int main()

{

   int cas;

   cin>>cas;

   while(cas--)

   {

       int n;cin>>n;

       for(int i=;i<=n;i++)

         scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);

       int cnt=;

       for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

          sum[cnt++]=a[i]+b[j];

        sort(sum,sum+cnt);

        long long ans=;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

              ans+=upper_bound(sum,sum+cnt,-d[j]-c[i])-lower_bound(sum,sum+cnt,-c[i]-d[j]);

        printf("%ld\n",ans);

        if(cas)printf("\n");

   }

}