Meet in the Middle

meet in the middle 是一种类似二分的搜索技巧。

以下题为例：

题目链接：https://cses.fi/problemset/task/1628/

Meet in the Middle

题意

给出一个大小为 $n$ 的数组 $t$ ，问有多少个子集和为 $x$ 。

• $1 \le n \le 40$

• $1 \le x \le 10^9$

• $1 \le t_i \le 10^9$

题解

如果直接枚举的话最多有 $2^{40}$ 种可能，所以可以将原数组分为两个大小相似的新数组，各自枚举新数组的子集，此时枚举的复杂度降到了 $2^{20}$ 。

之后枚举一个数组子集的值，用二分或双指针在另一个数组的子集值中进行查找即可。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;

    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    vector<int> t1, t2;
    for (int i = 0; i < n / 2; i++) {
        t1.push_back(t[i]);
    }
    for (int i = n / 2; i < n; i++) {
        t2.push_back(t[i]);
    }

    vector<long long> a, b;
    auto cal = [](auto v, auto &res) {
        int c = v.size();
        for (int i = 0; i < (1 << c); i++) {
            long long sum = 0;
            for (int j = 0; j < c; j++) {
                if (i & (1 << j)) {
                    sum += v[j];
                }
            }
            res.push_back(sum);
        }
    };
    cal(t1, a), cal(t2, b);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    long long ans = 0;
    for (auto val : a) {
        ans += upper_bound(b.begin(), b.end(), x - val) - lower_bound(b.begin(), b.end(), x - val);
    }
    cout << ans << "\n";

    return 0;
}

参考

https://usaco.guide/gold/meet-in-the-middle?lang=cpp