题解 P3067 【[USACO12OPEN]平衡的奶牛群Balanced Cow S…】
顾z
2018-10-21 20:40:17
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
> ### Description
>
> 给n个数,从中任意选出一些数,使这些数能分成和相等的两组。
>
> 求有多少种选数的方案。
>
> ### Input
>
> 第$1$行:一个整数$N$
>
> 第$2$到$N+1$行,包含一个整数$m_i$
>
> ### Output
>
> 一行:平衡的集合的个数.
看到题的一瞬间数据范围?
$N \leq 20$?状压!
明显直接做过不去,选择**折半搜索**.
折半搜索的话会有三种情况
- 一.选择当前位置
- 二.选择当前位置,给第一组.
- 三.选择当前位置,给第二组.
然后直接跑折半搜索+状压即可.
存储类似链式前向星,应该不是很难理解,就不过多解释了.
然后就枚举状态即可,可是直接枚举到$2^n-1$显然会$T$掉.
由于我们后半截的状态已知,所以说,我们只需要枚举前一半的状态即可.
注意要$sort$找到两边值相等的.
其他的就不太难理解了,如果不能理解的话可以私信我 qwq.
``代码``
```c++
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 10000008
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,w[28],mid,head[N];
struct cod{int u,val;}e[200008],edge[N];
int v[N],ans,tot,ttt,sta,cnt;
bool vis[2500000];
void dfs1(int dep,int sum,int state)
{
if(dep>mid)
{
edge[++tot].u=head[state];
edge[tot].val=sum;
head[state]=tot;
return;
}
dfs1(dep+1,sum,state);
dfs1(dep+1,sum+w[dep],state|(1<<(dep-1)));
dfs1(dep+1,sum-w[dep],state|(1<<(dep-1)));
}
void dfs2(int dep,int sum,int state)
{
if(dep>n)
{
e[++ttt].u=state;
e[ttt].val=sum;
return;
}
dfs2(dep+1,sum,state);
dfs2(dep+1,sum+w[dep],state | (1<<(dep-1)));
dfs2(dep+1,sum-w[dep],state | (1<<(dep-1)));
}
inline bool ccp(const cod&a,const cod&b)
{
return a.val<b.val;
}
int main()
{
in(n);mid=(n+1)>>1;sta=(1<<n)-1;
for(R int i=1;i<=n;i++)in(w[i]);
dfs1(1,0,0);dfs2(mid+1,0,0);
sort(e+1,e+ttt+1,ccp);
for(R int i=0;i<=(1<<mid);i++)
{
R int cnt=0;
for(R int j=head[i];j;j=edge[j].u)
v[++cnt]=edge[j].val;
sort(v+1,v+cnt+1);
R int pos=1;
if(v[1]>e[ttt].val)break;
for(R int j=1;j<=ttt;j++)
{
while(pos<=cnt and v[pos]<e[j].val)pos++;
if(pos>cnt)break;
if(v[pos]==e[j].val)
vis[i|e[j].u]=true;
}
}
for(R int i=1;i<=sta;i++)
if(vis[i])ans++;
printf("%d",ans);
}
```