[网络协议]P3067 [USACO12OPEN]Balanced Cow Subsets G 折半搜索

传送门

目录

题意：

给你$n$个数，从中任意选出一组数，使这些数能分成和相等的两组，问有多少种选数方案。

$2\le n\le 20,1\le a_i\le 1e9$

思路：

注意审题，是选出一组能分成两组和相等的即可，也就是说如果是同一组但是分成两个部分的时候有多种方案，那么也算一种。

看到$n$很小，不难想到爆搜，但是每个数有三种情况，复杂度$3^n$，但是我们可以使用$meetinmiddle$先搜一半，让后对于另一半直接使用其搜出来的信息，由于对于每一个选出来数相同的方案都视为一个方案，所以对于每个状态我们需要记一个state代表当前选了哪几个，让后去重即可。

考虑如何计算方案？假设当前两边差值的绝对值是$x$，那么需要另一半两边插值绝对值也为$x$，是否只需要加入另一半插值也为$x$的方案即可？答案是否定的，还需要判断当前这一半状态与另一半状态拼起来是否已经计算过，所以需要存下来遍历，这样复杂度有点高，但是吸氧能过。。

#include<bits/stdc++.h>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define Mid (tr[u].l+tr[u].r>>1)
#define pb push_back
using namespace std;

const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7;
typedef long long LL;
typedef pair<LL,LL> PII;

int n;
int a[N];
map<LL,vector<int>>mp;
map<pair<LL,LL>,int>st,vis;

void dfs(int u,LL l,LL r,LL state) {
    if(u>=n/2) {
        LL now=abs(r-l);
        if(st.count({state,now})) return;
        st[{state,now}]=1;
        mp[now].pb(state);
        //cout<<now<<"**"<<l<<' '<<r<<endl;
        return;
    }
    dfs(u+1,l,r,state);
    dfs(u+1,l+a[u],r,state+(1<<u));
    dfs(u+1,l,r+a[u],state+(1<<u));
}

LL ans=0;
void solve(int u,LL l,LL r,LL state) {
    if(u==n) {
        LL now=abs(l-r);
        if(st.count({state,now})) return;
        st[{state,now}]=1;
        //ans+=mp[now];
        for(auto x:mp[now]) {
            if(vis.count({x,state})) continue;
            vis[{x,state}]=1;
            ans++;
        }
        return;
    }
    solve(u+1,l,r,state);
    solve(u+1,l+a[u],r,state+(1<<u));
    solve(u+1,l,r+a[u],state+(1<<u));
}

void solve() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    if(n==1) {
        puts("0");
        return;
    }
    dfs(0,0,0,0);
    st.clear(); vis[{0,0}]=1;
    //for(auto x:mp) cout<<x.X<<' '<<x.Y<<endl;
    solve(n/2,0,0,0);
    printf("%lld\n",(ans));
}

int main() {
	int _=1;
	while(_--) {
		solve();
	}

    return 0;
}