Meet \ in \ the \ Middle
复杂度: O(k^{\frac{n}{2}})
适用范围:
1 数据很小，但不是特别小
2 答案需要支持合并
eg1 : 求在 n 个数中选取若干个数使其和为 m 的方案数(n \le 40)
solve :
把所有的数分成两半
先枚举前 \frac{n}{2} 个数中所以选择方案，将可能的值存入哈希表
再枚举后 \frac{n}{2} 个数中所以选择方案，在哈希表中查询和为 m 的方案数
复杂度 O(2^{\frac{n}{2}})
eg2 : 求在 n 个数中选取若干个数使其和为总和的一半的方案数(n \le 23)
每个数可能有三种状态 ：
不选 || 选中并分入第一个组 ||选中并分入第二个组
两种方案不同当且仅当他们"不选"状态的数集合不相同
题意可转化为：
为每个数分配权重 {-1,0,1} 之一，使
\sum w_i \times a_i = 0
求可能的 w_i = 0 的集合个数
solve :
左边取 m 个数，暴力枚举复杂度 O(3^m) 对每个 wi = 0 的集合记录其和的方案数
右边剩余 (n - m) 个数，暴力枚举 $w_i$，再枚举与左边哪个集合拼在一起对于每种右边 wi = O 集合与左边某个集合拼在一起和为 0 则对答案产生 1 的贡献
复杂度O$(3^{n-m} \times 2^m)$
eg3 : [NOI2001]方程的解数
eg4 : 给定一张 n 个点 m 条边的图，点权为 0 \ 或 $1$，边权为两端点值的和问有多少种写方案使边权至少有一个 $0 \ $，至少有一个 $1 \ $，至少有一个 2 \ ($n \le 40$，时限 3.5s)
solve :
考虑容斥
设 f[...] 表示边权取值在 ... 集合内的方案数
那么 ans = f[0, 1, 2] - f[0, 1] - f[1. 2] - f[0, 2] + f[0] + f[1] + f[2]
f[0, 1, 2] :点权任取, 方案数 2^n
f[0] / f[2] : 孤点任取, 其他点 1 或 $2$， 方案数 2^{孤点个数}
f[1] : 每条边连接的一定是一个 0 和一个 1, 即每个连通块都是二分图时, 方案数$2^{连通块个数}$，否则为 0
f[0, 2] :每个连通块点权相同，方案数 2^{连通块个数}
f[1, 2] / f[0, 1]:
考虑 meet\ in\ the\ middle\
f[0, 1] :
如果一个点取值为 $0$，则它相邻的点不受限制如果一个点取值为 $1$，则它相邻的点必定为 0,
将所有点分成两部分, 枚举前一半的点权可能取值，并判断当前状态合法与否（即是否已经产生冲突)
f[1, 2] : 同理
two-pointer
i 对 j 对影响
j移动的方向
j移动的起终点
j移动的快慢
对撞指针
eg1. 求和
给定一个长度为 n 的序列 {a_n} 和 $k$，求序列中有多少对数相加等于 k (n \le 10^5，|ai|,|k| \le 10^9)
solve :
1 sort
2 对撞指针
即 i 从小到大搜， j 从大到小搜
eg2. Black Hills golden jewels
给出一个长度为 n 的数组，求集合 (ai+aj), i<j 里的第 k 大元素 (n \le 105，k \le \frac{n(n-1)}{2})
solve :
正难则反 ——> 二分答案
但暴力统计 O(n^2)
故考虑双指针，排序，枚举一个 i ，求一个最大的 $j$。随着 i 增大，$j$ 只会不变或减小。 O(n)
滑动窗口
特征： 吞食， 吃撑， 排泄（6
eg1. 给定长度为n的数列和正整数S，求和不小于S的子段的最短长度(n < 1 \times 10^5，1 \le 数列元素,S \le 1 \times 10^9)
eg2. 给定一棵 n 个点的树，点有点权，点权互不相同。给定$q$ 组询问，每组询问给出 $x$，求 x 节点子树内是否存在三个点的点权可以构成三角形( n,q \le 4 \times 10^4，1 \le 点权 \le 10^7)
eg3. 给定一个长度为 n 的序列 {a_n} ，求最长的不包含重复数字的连续子段长度(n \le 1 \times 10^5, a_i < 3 \times 10^5)
快慢指针
小组成员：邵品渊， 邵品砚， 蒋佳成， 顾天泽