题目描述

夏令营有N个人，每个人的力气为M(i)。请大家从这N个人中选出若干人，如果这些人可以分成两组且两组力气之和完全相等，则称为一个合法的选法，问有多少种合法的选法？

数据范围

40%的数据满足：1<=M(i)<=1000；

对于100%的数据满足：2<=N<=20,1<=M(i)<=100000000

解法

40%

枚举每一位选或不选，设当前选的所有数的和为sum，然后使用背包求出当前每个可能的总和。

如果其中有sum/2，那么说明这种选法合法，使答案+1；

100%

比较显然的暴力是O(320)。

现在考虑使用折半搜索；

将原数集分为两个均匀的集合，

分别搜索出两个集合中所有可能的和，O(2∗310)；

由于一个集合中的负系数相当于把这项移项到另一个集合中。

所以直接找出两个集合中可能的和相等的数量即可。

运用二进制记录每个和选的方案，来防止重复计数。

---

实现：

将两组和排序，设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）

暂且不考虑其他玄学算法，考虑折半搜索：

直接的想法是O(2n)搜索，这显然超时；

但每个项的两个抉择互逆，也就是说每个项的抉择呈奇性。

将原数集分为两个均匀的集合。

分别使用O(2n/2)处理出两个集合的所有可能的和。

然后合并答案即可，使用二进制判重。

---

上述脑洞题算是与原问题的一个“外传”，也是应用折半搜索。

总结

大概折半搜索需要这个条件，将原数集分成两个均匀的集合后，项的抉择呈奇性。

至于奇性是什么上文已感性阐述，属博主自创词汇。

【JZOJ4841】【NOIP2016提高A组集训第4场11.1】平衡的子集的相关教程结束。