「笔记」折半搜索（Meet in the Middle）

思想

先搜索前一半的状态，再搜索后一半的状态，再记录两边状态相结合的答案。

暴力搜索的时间复杂度通常是 $O(2^{n})$ 级别的。但折半搜索可以将时间复杂度降到 $O(2 \times 2^{\frac{n}{2}})$，再加上统计答案的时间复杂度，总复杂度几乎缩小了一半。

例题

「CEOI2015 Day2」世界冰球锦标赛

题目链接

Luogu P4799 [CEOI2015 Day2]世界冰球锦标赛

分析

用折半搜索的思想，先搜索 $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$ 测试点 Time Limit Exceeded（开 $\text{O2}$ 可过）。

参考代码

#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

分析

同样折半搜索，先搜索 $0 \sim \lfloor \frac{n}{2} \rfloor$ 的数，再搜索 $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ 的数。

每个数有「放第一组」「放第二组」「不选」共三种状态，可以在搜索的时候把「放第一组」记为 $+$，把「放第二组」记为 $-$，「不选」就不加也不减，这样两组相等就是和为 $0$。

在搜索后半部分的时候，记录答案，假设该状态的和是 $s$，则去前半部分的答案中找到所有等于 $-s$ 的结果。

直接这样交会 Wrong Answer $38$。仔细看题，要求的是找出一些数，使得它们能被分为两组。比如有四个数 $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}$。

参考代码

#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;

}

「笔记」折半搜索（Meet in the Middle）的更多相关文章

折半搜索(meet in the middle)
折半搜索(meet in the middle) 我们经常会遇见一些暴力枚举的题目,但是由于时间复杂度太过庞大不得不放弃. 由于子树分支是指数性增长,所以我们考虑将其折半优化; 前言这个 ...
LOJ3044. 「ZJOI2019」Minimax 搜索
LOJ3044. 「ZJOI2019」Minimax 搜索 https://loj.ac/problem/3044 分析: 假设$w(1)=W$,那么使得这个值变化只会有两三种可能,比$W$小 ...
Loj #3044. 「ZJOI2019」Minimax 搜索
Loj #3044. 「ZJOI2019」Minimax 搜索题目描述九条可怜是一个喜欢玩游戏的女孩子.为了增强自己的游戏水平,她想要用理论的武器武装自己.这道题和著名的 Minimax 搜索有关 ...
【LOJ】#3044. 「ZJOI2019」Minimax 搜索
LOJ#3044. 「ZJOI2019」Minimax 搜索一个菜鸡的50pts暴力设$dp[u][j]$表示$u$用$j$次操作能使得$u$的大小改变的方案数设每个点的初始答案 ...
「笔记」AC 自动机
目录写在前面定义引入构造暴力字典图优化匹配在线离线复杂度完整代码例题 P3796 [模板]AC 自动机(加强版) P3808 [模板]AC 自动机(简单版) 「JSOI2007 ...
「笔记」数位DP
目录写在前面引入求解特判优化代码例题「ZJOI2010」数字计数「AHOI2009」同类分布套路题们「SDOI2014」数数写在最后写在前面 19 年前听 zlq 讲课的时候学 ...
「ZJOI2019」Minmax搜索
传送门 Solution 叶子节点的变化区间是连续的,可得知非叶子节点的权值变化区间也是连续的由此可知,$W$的变化值的可行域也是连续的,所以只需要看它能否变为$W+1$或$W-1$ 对 ...
[LOJ#3044][动态DP]「ZJOI2019」Minimax 搜索
题目传送门容易想到一种暴力 DP:先转化成对于每个 $k$ 求出 $\max_{i\in S}|i-w_i|\le k$ 的方案数,最后差分然后问题转化成每个叶子的权值有个取值区间,注意这 ...
「笔记」$Min\_25$筛
总之我也不知道这个奇怪的名字是怎么来的. $Min\_25$筛用来计算一类积性函数前缀和. 如果一个积性函数$F(x)$在质数单点是一个可以快速计算的关于此质数的多项式. 那么可以用\(Min ...
Editing a Book 搜索 + meet in the middle
我们可以发现最多只会进行5次操作. 由此我们从双向跑dfs,用一个unordered_map来保存状态,枚举一下两边的深度即可. 如果4次仍然不可行,则只有可能是5次.所以正反最多只需要搜2层 cod ...

随机推荐

改写URL的查询字符串QUERY_STRING(转)
查询字符串是指URL请求中“问号”后面的部分.比如,http://www.nowamagic.net/?foo=bar中粗体部分就是查询字符串,其中变量名是foo,值是bar. 1. 利用QSA转换查 ...
Ftp的断点下载实现
思路:首先获取本地临时文件的大小,在通过FTp的REST命令获取远程文件的偏移,然后再RETR命令在偏移处下载.while循环对比本地文件和远程文件的字节大小,如此不断的反复以上过程,直到远程文件字 ...
使用python写天气预告
先去YY天气注册一个账号,然后就能用API了 http://www.yytianqi.com/ # encoding=utf-8import urllib.requestimport jsonimpo ...
wsl中使用原生docker
之前介绍过windows中安装docker,但是它需要用到hyper-v.hyper-v与vm不兼容非常之不方便.不过发现windows有wsl(linux子系统)遂试验,结果非常nice功能一应俱全 ...
cookiejar
referer:https://www.cnblogs.com/why957/p/9297779.html文章介绍了四种模拟登陆方法 yield Request()可以将一个新的请求返回给爬虫执行在 ...
javaScript 二分查找
什么是二分查找的,举个栗子: var arr = [1, 3, 5, 7, 9, 11, 14, 15, 17, 19, 20]; 上面有序数组, 随便给你一位 9 ,输出该数在数组中的索引. 当 ...
js的数据类型。
字符串 String 数字 Number 布尔 Boolean Null 空 Undefined Object 对象 Array 数组 json function ...
jquery bxslider幻灯片样式改造
找了很多jquery的幻灯片,都觉得不是很好,最后发现bxslider兼容性最好,移动设备支持手动翻动. 但是官方提供的显示效果真的很难看,让人难以接受.最后只能自己DIY了. bxslider官方样 ...
CROC 2016 - Elimination Round (Rated Unofficial Edition) B. Mischievous Mess Makers 贪心
B. Mischievous Mess Makers 题目连接: http://www.codeforces.com/contest/655/problem/B Description It is a ...
编程技巧：使用异或操作符（XOR）交换两数值
异或(exclusive OR)作为4种逻辑操作符之一,相对其他3种(OR/AND/NOT)来说,出场的次数非常少,是因为在日常开发中能用到它的场景本来就不多.对笔者来说,目前接触到场景只有交换两个数 ...