折半搜索+Hash表+状态压缩 | [Usaco2012 Open]Balanced Cow Subsets | BZOJ 2679

折半搜索+Hash表+状态压缩 | [Usaco2012 Open]Balanced Cow Subsets | BZOJ 2679 | Luogu SP11469

题面：SP11469 SUBSET - Balanced Cow Subsets

题解：

对于任意一个数，它要么属于集合A，要么属于集合B，要么不选它。对应以上三种情况设置三个系数1、-1、0，于是将题目转化

为找出两个集合和为0，将这两个集合合并不重复的为一种答案。考虑折半搜索。搜出前一半和后一半，用哈希表和状态压缩记录

和去重，然后统计答案即可。

时间复杂度为O(6^(N/2))。

代码：

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn=25,MOD=230203,max_num=6e4;
 4 int N,M[maxn],num=0,ans=0,nx[max_num],hd[MOD+50];
 5 int Tmp[max_num],Sum[max_num],hf,ps;
 6 bool vis[1050][1050];
 7 inline void Insert(int tmp,int sum){
 8     ps=(sum%MOD+MOD)%MOD;
 9     for(int i=hd[ps];i;i=nx[i])
10         if(Tmp[i]==tmp && Sum[i]==sum) return;//
11     nx[++num]=hd[ps];
12     Tmp[num]=tmp;
13     Sum[num]=sum;
14     hd[ps]=num;
15     return;
16 }
17 inline int Find(int tmp,int sum){
18     ps=(sum%MOD+MOD)%MOD;
19     int ans=0;
20     for(int i=hd[ps];i;i=nx[i])
21         if(Sum[i]==sum && vis[Tmp[i]][tmp]==0){
22             vis[Tmp[i]][tmp]=1;
23             ans++;
24         }
25     return ans;
26 }
27 inline void Dfs1(int tp,int sum,int tmp){
28     if(tp>hf){
29         Insert(tmp,sum);
30         return;
31     }
32     Dfs1(tp+1,sum+M[tp],tmp<<1|1);
33     Dfs1(tp+1,sum-M[tp],tmp<<1|1);
34     Dfs1(tp+1,sum,tmp<<1);
35     return;
36 }
37 inline void Dfs2(int tp,int sum,int tmp){
38     if(tp>N){
39         ans+=Find(tmp,-sum);
40         return;
41     }
42     Dfs2(tp+1,sum+M[tp],tmp<<1|1);
43     Dfs2(tp+1,sum-M[tp],tmp<<1|1);
44     Dfs2(tp+1,sum,tmp<<1);
45     return;
46 }
47 int main(){
48     scanf("%d",&N);
49     hf=N>>1;
50     for(int i=1;i<=N;i++) scanf("%d",&M[i]);
51     Dfs1(1,0,0);
52     Dfs2(hf+1,0,0);
53     printf("%d
",ans-1);
54     return 0;
55 }

View Code

By:AlenaNuna