P3067 [USACO12OPEN]Balanced Cow Subsets G（折半搜索）

题目大意：

给n( ≤ 20 \le20 ≤20)个数，从中任意选出一些数，使这些数能分成和相等的两组。
求有多少种选数的方案。
（来源：洛谷）

解题思路：

先思考下，每种数有多少种取法，可以看出（一开始我就没看出 ）有3种取法：不取，放入左集合与放入右集合，直接暴力的话就是 O ( 3 20 ) O(3^{20}) O(320)，所以我们试着采取折半搜索

在采取折半搜索之前，我们先明确放入左右集合的区别，因为要求两个集合相等，则它们相差为0，若放入左集合相当于加上一个数，则放入右集合相当于减去一个数

若折半搜索可行

• 相遇的状态就是它们的数相等，但是因为互相组合在一起时，可能造成相同选数的情况下被多次计算，所以我们开个结构体，额外记录两次搜索每次搜索到状态的选数情况，对于已经选过的数不会再选
• 同时我们排序之后利用二分查找初搜索中找到的数，在末搜索中相同状态的区间，暴力统计即可

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 10;
const int maxm = (1 << 20) + 1;
bool vis[maxm];
int n, cnt1, cnt2, a[maxn];
struct P {
    ll sum;
    int state;
    friend bool operator < (P lhs, P rhs) {
        return lhs.sum > rhs.sum;
    }
} p1[maxm], p2[maxm];
bool cmp (P lhs, P rhs) {return lhs.sum < rhs.sum;}
void dfs(int lc, int rc, ll sum, int state, P *p, int &cnt) {
    if (lc > rc) {
        p[++cnt] = {sum, state};
        return;
    }
    dfs(lc + 1, rc, sum, state, p, cnt);
    dfs(lc + 1, rc, sum - a[lc], state | (1 << (lc - 1)), p, cnt);
    dfs(lc + 1, rc, sum + a[lc], state | (1 << (lc - 1)), p, cnt);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    dfs(1, n / 2, 0, 0, p1, cnt1),
    dfs(n / 2 + 1, n, 0, 0, p2, cnt2);
    sort (p1 + 1, p1 + cnt1 + 1, cmp);
    sort (p2 + 1, p2 + cnt2 + 1, cmp);
    for (int i = 1, lef, rig; i <= cnt1; i++) {
        int lc = 1, rc = cnt2, mc = (lc + rc) >> 1;
        // 找出相同的数字的左边界以及右边界
        while (lc <= rc) {
            if (p1[i].sum <= p2[mc].sum) lef = mc, rc = mc - 1;
            else lc = mc + 1;
            mc = (lc + rc) >> 1;
        }
        lc = 1, rc = cnt2, mc = (lc + rc) >> 1;
        while (lc <= rc) {
            if (p1[i].sum >= p2[mc].sum) rig = mc, lc = mc + 1;
            else rc = mc - 1;
            mc = (lc + rc) >> 1;
        }
        for (int j = lef; j <= rig && j <= cnt2 && p1[i].sum == p2[j].sum; j++) //多个判断主要是为了防止没有相同的导致越界
            vis[p1[i].state | p2[j].state] = 1;
    }
    int ans = 0;
    for (int i = 1; i < (1 << n); i++)
        if (vis[i])
            ans++;
    cout << ans << endl;
}