「笔记」折半搜索（Meet in the Middle）
## 思想
先搜索前一半的状态，再搜索后一半的状态，再记录两边状态相结合的答案。
暴力搜索的时间复杂度通常是 $O(2^{n})$ 级别的。但折半搜索可以将时间复杂度降到 $O(2 \times 2^{\frac{n}{2}})$，再加上统计答案的时间复杂度，总复杂度几乎缩小了一半。
## 例题
### 「CEOI2015 Day2」世界冰球锦标赛
#### 题目链接
[Luogu P4799 \[CEOI2015 Day2\]世界冰球锦标赛](https://www.luogu.com.cn/problem/P4799)
#### 分析
用折半搜索的思想，先搜索 $0 \sim \lfloor \frac{n}{2} \rfloor$ 的比赛，再搜索 $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ 的比赛。每个比赛有看与不看两种状态，时间复杂度 $O(2 \times 2^{\frac{n}{2}})$。在搜索后半部分的时候，假设该状态的花费是 $s$，则去前半部分的答案中找到所有花费小于等于 $m - s$ 的结果，统计答案。
前半部分搜索的时候记录所有的答案，然后排序，这样后半部分统计答案的时候可以二分。
总的时间复杂度为 $O(2^{\frac{n}{2}} + 2^{\frac{n}{2}} \cdot \log(2^{\frac{n}{2}}))$，可通过本题。
注意 `vector` 的常数问题：本题如果采用两个 `vector` 数组，分别记录两边的答案，最后再统计，则会在 $#45$ 测试点 <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Linhk1606/fontawesome-cdn@master/css/all.min.css"><span class="status time_limit_exceeded" style="color: sandybrown;"><i class="fad fa-fw fa-clock"></i> Time Limit Exceeded</span>（开 $\text{O2}$ 可过）。
#### 参考代码
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 50;
int n;
long long m, w[N];
vector <long long> v1; // 存储所有前部部分可以得到的状态的花费（可重）
long long ans;
void dfs1(int p, long long s){ // p -> 当前位置，s -> 当前花费，下同
if(p >= (n/2)){
v1.push_back(s); // 记录前半部分状态
return ;
}
dfs1(p+1, s);
if(s + w[p] <= m){
dfs1(p+1, s+w[p]);
}
}
void dfs2(int p, long long s){
if(p >= n){
ans += upper_bound(v1.begin(), v1.end(), m - s) - v1.begin(); // 统计前半部分花费小于 (m-s) 的状态数量
return ;
}
dfs2(p+1, s);
if(s + w[p] <= m){
dfs2(p+1, s+w[p]);
}
}
int main(){
scanf("%d%lld", &n, &m);
for(int i = 0; i < n; i++){
scanf("%lld", &w[i]);
}
dfs1(0, 0);
sort(v1.begin(), v1.end()); // 升序排序
dfs2((n/2), 0);
printf("%lld\n", ans);
return 0;
}
```
### 「USACO 12 OPEN」Balanced Cow Subsets G
#### 题目链接
[Luogu P3067 \[USACO12OPEN\]Balanced Cow Subsets G](https://www.luogu.com.cn/problem/P3067)
#### 分析
同样折半搜索，先搜索 $0 \sim \lfloor \frac{n}{2} \rfloor$ 的数，再搜索 $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ 的数。
每个数有「放第一组」「放第二组」「不选」共三种状态，可以在搜索的时候把「放第一组」记为 $+$，把「放第二组」记为 $-$，「不选」就不加也不减，这样两组相等就是和为 $0$。
在搜索后半部分的时候，记录答案，假设该状态的和是 $s$，则去前半部分的答案中找到所有等于 $-s$ 的结果。
直接这样交会 <span class="status wrong_answer" style="color: red;"><i class="fad fa-fw fa-times"></i>Wrong Answer <span style="color: #ffa900;">$38$</span></span>。仔细看题，要求的是找出一些数，使得它们能被分为两组。比如有四个数 $a, b, c, d$，满足 $a + b = c + d$，$c + d = a + b$，$a + c = b + d$，$b + d = a + c$ 之类，就会被重复记录。还有诸如此类的多个数的重复情况。所以要记录选数的情况（有些类似 hash 的思想），比如有 $a, b, c, d$ 四个数，选了 $a, c$ 两个，就用二进制数 $1010$ 记录（$1$ 表示选，$0$ 表示不选）。再左移 $10$ 位（$n \leq 20$，前半部分最多 $10$ 个数），并连接上后半部分的选数情况，就得到了形如 $1010000000xxxx$ 的二进制数，开 bool 数组去重即可。
这样时间复杂度为 $O(3^{\frac{n}{2}} + 3^{\frac{n}{2}} \cdot \log(3^{\frac{n}{2}}))$，实际远远跑不满，在开 $\text{O2}$ 的情况下最慢的测试数据也才 $131ms$。
代码中 `v1[x]` 是 `vector` 类型的，该数组表示所有前半部分答案为 $x$ 的选数情况记录。
还是注意考虑 `vector` 的常数问题，必要时善用 $\text{O2}$。
#### 参考代码
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N = 30, F = 1 << 21;
int n;
int a[N];
unordered_map <long long, vector <int> > v1;
long long ans;
bool vis[F];
void dfs1(int p, int s, int tp){ // p -> 当前位置，s -> 当前和，tp -> 选数记录（用于去重），下同
if(p >= (n/2)){
v1[s].push_back(tp); // 记录选数的情况
return ;
}
dfs1(p+1, s+a[p], (tp<<1)|1); // 放入第一组
dfs1(p+1, s-a[p], (tp<<1)|1); // 放入第二组
dfs1(p+1, s, (tp<<1)); // 不选
}
void dfs2(int p, int s, int tp){
if(p >= n){
for(int i : v1[-s]){ // 枚举前半部分所有结果为 -s 的
if(!vis[(i<<10)|tp]){ // 去重
vis[(i<<10)|tp] = 1;
ans++;
}
}
return ;
}
dfs2(p+1, s+a[p], (tp<<1)|1); // 放入第一组
dfs2(p+1, s-a[p], (tp<<1)|1); // 放入第二组
dfs2(p+1, s, (tp<<1)); // 不选
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
}
dfs1(0, 0, 0);
dfs2((n/2), 0, 0);
printf("%lld\n", ans-1); // 减去都不选的情况
return 0;
}
```
