题目

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

分析

如果暴力枚举每个人被分到哪个组或不分，O（2^20）显然会超时。

我们换一种思路，

每次只枚举一半，

将前后半部分分开枚举后半部分，枚举出每种的和以及有没有被选的状态。

枚举和相同的前后部分，如果这种状态没有被选过，就ans+1，然后将这种状态打个标记，这种状态就不再产生贡献。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const long long N=100000;

using namespace std;

struct ddx

{

	long long sum;

	int sta;

}a[N*6],b[N*6];

int re[N],n,ans,tot,tot1,bz[N*20],mi[N];

bool cmp(ddx x,ddx y)

{

	return x.sum<y.sum;

}

void dg(int x,long long y,int z)

{

	if(x>n/2)

	{

		a[++tot].sum=y;

		a[tot].sta=z;

		return;

	}

	dg(x+1,y,z);

	dg(x+1,y+re[x],z+mi[x-1]);

	dg(x+1,y-re[x],z+mi[x-1]);

}

void dg1(int x,long long y,int z)

{

	if(x>n)

	{

		b[++tot1].sum=y;

		b[tot1].sta=z;

		return;

	}

	dg1(x+1,y,z);

	dg1(x+1,y+re[x],z+mi[x-1]);

	dg1(x+1,y-re[x],z+mi[x-1]);

}

int main()

{

	scanf("%d",&n);

	mi[0]=1;

	for(int i=1;i<=n+1;i++) mi[i]=mi[i-1]*2;

	for(int i=1;i<=n;i++) scanf("%d",&re[i]);

	dg(1,0,0);

	dg1(n/2+1,0,0);

	sort(a+1,a+1+tot,cmp);

	sort(b+1,b+1+tot1,cmp);

	int i=1,j=1;

	for(;i<=tot && j<=tot1;)

	{

		if(a[i].sum<b[j].sum) i++;

		else

		if(a[i].sum>b[j].sum) j++;

		else

		{

		int k=i,l=j;

		for(;a[i].sum==a[k].sum;) k++;

		for(;b[j].sum==b[l].sum;) l++;

		for(int p=i;p<=k-1;p++)

			for(int q=j;q<=l-1;q++)

			{

				if(!bz[a[p].sta+b[q].sta])

				{

					ans++;

					bz[a[p].sta+b[q].sta]=true;

				}

			}

		i=k;

		j=l;

		}

	}

	cout<<ans-1;

}

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