Meet int the middle--cj集训10.16模拟赛T1

本文主要是介绍Meet int the middle--cj集训10.16模拟赛T1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
有多少个非空子集，能划分成和相等的两份。
solution:
只想到了 $3^n$ 暴力
其实可以用 $meet\ int\ the\ middle$ 的思想降低复杂度
左边的那些 $3^{N/2}$ 枚举分别是不放还是放到第一组还是放到第二组，并记录下来。
右边的 $3^{N/2}$ 枚举后，再 $2^{N/2}$ 看看左边符合这个值的那些，就行了。
总复杂度 $O(6^{N/2})$ 。

其实其他的都能想到，但就是降低复杂度的方法以前没有用过
$meet\ in\ the\ middle$ 只做过裸题，其实很多时候都可以这样做

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#define maxn 25
using namespace std;
int n,a[maxn],ans,haf,tot;
bool can[(1<<20)+5];
map<int,int> mp;
set<int> s[60000];
set<int>::iterator it;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}inline void solve(int ss,int lfsm,int rgsm){if(!mp.count(rgsm-lfsm)) return;int cur=mp[rgsm-lfsm];for(it=s[cur].begin();it!=s[cur].end();it++)can[ss|(*it)]=true;return;
}void dfs(int now,int t,int cur,int lfsm,int rgsm){if(now==t){if(t==n) {solve(cur,lfsm,rgsm);return;}int cc=lfsm-rgsm;if(!mp.count(cc)) mp[cc]=++tot;s[mp[cc]].insert(cur);return; }dfs(now+1,t,cur,lfsm,rgsm);//不放dfs(now+1,t,cur|(1<<now),lfsm+a[now+1],rgsm);//放左边dfs(now+1,t,cur|(1<<now),lfsm,rgsm+a[now+1]);//放右边return; 
}int main(){freopen("subsets.in","r",stdin);freopen("subsets.out","w",stdout);n=rd();for(int i=1;i<=n;i++) a[i]=rd();haf=n/2;dfs(0,haf,0,0,0);dfs(haf,n,0,0,0);for(int i=1;i<(1<<n);i++)if(can[i]) ++ans;printf("%d\n",ans);return 0;
}