「筆記」折半搜索（Meet in the Middle）

2022 年 7 月 6 日
筆記
C++ 信競, 折半搜索, 筆記

思想

先搜索前一半的狀態，再搜索後一半的狀態，再記錄兩邊狀態相結合的答案。

暴力搜索的時間複雜度通常是 \(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;
}

Tags: C++ 信競折半搜索筆記