题解 P3067 【[USACO12OPEN]平衡的奶牛群Balanced Cow S…】

顾z

2018-10-21 20:40:17

Solution

# [顾](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); } ```