Meet in the middle

Meet in the middle 双端搜索

不是怎么这个人现在才会双端搜索

Meet in the middle，顾名思义，就是从两端进行搜索，然后把两端的答案合并得到最终答案。

如果原本的搜索时间复杂度为 \(O(a^b)\)，那么 Meet in the middle 可以将搜索的时间复杂度优化到 \(O(wa^{\frac{b}{2}})\)，其中 \(w\) 为一个常数。

思路很简单，直接实战。上链接。

P5691 [NOI2001] 方程的解数

给定 \(n\)，\(k_1,k_2,...,k_n\)，\(p_1,p_2,...,p_n\) 求

\[\sum \limits_{i=1}^n k_ix_i^{p_i}=0 \]

的正整数解个数，其中 \(x \in [1,m] \ (i \in [1,n])\)。

\(1 \le n \le 6\)，\(1 \le m \le 150\)。

看到这题一眼爆搜，但很明显时间复杂度是 \(O(m^n)\) 的过不了。

考虑 Meet in the middle，处理前半部分和后半部分再合并。

How 合并？

由于最终的和为 \(0\)，我们只需在处理后半部分时找前半部分选取的和为后半部分选取的和相反数的方案即可。

于是开一个 map 记录前半部分选取对应的和的方案数，后半部分搜索完后从 map 里查找并更新答案即可。

时间复杂度 \(O(wm^{\frac{n}{2}})\)，其中 \(w\) 是 map 的常数。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=10;
map<ll,int> mp;
int n,m;
ll k[N],p[N],ans;
ll qpow(ll a,ll b){//快速幂，搜索时累加和用的
	ll res=1,x=a;
	while(b){
		if(b&1)res*=x;
		x*=x;
		b>>=1;
	}
	return res;
}
void dfs1(int x,ll sum){//前半
	if(x>(n>>1)){
		mp[sum]++;//记录
		return;
	}
	for(int i=1;i<=m;i++)//枚举下一步的选值
		dfs1(x+1,sum+k[x]*qpow(i,p[x]));
}
void dfs2(int x,ll sum){//后半
	if(x>n){
		ans+=mp[-sum];//找相反数的方案数
		return;
	}
	for(int i=1;i<=m;i++)
		dfs2(x+1,sum+k[x]*qpow(i,p[x]));
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>k[i]>>p[i];
	dfs1(1,0);
	dfs2((n>>1)+1,0);
	cout<<ans;
	return 0;
} 

做完这道再来看下一道：

P2962 [USACO09NOV] Lights G

有一张 \(n\) 个点 \(m\) 条边的无向图，每次操作一个点使其权值异或 \(1\)，与其连边的节点也会异或 \(1\)，求最小的操作次数。

\(1 \le n \le 35\)，\(1 \le m \le 595\)。没有重边和自环。

dfs 需要记录三个信息：当前所在的节点，状态和次数。

Meet in the middle，由于直接枚举相邻节点并统计状态相当不方便且肯定超时，且 \(n\) 的范围很小，于是我们可以状态压缩每一个节点会影响的节点（包括自身）与 dfs 中节点的状态。

考虑前半部分与后半部分能合并的条件：当且仅当所有的点权值都为 \(1\)，即当 front^now==(1<<n)-1 时方案才合法。

于是还是用 map 来维护，但这一次统计的是到达当前状态时至少需要几步。后半部分合并时，根据异或的性质有 front=now^((1<<n)-1) ，即如果 map 统计了 now^((1<<n)-1) 那么就可以用于更新最优解。

只加了 inline 用于卡常但没吸氧，跑得飞快。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=40,M=600;
map<ll,int> mp;
int n,m;ll s[N];
//s[i] 按下i对其他点产生的影响 
int ans=0x3f3f3f3f;
inline void dfs1(int x,ll now,int t){
	if(x>(n>>1)){//统计步数
		if(!mp.count(now))mp[now]=t;
		else mp[now]=min(mp[now],t);
		return; 
	}
	dfs1(x+1,now,t);
	dfs1(x+1,now^s[x],t+1);
}
inline void dfs2(int x,ll now,int t){
	if(x>n){
		if(mp.count(((1ll<<n)-1)^now))//如果这种状态是可行的
			ans=min(ans,mp[((1ll<<n)-1)^now]+t);//更新答案
		return;
	}
	dfs2(x+1,now,t);
	dfs2(x+1,now^s[x],t+1);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		s[i]|=1<<i-1;//状压
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		s[u]|=1ll<<v-1;
		s[v]|=1ll<<u-1;
	}
	dfs1(1,0,0);
	dfs2((n>>1)+1,0,0);
	cout<<ans;
	return 0;
}

现在你已经学会了 Meet in the middle，快去做题看看实力吧。