平衡奶牛子集(Balanced Cow Subsets G) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void genHalf(const vector<long long>& a, int offset, int len, vector<pair<long long, int>>& out) {
    out.push_back({0, 0});
    for (int i = 0; i < len; ++i) {
        int curSz = (int)out.size();
        int bit = 1 << (offset + i);
        long long v = a[offset + i];
        for (int j = 0; j < curSz; ++j) {
            out.push_back({out[j].first + v, out[j].second | bit});
            out.push_back({out[j].first - v, out[j].second | bit});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int n1 = n / 2;
    int n2 = n - n1;
    vector<pair<long long, int>> L, R;
    L.reserve(60000);
    R.reserve(60000);
    genHalf(a, 0, n1, L);
    genHalf(a, n1, n2, R);
    sort(L.begin(), L.end());
    L.erase(unique(L.begin(), L.end()), L.end());
    sort(R.begin(), R.end());
    R.erase(unique(R.begin(), R.end()), R.end());
    vector<bool> good(1 << n, false);
    int pL = 0, szL = (int)L.size();
    int pR = 0, szR = (int)R.size();
    while (pL < szL && pR < szR) {
        if (L[pL].first < R[pR].first) {
            ++pL;
        } else if (L[pL].first > R[pR].first) {
            ++pR;
        } else {
            long long val = L[pL].first;
            int eL = pL;
            while (eL < szL && L[eL].first == val) ++eL;
            int eR = pR;
            while (eR < szR && R[eR].first == val) ++eR;
            for (int i = pL; i < eL; ++i) {
                for (int j = pR; j < eR; ++j) {
                    good[L[i].second | R[j].second] = true;
                }
            }
            pL = eL;
            pR = eR;
        }
    }
    int ans = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        if (good[mask]) ++ans;
    }
    cout << ans << "\n";
    return 0;
}