姓名： 王梓涵
赛道： 提高组
类型： 算法技能
折半搜索/中途相遇法
关键词： 中途相遇法、meet in the middle、折半搜索
折半搜索(meet in the middle)，也叫中途相遇法，就是可以将搜索折半的一种方法，比如一个要计算一个搜索次数为 2^{40} 的题目，爆搜必定超时，而我们可以用类似分治的方法，把它分成一半然后计算 l, mid 和 mid + 1, r 的答案，将他们按照一定的性质结合起来。
模板题：
给定 n 和一个长度为 n 的数组，有多少种方法选择一个该数组的子集使得和为 x 。
这道题目非常板，就是分成两半，一半 [l,mid] ，一半 [mid + 1, r] ，每次加和完后，用 map 进行记录，最后看看存不存在计数即可。
代码实现：
int mid = n / 2;//折半操作
for(int i = 0;i < (1 << mid);i ++)//枚举前一半的数
{
int s = 0;
for(int j = 0;j < mid;j ++)
{
if(1 & (i >> j))//用枚举子集的方法，去统计不同的和
{
s += a[j];
}
}
mp[x - s] ++;//存入 map 中以在后面统计能和目前这一半的和相加产生贡献的子集的个数
}
for(int i = 0;i < (1 << (n - mid));i ++)//枚举后一半数
{
int s = 0;
for(int j = 0;j < n - mid;j ++)
{
if(1 & (i >> j))//枚举子集，统计加和
{
s += a[j + mid];
}
}
if(mp.find(s) != mp.end())//看看是否有能与之前合并的子集
{
res += mp[s];//统计答案
}
}
练习题讲解：
一下题目可能含有原创题，会给网址，有兴趣可以做一做。
下面五道题目的题单，戳这里，欢迎做我们自出的一道简单题。
给定 N 个数字，跟一个限制 M ，问有多少种不同的取数方法，使得取数的和不超过 M 。
1 \le N \le 40 ， 1 \le M \le 10^{18} 。
首先是朴素的方法，就是暴力搜索，显然时间复杂度为 2 ^ {n} 次方，显然过不了，这时候可以利用分治的思想，欸，这道题目可以进行折半操作，将时间复杂度降为了 O(2 ^ {\frac n 2} + 2 ^ {\frac n 2}) ，你会发现如果存在一种这样的解法，那么就可以通过这道题目，你还会发现，这道题目中的 40 就是希望你用这般搜索完成这道题，因为如果 n 再大一些肯定就过不了了。
现在我们来想一想正解，我们可以把整个序列分为两段，第一段为 [1, \left \lfloor \frac n 2 \right \rfloor] ，第二段为 [\left \lfloor \frac n 2 \right \rfloor + 1, n] ，我们分别将两次搜索出来的价格存入到两个 vector 中，再接着通过枚举第一个 vector 中的方案，来枚举将两边答案结合是否能够产生贡献，也许这就是这道题目中用 vector 存方案的最主要原因了，而如何查找出能够统计贡献的方案呢，可以通过二分来完成，为了方便，可以使用函数 upper_bound 来快速完成，总时间复杂度为 O(2 ^ {\frac n 2} \log(2^{\frac n 2}))=O(n2^{\frac n 2}) ，瓶颈在于排序。
给一个大小为 n 的集合，问有多少个该集合的子集，满足它可被分成两部分，且这两部分的和相等， n\le 20 。
一个最简单的思路，就是暴力，每个数要么不选，要么选进第一个集合，要么选进第二个集合。枚举每个数的状态然后检验答案。这样做的时间复杂度，是 O(3^n) 的。显然超时 （ 3^{10}=59049 ）
考虑优化这个过程，我们都知道折半搜索通常能把时间从 O(x^n) 降到 O(nx^{\frac n 2}) 。那么我们有一个初步的思路，就是先只搜索前 \left\lfloor\frac{n}{2} \right\rfloor 个元素构成的子集情形。也是枚举要么进第一个集合要么进第二个集合要么谁都不选。然后考虑搜索后面剩下的元素构成的子集情形。
我们想这样一件事情：我们设第一次搜到的某两个子集和分别为 a,b ，第二次搜到的某两个集合和为 c,d ，则我们想让 a+c=b+d 。我们不妨换一个角度考虑这个问题，我们也可以让 a+d=b+c ，这样就是一种合法的方案。考虑移项， a-b=c-d 。于是我们发现，只要两种选择的差相等时，就可以合并。
于是我们搜索时只需记录选择的差，状态只需记录要么选要么不选。每次要么 +a_x ，要么 -a_x ，要么不选，所以我们第一次搜索完成时，把当前状态推到 diff 的 vector 数组里面。这样是因为，之后的一次搜索再搜出 diff 时，可以直接从这个 vector 不重不漏的找出所有可以和当前状态合并的状态。（事实上可以发现， -diff 也可以和 diff 合并，但这样会有重复，因为我们在选取时，显然也会再出现结果为 -diff 的情况）。对于数组下标，由于 a-b 可能小于 0 ，或者过大，所以我们要借助 map 离散化下标。在之后只要在 map 中查找 $diff$，就遍历 vec_{mp_{diff}} 标记 st|St 为可行解（因为一种选择方案可能有多种划分方式，这样做可避免重复）。最终 O(2^n) 遍历哪些是可行解即可。
时间复杂度 O(n3^{\frac n 2}\log{3^{\frac n 2}}+2^n)=O(n^23^{\frac n 2}+2^n) ，可以通过。
给一个长 n 序列，要求你选若干元素，最大化模 m 的值， n\le35 。
朴素做法：枚举每个数选或不选，直接算出最终答案，这样是 O(2^n) 的，显然不行。
考虑优化：我们考虑这样一件事情：将整个序列分成两半，我们对于这两个序列，按照上面的朴素做法，得到模 m 的序列 a, b 。
将 a,b 排序。由于 a, b 中每个数都不大于 m ，所以我们有一个贪心的想法，答案一定是在某个位置 i ，在 b 序列中最大的小于等于 m - 1 - a_i 的数 + a_i 。因为不这样选，假设选一个后面的 b_j ，但是会发现 a_i + b_j \ge m 了，这导致结果变为 a_i + b_j - m ，显然不优。除非不存在这样的 b_j ，这时候，要取 b 中最大的数。
已知一个 n 元高次方程：
\sum\limits_{i=1}^n k_ix_i^{p_i} = 0
其中： x_1, x_2, \dots ,x_n 是未知数， k_1,k_2, \dots ,k_n 是系数， p_1,p_2,…p_n 是指数。且方程中的所有数均为整数。
假设未知数 x_i \in [1,m] \space ( i \in [1,n]) ，求这个方程的整数解的个数。
对于 100\% 的数据， 1\le n \le 6 ， 1\le m \le 150 ，且
\sum\limits_{i=1}^n |k_im^{p_i}| < 2^{31}
答案不超过 2^{31}-1 ， p_i \in \mathbb N^* 。
折半时只需枚举 x 的值即可。复杂度 O(300\times150^3) ，由于时限是 6s ，可以通过，由于题目过于简单，就就不多讲了。
小 W 在走格子。
这是一张 n 行 m 列的网格。可爱的小 W 发现这样一件事情：初始时数字 S=0 ，当他走偶数步（初始是 0 步）落在格子 (x,y) 上时，会使得 S\gets S+a_{x,y} ，如果是走奇数步到 (x,y) ，会使得 S\gets S-a_{x,y} 。问，从 (1,1) 走到 (n,m) ，有多少种方案，使得最后 S=w ？ n,m\le 20 。
可以发现如果暴力走，时间是 O(2^{n+m}) 的，会超时。（发现要跑一天）
我们把走步这件事拆成两部分：从 (1,1) 走到 x+y=\left\lfloor\frac {n+m+2}2\right\rfloor 的部分，和从 (n,m) 走到 x+y=\left\lfloor\frac {n+m+2}2\right\rfloor 的部分，将两个信息合并即可得答案。第一遍只需记录走到每个 x+y=\left\lfloor\frac {n+m+2}2\right\rfloor 的点，有多少种加和，他们的方案数。第二遍再根据奇偶性，如果 n+m 是奇数那就累计 w+sum 的贡献，否则就是 w-sum 。
由于作者很菜，且折半搜索题目不是很多，所以只能讲这些简单题了，那么本篇笔记到这里就结束了，感谢观看。