题目链接：https://vjudge.net/problem/UVA-1152
这题题意就是在四个集合内。每个集合分别里挑一个数a,b,c,d，求a+b+c+d=0有多少种选法。
暴力的话就是四重循环，复杂度O(n^4)容易超时。稍微优化一点就是分别枚举其中三个集合里的元素a+b+c，然后用二分查找剩下那个集合里存不存在a+b+c的相反数，复杂度O(n^3*logn)勉强还行。
不过可以枚举a+b,放入map中，然后枚举-c-d，看看-c-d有多少种方法能写成a+b。复杂度O(n^2*logn)，但由于map是用红黑树实现的，很容易超时，但c++11提供了unordered_map，用哈希函数实现的
，问题就解决了。
#include<bits/stdc++.h> using namespace std; #define ll long long unordered_map<ll,ll> mp; ll a[10005],b[10005],c[10005],d[10005]; int main() { int T,n,x; cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { mp[a[i]+b[j]]++; } } ll ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { ans=ans+mp[-c[i]-d[j]]; } } cout<<ans<<"\n"; if(T) cout<<"\n"; mp.clear(); } return 0; }
4 Values whose Sum is 0 UVA 1152
原文：https://www.cnblogs.com/hh13579/p/11192236.html