| 难度 | 算法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 {// 放入集合 Adfs1(dep + 1, value + cow[dep], state | (1 << dep));// 不放dfs1(dep + 1, value, state);// 放入集合 Bdfs1(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 {// 放入集合 Adfs2(dep + 1, value - cow[dep], state | (1 << dep));// 不放dfs2(dep + 1, value, state);// 放入集合 Bdfs2(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;
}