当前位置：首页 > news >正文

Meet in the middle 学习笔记

news 2025/10/25 21:40:16

由于蒟蒻在模拟赛写 DFS 挂掉了，所以来学 Meet in the middle 。

「引入」

Meet in the middle 算法没有正式译名，常见的翻译为「折半搜索」、「双向搜索」或「中途相遇」，以下称折半搜索。

它适用于输入数据较小，但还没小到能直接使用暴力搜索的情况。

在普通 DFS 还在为难以通过 \(n\le 20\) 的数据点而抓耳挠腮时，我们折半搜索已经秒切 \(n\le 40\) 的数据点了。这么棒的算法你确定不学学吗？

「算法介绍」

折半搜索本质上是 DFS 的一种优化，它将搜索过程分成两半，分别计算后再将其结合，时间复杂度大大减少，将朴素 DFS 的 \(O(a^b)\) 优化到了 \(O(a^{b/2})\) 。

这么讲可能有点抽象，让我们结合一道例题来深度讲解。

「例题」

洛谷 P4799 [CEOI 2015] 世界冰球锦标赛 (Day2)

给定 \(N\) 场比赛的票价和预算 \(M\)，计算总票价不超过 \(M\) 的观赛方案数（不看任何比赛也算一种方案，选与不选某场比赛视为不同方案），其中 \(1 \le N \le 40，1 \le M \le 10^{18}\)，票价不超过 \(10^{16}\)。

先考虑朴素 DFS ，枚举每个比赛选或不选，时间复杂度 \(O(2^N)\) ，期望得分 \(40\ pts\) 。

\(Code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[50],ans;
void dfs(int now,int sum){if(sum>m) return;if(now>n){ans++;return;}dfs(now+1,sum+a[now]);dfs(now+1,sum);
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];dfs(1,0);cout<<ans;return 0;
}

提交记录

尝试在朴素 DFS 的基础上进行优化，首先，我们将门票价格均分成两半并分别进行搜索，并将搜索到的结果计入两个数组中。

vector<int> lf,rf; // 记录两次搜索的结果
void dfs1(int l,int r,int sum){if(sum>m) return;if(l>r){ // 与朴素 DFS 不同的点在于此处将 sum 计入搜索结果lf.push_back(sum);return;}dfs1(l+1,r,sum+a[l]);dfs1(l+1,r,sum);
}
void dfs2(int l,int r,int sum){if(sum>m) return;if(l>r){rf.push_back(sum);return;}dfs2(l+1,r,sum+a[l]);dfs2(l+1,r,sum);
}

接下来，我们将答案进行合并，对于答案数组 \(lf\) ，我们将其按从小到大的顺序排序，随后枚举答案数组 \(rf\) ，每次二分找到第一个符合条件（设找到的 \(lf\) 为 \(x\) ，当前枚举到了 \(rf\) 的第 \(i\) 个数，则符合条件的 \(x\) 需满足 \(lf_x+rf_i\le m\)）的 \(x\) ，不难想到所有下标 \(\le x\) 的答案也合法，所以将答案累加 \(x\) 。

sort(lf.begin(),lf.end());for(int i:rf){int rem=m-i;if(rem<0) continue;ans+=upper_bound(lf.begin(),lf.end(),rem)-lf.begin();}

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[50],ans;
vector<int> lf,rf;
void dfs1(int l,int r,int sum){if(sum>m) return;if(l>r){lf.push_back(sum);return;}dfs1(l+1,r,sum+a[l]);dfs1(l+1,r,sum);
}
void dfs2(int l,int r,int sum){if(sum>m) return;if(l>r){rf.push_back(sum);return;}dfs2(l+1,r,sum+a[l]);dfs2(l+1,r,sum);
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int mid=(1+n)/2;dfs1(1,mid,0);dfs2(mid+1,n,0);sort(lf.begin(),lf.end());for(int i:rf){int rem=m-i;if(rem<0) continue;ans+=upper_bound(lf.begin(),lf.end(),rem)-lf.begin();}cout<<ans;return 0;
}

期望得分 \(100\ pts\) 。