4 Values whose Sum is 0

​​4 Values whose Sum is 0​​

如果直接暴力枚舉的話，其複雜度為\(O(n^4)\)，這是必然逾時的。

但是如果把這四個序列分成兩半，通過周遊一半，而到另外一半去進行二分查找的話，複雜度就可以降為\(O(n^2log(n))\)。

// Created by CAD on 2020/2/2.
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=4005;
int a[maxn],b[maxn],c[maxn],d[maxn],s1[maxn*maxn],s2[maxn*maxn];
int main()
{
    int n;  cin>>n;
    for(int i=1;i<=n;++i)
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    int cnt=0;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=n;++j)
            s1[++cnt]=a[i]+b[j],s2[cnt]=c[i]+d[j];
    sort(s2+1,s2+1+cnt);
    int ans=0;
    for(register int i=1;i<=cnt;++i)
        ans+=upper_bound(s2+1,s2+1+cnt,-s1[i])-lower_bound(s2+1,s2+1+cnt,-s1[i]);
    printf("%d\n",ans);
    return 0;
}      

同時又想到可以用 map 來進行查值，複雜度與二分相同，但是由于常數過大逾時了，是以用​

​unordered_map​

​​進行優化，它是用哈希表進行存值的，平均查找複雜度為\(O(1)\)，但是由于 POJ 沒有​

​unordered_map​

​這個頭檔案，是以送出不了。

// Created by CAD on 2020/2/2.
#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;
const int maxn=4005;
int a[maxn],b[maxn],c[maxn],d[maxn],s[maxn*maxn];
unordered_map<int,int> m;
int main()
{
    m.clear();
    int n;  cin>>n;
    for(int i=1;i<=n;++i)
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    int cnt=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            s[++cnt]=a[i]+b[j],m[c[i]+d[j]]++;
    int ans=0;
    for(int i=1;i<=cnt;++i)
        ans+=m[-s[i]];
    printf("%d\n",ans);
    return 0;
}