洛谷原题链接：P3067 [USACO12OPEN] Balanced Cow Subsets G

题意：

有 $n$ 个数，第 $i$ 个数大小为 $M(i)$，要从 $n$ 头奶牛中选出一个奶牛子集 $S$ 使得 $S$ 能够被划分成两个子集 $L$ 和 $R$，其中 $L$ 子集内的奶牛总产量等于 $R$ 子集内的奶牛总产量。问有多少个 $S$ 符合条件。

---

翻译：

有 $n$ 个数构成多重集 $M$，第 $i$ 个数为 $M(i)$，从中选出一个子集 $S$ 使得 $S$ 能够划分为两个子集 $L$ 和 $R$，使得 $L$ 和 $R$ 内元素之和相等，求 $S$ 的个数。

---

暴力思路：

最简单的想法必然是暴力——直接深搜，每次要么把当前奶牛加入 $L$ 子集，要么加入 $R$ 子集，要么都不加入，最终判断 $L$ 子集内的奶牛总产量是否等于 $R$ 子集内的奶牛总产量即可

该版本の代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans=0,a[25],sum[25],s[25];
void dfs(int dep=1,int L=0,int R=0){ //核心深搜代码
    if(dep>n){
        if(L==R)ans++;
        return;
    }
    if(min(L,R)+sum[n]-sum[dep-1]<max(L,R))return; //小优化
    dfs(dep+1,L+a[dep],R); //加入L子集
    dfs(dep+1,L,R+a[dep]); //加入R子集
    dfs(dep+1,L,R); //不加入
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    dfs();
    cout<<(ans>>1);
    return 0;
}

小优化：如果和较小的那个子集加上剩下所有的奶牛都没办法达到和较大的那个子集，则这种方案不管怎么继续往下选择，都不可能得到一个平衡的子集 $S$，因此剪枝

最坏时间复杂度：$O(3^n)=O(3^{20})$ 明显会超时
预计得分：$\leq30pts$（洛谷实测，得分 $19pts$）

---

优化思路：

原本直接一个递归暴力枚举所有情况，思路可行，也很容易想到，但是太容易超时。
那么，不妨把原数组一分为二，从当中切开分别处理前半段和后半段。这便是折半搜索。

这样子的话，时间复杂度直接砍成了 $O(2\times3^\frac{n}{2})=O(2\times3^{10})$，明显不会超时（除非你在分别递归完之后处理不当）

递归操作同上，只是到了最后一层的时候对数据的处理需要做修改。

因为现在一分为二，你在对前半部分递归的时候无法知晓后半部分的数据处理完之后到底怎样。因此，你需要对前半部分的选择进行记录并保存在合适的容器里。

我这边采用状态压缩的方式存储每一次选择的结果，因为这边状态只有选($0$)和不选($1$)两种操作，这样我就不需要再用数组来保存每个位置的选择，而且方便保存每次的状态。
然后我是考虑利用一个哈希表unordered_map，就叫它 $d$ 吧，毕竟是difference单词的首字母，$d[x]$ 表示所有 $R-L=x$ 的状态，主要是为了记录下所有差值为 $R-L$ 的选择方案，以便于后续答案统计。

（当然，如果你有更好的方案，完全可以不按照我这种方法写）

把前半部分保存下来就简单很多了，后半部分的递归思路同上，只是注意要从一半的位置（而非数组的开头）开始。

后半部分到了最后一层之后，便需要从当前状态开始查找并统计答案。

假设前半部分放入 $L$ 子集的和为 $L_1$，放入 $R$ 子集的和为 $R_1$，后半部分放入 $L$ 子集的和为 $L_2$，放入 $R$ 子集的和为 $R_2$，
为了保证 $L=R$，即 $L_1+L_2=R_1+R_2$，调整得 $R_1-L_1=L_2-R_2$。

由于在前面的哈希表中是按照 $R_1-L_1$ 存储的所有选择方案，那么在后半部分的递归到最后一层时，只需要访问 $d[L-R]$ （或者说 $d[L_2-R_2]$）就能够查找到所有和当前选择能够组合出平衡子集 $S$ 的方案。

不过，有一个细节需要注意：你不能直接ans+=d[L-R].size()，因为可能会有重复的情况。还需要开一个标记数组vis，vis[state]=1说明 $state$ 这个选择的状态已经有了，不能重复计数。

至于为什么会有重复计数，我举一个例子：

奶牛产量为 $\{1,3,2,4\}$，前半部分我把 $1$ 放入 $L$，把 $3$ 放入 $R$，后半部分我把 $2$ 放入 $R$，把 $4$ 放入 $L$，则 $S=\{1,3,2,4\}$
但我如果前半部分把 $1$ 放入 $R$，把 $3$ 放入 $L$，后半部分我把 $2$ 放入 $L$，把 $4$ 放入 $R$，则 $S=\{1,3,2,4\}$ 和上面一样，

但在程序中它们被分别放在 $d[3-1]$ 和 $d[1-3]$ 中，如果直接ans+=d[L-R].size()会让同一个 $S$ 被统计两遍，与题意不合。

最终版本の代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int n,a[25],ans;
bool vis[1050000];
unordered_map<int,vector<int>>d; //用unordered_map，避免map额外的O(log)排序时间
void dfs1(int dep=1,int end=n>>1,int L=0,int R=0,int state=0){ //前半段递归，state状压
    if(dep>end){
        d[R-L].pb(state); //哈希表+向量存储当前状态
        return;
    }
    dfs1(dep+1,end,L+a[dep],R,state|1<<dep-1); //加入L,状压
    dfs1(dep+1,end,L,R+a[dep],state|1<<dep-1); //加入R,状压
    dfs1(dep+1,end,L,R,state); //什么都不加（状态不变）
}
void dfs2(int dep=(n>>1)+1,int end=n,int L=0,int R=0,int state=0){ //后半段递归，state状压
    if(dep>end){
        if(d.count(L-R)) //判断是否有符合要求的状态
            for(const auto&st:d[L-R]) //遍历所有符合要求的状态
                if(!vis[st|state]) //要求：两部分状态合并后并未被统计过
                    ans++,vis[st|state]=1; //统计答案并标记
        return;
    }
    dfs2(dep+1,end,L+a[dep],R,state|1<<dep-1);
    dfs2(dep+1,end,L,R+a[dep],state|1<<dep-1);
    dfs2(dep+1,end,L,R,state);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs1();
    dfs2();
    cout<<ans-1;
    return 0;
}

时间复杂度：约 $O(3^\frac{n}{2})=O(3^{10})$
预计得分：$100pts$
ACGO&洛谷实测：均可AC

解锁成就：时空双修（截止到作者提交的时刻，作者的代码时间和空间均超过了 $100\%$ 的用户）

---

附：
状压：利用二进制，将 $01$ 状态压缩为一个二进制下的整数。
操作：二进制下，从右往左第 $i$ 位为 $1$ 表示数组第 $i$ 个元素被选择，反之则是不被选择。
优势：可以直接使用位运算来操作，消耗时间少，且能够作为数组和其他 $\tt{STL}$ 容器的下标和值。

标记数组 vis 具体大小：$2^{20}=1048576$，覆盖了 $0$ 到 $2^{20}-1$ 所有状态。
示例代码中开的大小为vis[1050000]完全足够。