P3067 [USACO12OPEN] Balanced Cow Subsets G

难度	算法s	日期	题目链接
提高+/省选−	折半搜索	2025-09-24	https://luogu.com.cn/problem/P3067

这道题在我的任务列表里面很久了，今天下定决心一定要切掉。

题意简述

我们定义一个奶牛集合 $S$ 是平衡的，当且仅当满足以下两个条件：

• $S$ 非空。
• $S$ 可以被划分成两个集合 $A,B$，满足 $A$ 里的奶牛产奶量之和等于 $B$ 里的奶牛产奶量之和。划分的含义是，$A\cup B=S$ 且 $A\cap B=\varnothing$。

现在给定大小为 $n$ 的奶牛集合 $S$，询问它有多少个子集是平衡的。请注意，奶牛之间是互不相同的，但是它们的产奶量可能出现相同。

范围：$1\le n\le 20$，$1\le a_i\le 10^8$。

思路

如果暴力搜索，枚举每种划分方法，每头牛有三种状态：放入集合 $A$、放入集合 $B$、不放。（这样就涵盖了 $S$ 的所有子集）

则总时间复杂度为 $O(3^n)$，$3^{20}\approx3\times10^9$，无法接受。

使用折半搜索，可以把时间复杂度降到 $O(3^{n/2})$，$3^{10}\approx6\times10^4$，温柔得多，可以接受。

---

本题难点在于如何设计折半的方法。

假设在前 $n/2$ 头奶牛中，选 $a_1$ 头放入集合 $A$，$b_1$ 头放入集合 $B$；在后 $n/2$ 头奶牛中，选 $a_2$ 头放入集合 $A$，$b_2$ 头放入集合 $B$。

最终集合 $A$ 和集合 $B$ 要平衡，就是要满足 $a_1+a_2=b_1+b_2$。

可是我们要把前后两个半段分开统计，所以移项一下，变成 $a_1-b_1=b_2-a_2$。

也就是说，我们要在前半段中，分别统计每个 $(a_1-b_1)=k$ 的方案数。即统计 $\text{ans1}[]$，其中 $\text{ans1}[k]=\text{true}$ 代表存在满足 $(a_1-b_1)=k$ 的方案。

后半段也类似，统计 $\text{ans2}[]$，其中 $\text{ans2}[k]=\text{true}$ 代表存在满足 $(b_2-a_2)=k$ 的方案。

---

这对吗？

显然，$a_1-b_1=k$ 一定时，可能有不同的划分方法。所以尽管我们用 $a_1-b_1=b_2-a_2$ 作为判据，但是只记录 $\text{ans}[k]$ 是不行的。我们应该记录对于每个 $k$，划分方式 $s$ 一共有几种。

这对吗？

再读题目，发现题目要求的是 “子集” 的个数。两个子集不同，当且仅当我们选择放入子集的奶牛不同。至于它是放在集合 $A$ 还是集合 $B$，这里并不关心。所以，我们需要去重，避免那些 $A\cup B$ 相同的子集被重复统计。所以，我们应该记录对于每个 $k$，所有的划分方式 $s$。

这里奶牛最多有 $20$ 头，int 是 32 位的，我们考虑使用状态压缩，用 int 存状态。第一次搜索时，我们记录下所有状态 $s_1$；第二次搜索，设一次搜索结束后状态为 $s_2$，我们令 $\text{ans[}s_1|s_2\text{]}=\text{true}$。最后，我们统计 $\text{ans[k]}=\text{true}$ 的一共有几个，就得到了答案。

大功告成！

编码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int cow[MAXN + 1], n;
map<int, vector<unsigned>> states; // state[k] 表示判据为 k 的所有状态
bool ans[(1 << 21) + 1]; // ans[s] 表示这种划分方式是否存在
void dfs1(int dep, int value, unsigned state) {
    if (dep > n / 2) {
        states[value].push_back(state);
    } else {
        // 放入集合 A
        dfs1(dep + 1, value + cow[dep], state | (1 << dep));
        // 不放
        dfs1(dep + 1, value, state);
        // 放入集合 B
        dfs1(dep + 1, value - cow[dep], state | (1 << dep));
    }
}
void dfs2(int dep, int value, unsigned state) {
    if (dep > n) {
        if (!states.count(value)) return;
        for (auto s : states[value]) {
            ans[s | state] = true;
        }
    } else {
        // 放入集合 A
        dfs2(dep + 1, value - cow[dep], state | (1 << dep));
        // 不放
        dfs2(dep + 1, value, state);
        // 放入集合 B
        dfs2(dep + 1, value + cow[dep], state | (1 << dep));
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> cow[i];
    dfs1(1, 0, 0);
    dfs2(n / 2 + 1, 0, 0);
    int total = 0;
    for (auto i : ans) total += i;
    cout << total - 1 << endl; // 排除空集的情况
    return 0;
}