Uva 1152 进来学学中途相遇法

一、题意

给定4个n元素（1<=n<=4000）的集合A,B,C,D，要求分别从中选取一个元素a,b,c,d，使得a+b+c+d=0。
问有多少种取法。

二、解析

直接4重循环暴力肯定超时。
回想若只有两个集合时，我们会通过map来存储其中一个集合A的值，然后遍历另外一个集合B来从map中询问是否有-b存在。
在这里也可以用类似的思想。

先用二重循环遍历集合A,B，然后把选取的a+b的值放入map中，然后再用二重循环遍历C,D，去询问map中有无-c-d存在。
时间复杂度为O(n^2lgn)，由于n<=4000，还是会有超时风险，因此改用unordered_map即可。

三、代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
using LL = long long;
int kase, n;

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        vector<int> A, B, C, D;
        for(int i = 0, a, b, c, d; i < n; i ++) {
            cin >> a >> b >> c >> d;
            A.push_back(a), B.push_back(b), C.push_back(c), D.push_back(d);
        }
        unordered_map<int, LL> sum_cnt;
        for(auto a : A) for(auto b : B) sum_cnt[a + b] ++;
        LL ans = 0;
        for(auto c : C) for(auto d : D) if(sum_cnt.count(-c - d)) ans += sum_cnt[-c - d];
        cout << ans << endl;
        if(kase) cout << endl;
    }
}

四、归纳

• 紫薯中，这种方法叫中途相遇法，感觉还挺常见的。