难度 | 算法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;
}