题目描述
夏令营有N个人，每个人的力气为M(i)。请大家从这N个人中选出若干人，如果这些人可以分成两组且两组力气之和完全相等，则称为一个合法的选法，问有多少种合法的选法？
数据范围
40%的数据满足：1<=M(i)<=1000；
对于100%的数据满足：2<=N<=20,1<=M(i)<=100000000
解法
40%
枚举每一位选或不选，设当前选的所有数的和为sum，然后使用背包求出当前每个可能的总和。
如果其中有sum/2，那么说明这种选法合法，使答案+1；
100%
比较显然的暴力是
现在考虑使用折半搜索；
将原数集分为两个均匀的集合，
分别搜索出两个集合中所有可能的和，
由于一个集合中的负系数相当于把这项移项到另一个集合中。
所以直接找出两个集合中可能的和相等的数量即可。
运用二进制记录每个和选的方案，来防止重复计数。
实现：
将两组和排序，设l为第一组的指针，r为第二组的指针；
通过此大彼进，使得a[l]==b[r]；
相同的和之间两两匹配来贡献答案，判重。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const char* fin="subset.in";
const char* fout="subset.out";
const int maxn=50,maxh=1048580;
const int er[21]={1,2,4,8,16,32,64,128,256,512,1024};
int n,nn,i,j,k;
int a[maxn],b[maxn];
bool bz[1025][1025];
int h[maxh];
int ans1;
int fi[maxh],ne[maxh],la[maxh],en[maxh];
int ans,tot,tot1;
int ans2;
void add_line(int a,int b,int c){
if (h[a]<0){
tot++;
fi[a]=en[a]=tot;
la[tot]=b;
h[a]=c;
}else{
ne[en[a]]=tot+1;
tot++;
en[a]=tot;
la[tot]=b;
}
}
int hash(int v){
int k=(v%maxh+maxh)%maxh;
while (h[k]!=ans1 && h[k]!=v) {
k=(k+1)%maxh;
}
return k;
}
void dfs(int v,int sum,int state){
int i,j,k;
if (v>nn){
k=hash(sum);
add_line(k,state,sum);
return ;
}
dfs(v+1,sum,state);
dfs(v+1,sum+a[v],state+er[v-1]);
dfs(v+1,sum-a[v],state+er[v-1]);
}
void getans(int v,int sum,int stat){
int i,j,k;
if (v>n){
k=hash(sum);
if (h[k]!=ans1){
if (fi[k]==ans1) return;
ans2++;
j=0;
for (i=fi[k];i;i=ne[i]){
j++;
if (!bz[stat][la[i]]){
ans++;
bz[stat][la[i]]=true;
}
}
//ans2=ans2+j;
}
return;
}
getans(v+1,sum,stat);
getans(v+1,sum+a[v],stat+er[v-1-nn]);
getans(v+1,sum-a[v],stat+er[v-nn-1]);
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d",&n);
nn=n/2;
memset(h,128,sizeof(h));
memset(fi,128,sizeof(fi));
ans1=h[0];
for (i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(1,0,0);
getans(nn+1,0,0);
ans--;
printf("%d",ans);
return 0;
}启发
折半搜索
本题
本题：每个数有不选，隶属A，隶属B，三种选择。
而对于在一个集合中，每个数的选择意义就是不选，隶属这个集合①，隶属另一个集合②。
①②选择在两个集合之间互逆。
姑且称这些元素的抉择是奇性的。
那么本体就可以使用折半搜索。
拓展
现在有这么一题，
夏令营有N个人，每个人的力气为M(i)。问有多少种分法将这N个人分成两组且两组力气之和完全相等？（n<=40,m(i)<=10000000）
暂且不考虑其他玄学算法，考虑折半搜索：
直接的想法是
但每个项的两个抉择互逆，也就是说每个项的抉择呈奇性。
将原数集分为两个均匀的集合。
分别使用
然后合并答案即可，使用二进制判重。
上述脑洞题算是与原问题的一个“外传”，也是应用折半搜索。
总结
大概折半搜索需要这个条件，将原数集分成两个均匀的集合后，项的抉择呈奇性。
至于奇性是什么上文已感性阐述，属博主自创词汇。