「筆記」折半搜索（Meet in the Middle）
## 思想
先搜索前一半的狀態(tài)，再搜索后一半的狀態(tài)，再記錄兩邊狀態(tài)相結(jié)合的答案。
暴力搜索的時(shí)間復(fù)雜度通常是 $O(2^{n})$ 級(jí)別的。但折半搜索可以將時(shí)間復(fù)雜度降到 $O(2 \times 2^{\frac{n}{2}})$，再加上統(tǒng)計(jì)答案的時(shí)間復(fù)雜度，總復(fù)雜度幾乎縮小了一半。
## 例題
### 「CEOI2015 Day2」世界冰球錦標(biāo)賽
#### 題目鏈接
[Luogu P4799 \[CEOI2015 Day2\]世界冰球錦標(biāo)賽](https://www.luogu.com.cn/problem/P4799)
#### 分析
用折半搜索的思想，先搜索 $0 \sim \lfloor \frac{n}{2} \rfloor$ 的比賽，再搜索 $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ 的比賽。每個(gè)比賽有看與不看兩種狀態(tài)，時(shí)間復(fù)雜度 $O(2 \times 2^{\frac{n}{2}})$。在搜索后半部分的時(shí)候，假設(shè)該狀態(tài)的花費(fèi)是 $s$，則去前半部分的答案中找到所有花費(fèi)小于等于 $m - s$ 的結(jié)果，統(tǒng)計(jì)答案。
前半部分搜索的時(shí)候記錄所有的答案，然后排序，這樣后半部分統(tǒng)計(jì)答案的時(shí)候可以二分。
總的時(shí)間復(fù)雜度為 $O(2^{\frac{n}{2}} + 2^{\frac{n}{2}} \cdot \log(2^{\frac{n}{2}}))$，可通過(guò)本題。
注意 `vector` 的常數(shù)問(wèn)題：本題如果采用兩個(gè) `vector` 數(shù)組，分別記錄兩邊的答案，最后再統(tǒng)計(jì)，則會(huì)在 $#45$ 測(cè)試點(diǎn) <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>（開(kāi) $\text{O2}$ 可過(guò)）。
#### 參考代碼
```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; // 存儲(chǔ)所有前部部分可以得到的狀態(tài)的花費(fèi)（可重）
long long ans;
void dfs1(int p, long long s){ // p -> 當(dāng)前位置，s -> 當(dāng)前花費(fèi)，下同
????if(p >= (n/2)){
????????v1.push_back(s); // 記錄前半部分狀態(tài)
????????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(); // 統(tǒng)計(jì)前半部分花費(fèi)小于 (m-s) 的狀態(tài)數(shù)量
????????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$ 的數(shù)，再搜索 $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ 的數(shù)。
每個(gè)數(shù)有「放第一組」「放第二組」「不選」共三種狀態(tài)，可以在搜索的時(shí)候把「放第一組」記為 $+$，把「放第二組」記為 $-$，「不選」就不加也不減，這樣兩組相等就是和為 $0$。
在搜索后半部分的時(shí)候，記錄答案，假設(shè)該狀態(tài)的和是 $s$，則去前半部分的答案中找到所有等于 $-s$ 的結(jié)果。
直接這樣交會(huì) <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>。仔細(xì)看題，要求的是找出一些數(shù)，使得它們能被分為兩組。比如有四個(gè)數(shù) $a, b, c, d$，滿足 $a + b = c + d$，$c + d = a + b$，$a + c = b + d$，$b + d = a + c$ 之類，就會(huì)被重復(fù)記錄。還有諸如此類的多個(gè)數(shù)的重復(fù)情況。所以要記錄選數(shù)的情況（有些類似 hash 的思想），比如有 $a, b, c, d$ 四個(gè)數(shù)，選了 $a, c$ 兩個(gè)，就用二進(jìn)制數(shù) $1010$ 記錄（$1$ 表示選，$0$ 表示不選）。再左移 $10$ 位（$n \leq 20$，前半部分最多 $10$ 個(gè)數(shù)），并連接上后半部分的選數(shù)情況，就得到了形如 $1010000000xxxx$ 的二進(jìn)制數(shù)，開(kāi) bool 數(shù)組去重即可。
這樣時(shí)間復(fù)雜度為 $O(3^{\frac{n}{2}} + 3^{\frac{n}{2}} \cdot \log(3^{\frac{n}{2}}))$，實(shí)際遠(yuǎn)遠(yuǎn)跑不滿，在開(kāi) $\text{O2}$ 的情況下最慢的測(cè)試數(shù)據(jù)也才 $131ms$。
代碼中 `v1[x]` 是 `vector` 類型的，該數(shù)組表示所有前半部分答案為 $x$ 的選數(shù)情況記錄。
還是注意考慮 `vector` 的常數(shù)問(wèn)題，必要時(shí)善用 $\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 -> 當(dāng)前位置，s -> 當(dāng)前和，tp -> 選數(shù)記錄（用于去重），下同
????if(p >= (n/2)){
????????v1[s].push_back(tp); // 記錄選數(shù)的情況
????????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]){ // 枚舉前半部分所有結(jié)果為 -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;
}
```
