折半搜索笔记

前言

$01$ 爆搜的时间复杂度通常为 $O(2^n)$，只能应付 $N$ 为 $20$ 左右的题目，但是折半搜索可以应付 $N$ 为 $30$ ~ $40$ 的题目。

思想

将 $N$ 个数分为前后两半，先搜索前一半的状态，再搜索后一半的状态，分别记录两边状态能贡献的结果，后续就可以枚举前一半的贡献结果，再在右半结果二分查找，因此搜索的时间复杂度降到 $O(2\times 2^{\frac{2}{n}})$。

例题

P4799 [CEOI 2015] 世界冰球锦标赛 (Day2)

题目描述

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。

如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式

第一行，两个正整数 $N$ 和 $M(1\le N\le 40,1\le M\le 10^{18})$，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，$N$ 个以空格分隔的正整数，均不超过 $10^{16}$，代表每场比赛门票的价格。

输入格式

输出一行，表示方案的个数。由于 $N$ 十分大，注意：答案 $\le 2^{40}$。

输入样例

5 1000
100 1500 500 500 1000

输出样例

8

思路

因为 $N$ 最大能到达 $40$，因此直接 $01$ 爆搜，时间复杂度将达到 $O(2^{40})$，必然会超时，但是如果我们能降到 $O(2^{20})$ 左右，那么就可以接受，因此启发我们可以使用折半搜索，先将左右两边的结果用两个 vector 分别保存下来，将右 vector 从小到大排序，然后枚举左半边，在右 vector 中二分查找两者相加小于等于 $M$ 的最右下标 $pos$，那么对答案的贡献就是 $pos+1$。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll m, a[45];
vector<ll> lw, rw;//分别记录左右两边能提供的结果
void dfs1(int u, ll s) {//暴搜左半
	if (s > m) return;
	if (u == n / 2 + 1) {
		lw.push_back(s);
		return;
	}
	dfs1(u + 1, s);//不选
	dfs1(u + 1, s + a[u]);//选
}
void dfs2(int u, ll s) {//暴搜右半
	if (s > m) return;
	if (u == n + 1) {
		rw.push_back(s);
		return;
	}
	dfs2(u + 1, s);
	dfs2(u + 1, s + a[u]);
}
void solve()
{
	scanf("%d%lld", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	dfs1(1, 0);//左半边
	dfs2(n / 2 + 1, 0);//右半边
	ll ans = 0;
	sort(rw.begin(), rw.end());//为二分排序
	for (int i = 0; i < lw.size(); i++) {//枚举左半边
		int l = 0, r = rw.size() - 1, pos = -1;
		while (l <= r) {
			int mid = l + r >> 1;
			if (lw[i] + rw[mid] <= m) pos = mid, l = mid + 1;
			else r = mid - 1;
		}
		ans += pos + 1;
	}
	printf("%lld\n", ans);
}
int main()
{
	int t = 1;
	//scanf("%d",&t);
	while (t--) solve();
	return 0;
}

P9234 [蓝桥杯 2023 省 A] 买瓜

题目描述

小蓝正在一个瓜摊上买瓜。瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$。小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 $m$。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。如果无论怎样小蓝都无法得到总重恰好为 $m$ 的瓜，请输出 $-1$。

输入格式

输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。

输入格式

输出一行包含一个整数表示答案。

输入样例

3 10
1 3 13

输出样例

2

思路

类似上题，左右暴力搜索之后，问题就相当于转化为问左右半各选一个数，使得和恰好等于 $m$，劈瓜次数最少的次数。

对于这种恰好等于某个数，我们就不用存下来再去二分查找，可以搜索左半边的时候直接用 $map$ 来记录下（重量，劈瓜的次数），这样搜索右边的时候，对于 $x$，可以直接访问 $mp[m-x]$，跟答案取名即可。

注意点：

• 因为考虑到奇数除以二会有浮点数，我们优先把重量和 $m$ 全部乘 $2$。
• 因为有些重量，劈瓜 $0$ 次就可以得到，因此不能直接用 $mp[m-x]$ 来判断有没有存在 $m-x$ 这个重量，而应该用 $mp.count(m-x)$。

#include <bits/stdc++.h>
using namespace std;
int main() {
	map<int, int> mp;
	mp[3] = 0;
	cout << mp[3] << " " << mp.count(3);
    //会输出0 1
	return 0;
}

代码实现

#include <bits/stdc++.h>
using namespace std;
int n, m, a[35], ans = 1e9;
unordered_map<int, int> mp;//用于记录左半(结果,所需劈瓜的次数)
void dfs1(int u, int s, int cnt) {
	if (s > m || cnt >= ans) return; //剪枝
	if (s == m) ans = min(ans, cnt);
	if (u == n / 2 + 1) {
		if (!mp.count(s)) mp[s] = cnt;//如果是第一次得到该重量,记录所需劈瓜次数
		else mp[s] = min(mp[s], cnt);//否则,选取劈瓜次数少的
		return;
	}
	dfs1(u + 1, s, cnt);
	dfs1(u + 1, s + a[u], cnt);
	dfs1(u + 1, s + a[u] / 2, cnt + 1);
}
void dfs2(int u, int s, int cnt) {//搜索右半边
	if (s > m || cnt >= ans) return;
	if (s == m) ans = min(ans, cnt);
	if (u == n + 1) {
		if (mp.count(m - s)) ans = min(ans, mp[m - s] + cnt);//如果m-s存在,跟答案取min
		return;
	}
	dfs2(u + 1, s, cnt);
	dfs2(u + 1, s + a[u], cnt);
	dfs2(u + 1, s + a[u] / 2, cnt + 1);
}
void solve()
{
	scanf("%d%d", &n, &m);
	m *= 2;//防止精度问题,可以全部先乘2
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] *= 2;
	sort(a + 1, a + n + 1);
	dfs1(1, 0, 0);
	dfs2(n / 2 + 1, 0, 0);
	if (ans == 1e9) ans = -1;
	printf("%d\n", ans);
}
int main()
{
	int t = 1;
	//scanf("%d",&t);
	while (t--) solve();
	return 0;
}

