折半搜索 笔记

介绍

折半搜索(meet in the middle)，指把一次搜索的过程分成两半，分别查找这两部分的结果，然后再进行合并

折半搜索能够大大地降低时间复杂度，典型的例子：如果一个搜索每次有两种选择，那么它正常的时间复杂度为$O(2^n)$，使用折半搜索后，时间复杂度降为$O(2^{\frac{n}{2}})$

具体怎样实现呢？请看例题

例题

1.世界冰球锦标赛

P4799 [CEOI2015 Day2] 世界冰球锦标赛

给定有 $n$ 个比赛，有一定财产，问在有限的消费内有几种看比赛的方案

每次都有选和不选两种选择，可以把整个搜索的过程分为前 $n/2$ 和后 $n/2$ 进行两次查找，第一次记录前半部分所有满足的情况，然后排序，在第二次搜索查找满足的情况并通过对刚刚记录下的所有情况二分求出总的情况

#include<bits/stdc++.h>
using namespace std;
long long n,a[45],m,ans,b[10000005],tb;
void fun1(int pos,long long sum){
	if(sum>m){
		return ;
	}
	if(pos>n/2){
		b[++tb]=sum;
		return ;
	}
	fun1(pos+1,sum);
	fun1(pos+1,sum+a[pos]);
}
void fun2(int pos,long long sum){
	if(sum>m){
		return ;
	}
	if(pos>n){
		int k=upper_bound(b+1,b+tb+1,m-sum)-b;
		ans+=k-1;
		return ;
	}
	fun2(pos+1,sum);
	fun2(pos+1,sum+a[pos]);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	fun1(1,0);
	sort(b+1,b+tb+1);
	fun2(n/2+1,0);
	printf("%lld",ans);
	return 0;
}

2.Xor-Paths

Codeforces 1006F Xor-Paths
给定一个网格，从左上角右下走，问有多少种方案满足所经过的元素的异或和等于给定的数

本题可以以对对角线为界进行折半搜索，即 $x+y==(n+m)/2+1$，在对角线上记录异或和，第二次搜索从右下向左上，到对角线结束，查找上次的记录中与本身异或和等于给定的数的情况，统计个数

#include<bits/stdc++.h>
using namespace std;
map<pair<pair<int,int>,long long>,long long>mp;
long long n,m,a[25][25],k,ans;
void fun1(int x,int y,long long xr){
	if(x>n||y>m){
		return ;
	}
	if(x+y==(n+m)/2+1){
		mp[make_pair(make_pair(x,y),xr)]++;
		return ;
	}
	
	fun1(x+1,y,xr^a[x+1][y]);
	fun1(x,y+1,xr^a[x][y+1]);
}
void fun2(int x,int y,long long xr){
	if(x<1||y<1){
		return ;
	}
	if(x+y==(n+m)/2+1){
		xr^=a[x][y];
		ans+=mp[make_pair(make_pair(x,y),k^xr)];
		return ;
	}
	fun2(x-1,y,xr^a[x-1][y]);
	fun2(x,y-1,xr^a[x][y-1]);
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	fun1(1,1,a[1][1]);
	fun2(n,m,a[n][m]);
	printf("%lld",ans);
	return 0;
}