折半搜索 [meet in the middle]

Learning

在使用搜索的时候，当n过大2ⁿ会超时，这时候可以用折半搜索，把时间复杂度降低到2^n/2+1

具体方法：分别搜索前一半，把状态放入a数组，搜索后一半，把状态放入b数组，最后统计答案。
一般meet in the middle的难点主要在于最后答案的组合统计。
我们可以现将a或b数组sort，让其有序。然后通过枚举另一个数组中的状态，来实现统计答案。

---

Practice

[洛谷 4799] 世界冰球锦标赛

题目链接

题意：给定n(<=40)场比赛门票各自的价格，和Bobek拥有的钱数，求观赛方案总数。
（如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。可以一场也不看）

思路：2⁴⁰的搜索肯定会超时，所以折半搜索。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1<<21;
ll m,ans,a[50],suma[MAXN],sumb[MAXN];
int n,cnta,cntb;
void dfs(int t,int M,ll f[],ll s,int &cnt){
	if(t==M+1){
		f[++cnt]=s;
		return;
	}
	dfs(t+1,M,f,s,cnt);
	dfs(t+1,M,f,s+a[t],cnt);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int k=(1+n)/2,d;
	dfs(1,k,suma,0,cnta);//搜索前一半
	dfs(k+1,n,sumb,0,cntb);//搜索后一半
	sort(sumb+1,sumb+1+cntb);//合并
	for(int i=1;i<=cnta;i++){
		d=upper_bound(sumb+1,sumb+1+cntb,m-suma[i])-sumb-1;
		ans+=d;
	}
	cout<<ans;
}

[洛谷 3067] Balanced Cow Subsets

题目链接

题意：给n(<=20)个数，从中任意选出一些数，使这些数能分成和相等的两组。求有多少种选数的方案。

思路：这道题有三种状态：①不放入任何集合 ②放入左边集合 ③放入右边集合
[面向题解设计程序。。一知半解]

#include<cstdio>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
int n,mid;
struct node{
	int v,f;
}suma[1<<22],sumb[1<<22];
int cnta,cntb,m[44],r;
bool vis[1<<23];
ll ans;
void dfs(int l,int flag,int sum,int t){
	if(l>r){
		if(t){
			suma[++cnta].v=sum;
			suma[cnta].f=flag;
		}else{
			sumb[++cntb].v=sum;
			sumb[cntb].f=flag;
		}
		return;
	}
	dfs(l+1,flag,sum,t);
	dfs(l+1,flag+(1<<(l-1)),sum+m[l],t);
	dfs(l+1,flag+(1<<(l-1)),sum-m[l],t);
}
inline bool cmp1(node x,node y){return x.v<y.v;}
inline bool cmp2(node x,node y){return x.v>y.v;}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&m[i]);
	mid=(1+n)/2;
	r=mid;dfs(1,0,0,1);//折半搜索 
	r=n;dfs(mid+1,0,0,0);
	
	sort(suma+1,suma+1+cnta,cmp1);//排序 
	sort(sumb+1,sumb+1+cntb,cmp2);
	
	int l=1,r=1;
	while(l<=cnta&&r<=cntb){//双指针
		while(-suma[l].v<sumb[r].v&&r<=cntb)r++;
		int p=r;
		while(r<=cntb&&-suma[l].v==sumb[r].v){
			if(!vis[suma[l].f|sumb[r].f]){
				vis[suma[l].f|sumb[r].f]=1;
				ans++;
			}
			r++;
		}
		if(l<cnta&&suma[l].v==suma[l+1].v)r=p;
		l++;
	}
	cout<<ans-1;
}