简单集合之和

题目描述

给了你一个长度为 $n$ 的序列：$a_1,a_2,...,a_n$。

现在你需要从中选出任意个数，其中每个数最多选 $1$ 次，并且组成一个集合，同时需要你找出对 $x$ 取模后最大的集合之和。

现在请你输出该集合之和对 $x$ 取余后的结果。

输入格式

第一行有两个正整数 $n(\le 35)$，$x(10^9)$，意义如题。

第二行有 $n$ 个正整数：$a_1,a_2,...,a_n(a_i\le 10^9)$。

输出格式

输出一个整数，表示所选子序列之和对 $x$ 取模后的结果。

输入样例

3 20
199 41 299

输出样例

19

思路

折半搜索左右两半，过程中可以直接取模 $x$，将结果存下来，问题就转化为了两个集合中各取一个数，使得相加的和取模 $x$ 的值最大。

对于这个新的问题，我们知道每个数的值在 $[0,x-1]$，枚举左半边的值 $w$，那么我们贪心地肯定希望有右半边有 $x-1-w$，可证明对于 $x$，最大值总是 $x$ 和 $x+($小于等于 $x-1-w$ 的最大数$)$其中一个，所以我们把右半边从小到大排序，每次二分小于等于 $x-1-w$ 的最右位置，跟答案取 max 即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n, x, a[40];
vector<int> lw, rw;//分别保存左右搜索能得到的值
void dfs1(int u, int s) {
	if (u == n / 2 + 1) {
		lw.push_back(s);
		return;
	}
	dfs1(u + 1, s);//不选
	dfs1(u + 1, (s + a[u]) % x);//选
}
void dfs2(int u, int s) {
	if (u == n + 1) {
		rw.push_back(s);
		return;
	}
	dfs2(u + 1, s);
	dfs2(u + 1, (s + a[u]) % x);
}
void solve()
{
	scanf("%d%d", &n, &x);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	dfs1(1, 0), dfs2(n / 2 + 1, 0);
	sort(rw.begin(), rw.end());//为后续二分排序
	int ans = 0;
	for (int i = 0; i < lw.size(); i++) {//枚举左半边的值
		int l = 0, r = rw.size() - 1, pos = -1;
		ans = max(ans, lw[i]);
		while (l <= r) {
			int mid = l + r >> 1;
			if (rw[mid] <= x - 1 - lw[i]) pos = mid, l = mid + 1;
			else r = mid - 1;
		}
		if (pos != -1) ans = max(ans, lw[i] + rw[pos]);
	}
	printf("%d\n", ans);
}
int main()
{
	int t = 1;
	//scanf("%d",&t);
	while (t--) solve();
	return 0;
}